W jaki sposób zaimplementowano pierwiastek kwadratowy?

Question

W jaki sposób zaimplementowano pierwiastek kwadratowy?

Answer 1

Na sprzęcie firmy Intel jest często implementowany jako dodatek do instrukcji sprzętowej SQRT. Niektóre biblioteki po prostu wykorzystują wynik tego od razu, niektórzy mogą przejść przez kilka rund optymalizacji Newtona, aby uczynić go dokładniejszym w przypadku narożników.

Answer 2

Źródło here.

Opis problemu: Podano x> 0, znajdź y tak, że y^2 = x => y = x/y (jest to kluczowy krok).

1) Zgadnij pewną wartość g dla yi przetestuj ją.
2) Oblicz x/g.
3) Jeśli x/g jest wystarczająco blisko g, powróć g. W przeciwnym razie spróbuj odgadnąć lepiej.

double test(double x, double g) { 
    if closeEnough(x/g, g) 
     return g; 
    else 
     return test(x, betterGuess(x, g)); 
} 

boolean closeEnough(double a, double b) { 
    return (Math.abs(a - b) < .001); 
} 

double betterGuess(double x, double g) { 
    return ((g + x/g)/2); 
} 

---

sqrt(2)   | Guess g x/g    | New guess, (g + x/g)/2 
----------------|------------------------------|------------------------------- 
test(2, 1)  | 1  2/1  = 2  | (2  +  1)/2 = 1.5 
test(2, 1.5) | 1.5  2/1.5 = 1.3333 | (1.3333 + 1.5)/2 = 1.4167 
test(2, 1.4167) | 1.4167 2/1.4167 = 1.4118 | (1.4167 + 1.4118)/2 = 1.4142 
test(2, 1.4142) | 1.4142 ...     | ... 

Answer 3

Do obliczania pierwiastka kwadratowego (bez korzystania z funkcji wbudowany Math.sqrt):

SquareRootFunction.java

public class SquareRootFunction { 

    public double squareRoot(double value,int decimalPoints) 
    { 
     int firstPart=0; 


     /*calculating the integer part*/ 
     while(square(firstPart)<value) 
     { 
      firstPart++;    
     } 

     if(square(firstPart)==value) 
      return firstPart; 
     firstPart--; 

     /*calculating the decimal values*/ 
     double precisionVal=0.1; 
     double[] decimalValues=new double[decimalPoints]; 
     double secondPart=0; 

     for(int i=0;i<decimalPoints;i++) 
     { 
      while(square(firstPart+secondPart+decimalValues[i])<value) 
      { 
       decimalValues[i]+=precisionVal; 
      } 

      if(square(firstPart+secondPart+decimalValues[i])==value) 
      { 
       return (firstPart+secondPart+decimalValues[i]); 
      } 

      decimalValues[i]-=precisionVal; 
      secondPart+=decimalValues[i]; 
      precisionVal*=0.1; 
     } 

     return(firstPart+secondPart); 

    } 


    public double square(double val) 
    { 
     return val*val; 
    } 

} 

MainApp.java

import java.util.Scanner; 

public class MainApp { 

public static void main(String[] args) { 

    double number; 
    double result; 
    int decimalPoints; 
    Scanner in = new Scanner(System.in); 

    SquareRootFunction sqrt=new SquareRootFunction(); 
    System.out.println("Enter the number\n");    
    number=in.nextFloat(); 

    System.out.println("Enter the decimal points\n");   
    decimalPoints=in.nextInt(); 

    result=sqrt.squareRoot(number,decimalPoints); 

    System.out.println("The square root value is "+ result); 

    in.close(); 

    } 

} 

Answer 4

Proste wdrożenie używając Binary Search z C++

double root(double n){ 
    double lo = 0, hi = n, mid; 
    for(int i = 0 ; i < 1000 ; i++){ 
     mid = (lo+hi)/2; 
     if(mid*mid == n) return mid; 
     if(mid*mid > n){ 
      hi = mid; 
     }else{ 
      lo = mid; 
     } 
    } 
    return mid; 
} 

Zauważ, że while pętla jest najczęściej przy wyszukiwaniu binarnym, ale osobiście wolę korzystania for gdy ma do czynienia z liczbami po przecinku, zapisuje pewne szczególne przypadki przeładunku i dostaje dość dokładny wynik z małych pętli, takich jak ten 1000 lub nawet 500 (Oba dadzą taki sam wynik dla prawie wszystkich liczb, ale po to, by być bezpiecznym)

Answer 5

FDLIBM (swobodnie dystrybuowalna LIBM) ma całkiem niezłą udokumentowaną wersję sqrt. e_sqrt.c.

Mają jedną wersję, która wykorzystuje arytmetykę liczb całkowitych i formułę powtarzania, modyfikując po jednym bicie.

Inna metoda wykorzystuje metodę Newtona. Zaczyna się jakiejś czarnej magii i tabeli odnośników, aby uzyskać pierwsze 8 bitów, a następnie stosuje się formułę nawrotów

y_{i+1} = 1/2 * (y_i + x/y_i) 

gdzie x to numer zaczęliśmy. To jest Babylonian method metody Herona. Jego początki sięgają Bohatera Alexandra w pierwszym centuale AD.

Istnieje inna metoda o nazwie Fast inverse square root lub reciproot. który używa "złego, zmiennoprzecinkowego hakowania na poziomie bitowym", aby znaleźć wartość 1/sqrt (x). i = 0x5f3759df - (i >> 1); Wykorzystuje binarną reprezentację zmiennoprzecinkową przy użyciu mantysy i wykładnika. Jeśli naszą liczbą x jest (1 + m) * 2^e, gdzie m jest mantyzą, a e wykładnikiem i wynikiem y = 1/sqrt (x) = (1 + n) * 2^f.Wykonywanie dzienników

lg(y) = - 1/2 lg(x) 
f + lg(1+n) = -1/2 e - 1/2 lg(1+m) 

Widzimy, że część wykładnicza wyniku wynosi -1/2 wykładnika liczby. Czarna magia zasadniczo przesuwa się nieco na wykładniku i używa liniowego przybliżenia mantysy.

Po uzyskaniu dobrego pierwszego przybliżenia można użyć metod Newtona, aby uzyskać lepszy wynik, a na koniec trochę pracy na poziomie bitów, aby naprawić ostatnią cyfrę.

Answer 6

sqrt(); Funkcja Za kulisami.

Zawsze sprawdza pod kątem punktów pośrednich na wykresie. Przykład: sqrt (16) = 4; sqrt (4) = 2;

Teraz, jeśli podasz jakieś dane wejściowe w postaci 16 lub 4 jako sqrt (10) ==?

Znajduje środkowy punkt 2 i 4, tj. = X, a następnie ponownie znajduje środkowy punkt x i 4 (nie uwzględnia dolnej granicy na tym wejściu). Powtarza ten krok raz po raz, dopóki nie uzyska idealnej odpowiedzi, tj. Sqrt (10) == 3.16227766017. To leży b/w 2 i 4. Wszystkie te wbudowane funkcje są tworzone przy użyciu rachunku różniczkowego i integracji.

Answer 7

long long int floorSqrt(long long int x) 
{ 
    long long r = 0; 
    while((long)(1<<r)*(long)(1<<r) <= x){ 
     r++; 
    } 
    r--; 
    long long b = r -1; 
    long long ans = 1 << r; 
    while(b >= 0){ 
     if(((long)(ans|1<<b)*(long)(ans|1<<b))<=x){ 
      ans |= (1<<b); 
     } 
     b--; 
    } 
    return ans; 
}