Wie ist die Quadratwurzelfunktion implementiert?

Wie ist die Quadratwurzelfunktion implementiert?

Einfache Implementierung mit Binary Search mit C ++

double root(double n){
  // Max and min are used to take into account numbers less than 1
  double lo = min(1, n), hi = max(1, n), mid;

  // Update the bounds to be off the target by a factor of 10
  while(100 * lo * lo < n) lo *= 10;
  while(100 * hi * hi > n) hi *= 0.1;

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

Beachten Sie, dass die whileSchleife bei der binären Suche am häufigsten vorkommt, aber ich persönlich bevorzuge die Verwendung forbeim Umgang mit Dezimalzahlen. Sie spart die Behandlung einiger Sonderfälle und liefert ziemlich genaue Ergebnisse aus solchen 1000oder sogar kleinen Schleifen 500(beide liefern für fast alle Zahlen das gleiche Ergebnis aber nur um sicher zu gehen).

Bearbeiten: In diesem Wikipedia-Artikel finden Sie verschiedene Methoden für spezielle Zwecke, die auf die Berechnung der Quadratwurzel spezialisiert sind.

Bearbeiten 2: Wenden Sie von @jorgbrown vorgeschlagene Aktualisierungen an, um die Funktion bei Eingaben unter 1 zu korrigieren. Wenden Sie außerdem eine Optimierung an, um die Grenzen von der Zielwurzel um den Faktor 10 zu verschieben

Auf Intel-Hardware wird es häufig zusätzlich zur Hardware-SQRT-Anweisung implementiert. Einige Bibliotheken verwenden das Ergebnis nur direkt, andere durchlaufen möglicherweise einige Runden der Newton-Optimierung, um es in den Eckfällen genauer zu machen.

Das FDLIBM (Freely Distributable LIBM) hat eine sehr schöne dokumentierte Version von sqrt. e_sqrt.c .

Sie haben eine Version, die Ganzzahlarithmetik und eine Wiederholungsformel verwendet, die jeweils ein Bit ändert.

Eine andere Methode verwendet die Newtonsche Methode. Es beginnt mit etwas schwarzer Magie und einer Nachschlagetabelle, um die ersten 8 Bits zu erhalten, und wendet dann die Wiederholungsformel an

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

Dabei ist x die Zahl, mit der wir begonnen haben. Dies ist die babylonische Methode von Herons Methode. Es stammt aus Hero of Alexandra im ersten Jahrhundert nach Christus.

Es gibt eine andere Methode, die als schnelle inverse Quadratwurzel oder Reziproot bezeichnet wird. Dabei wird "böses Gleitkomma-Bit-Level-Hacking" verwendet, um den Wert 1 / sqrt (x) zu ermitteln. i = 0x5f3759df - ( i >> 1 );Es nutzt die binäre Darstellung eines Floats unter Verwendung der Mantisse und des Exponenten. Wenn unsere Zahl x (1 + m) * 2 ^ e ist, wobei m die Mantisse und e der Exponent ist und das Ergebnis y = 1 / sqrt (x) = (1 + n) * 2 ^ f. Protokolle erstellen

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

Wir sehen also, dass der Exponententeil des Ergebnisses -1/2 der Exponent der Zahl ist. Die schwarze Magie verschiebt den Exponenten grundsätzlich bitweise und verwendet eine lineare Approximation auf der Mantisse.

Sobald Sie eine gute erste Annäherung haben, können Sie Newtons Methoden verwenden, um ein besseres Ergebnis zu erzielen, und schließlich einige Arbeiten auf Bitebene, um die letzte Ziffer zu korrigieren.

Dies ist eine Implementierung des Newton-Algorithmus, siehe https://tour.golang.org/flowcontrol/8 .

func Sqrt(x float64) float64 {
  // let initial guess to be 1
  z := 1.0
  for i := 1; i <= 10; i++ {
    z -= (z*z - x) / (2*z) // MAGIC LINE!!
    fmt.Println(z)
  }
  return z
}

Das Folgende ist eine mathematische Erklärung der magischen Linie. Angenommen, Sie möchten die Wurzel des Polynoms $ f (x) = x ^ 2 - a $ finden. Nach Newtons Methode könnten Sie mit einer anfänglichen Schätzung von $ x_0 = 1 $ beginnen. Die nächste Vermutung ist $ x_1 = x_0 - f (x_0) / f '(x_0) $, wobei $ f' (x) = 2x $. Daher ist Ihre neue Vermutung

$ x_1 = x_0 - (x_0 ^ 2 - a) / 2x_0 $

sqrt (); Funktion Hinter den Kulissen.

Es wird immer nach den Mittelpunkten in einem Diagramm gesucht. Beispiel: sqrt (16) = 4; sqrt (4) = 2;

Wenn Sie nun innerhalb von 16 oder 4 Eingaben wie sqrt (10) == geben?

Es findet den Mittelpunkt von 2 und 4, dh = x, und findet dann wieder den Mittelpunkt von x und 4 (es schließt die Untergrenze in dieser Eingabe aus). Dieser Schritt wird immer wieder wiederholt, bis die perfekte Antwort vorliegt, z. B. sqrt (10) == 3.16227766017. Er liegt s / w 2 und 4. Alle diese integrierten Funktionen werden mithilfe von Kalkül, Differenzierung und Integration erstellt.

Implementierung in Python: Der Boden des Stammwerts ist die Ausgabe dieser Funktion. Beispiel: Die Quadratwurzel von 8 ist 2.82842 ..., diese Funktion gibt die Ausgabe '2' aus.

def mySqrt(x):
        # return int(math.sqrt(x))
        if x==0 or x==1:
            return x
        else:
            start = 0
            end = x  
            while (start <= end):
                mid = int((start + end) / 2)
                if (mid*mid == x):
                    return mid
                elif (mid*mid < x):
                    start = mid + 1
                    ans = mid
                else:
                    end = mid - 1
            return ans

Ich mache auch eine sqrt-Funktion, 100000000 Iterationen dauern 14 Sekunden, immer noch nichts im Vergleich zu 1 Sekunde von sqrt

double mysqrt(double n)
{
    double x = n;
    int it = 4;
    if (n >= 90)
    {
        it = 6;
    }
    if (n >= 5000)
    {
        it = 8;
    }
    if (n >= 20000)
    {
        it = 10;
    }
    if (n >= 90000)
    {
        it = 11;
    }
    if (n >= 200000)
    {
        it = 12;
    }
    if (n >= 900000)
    {
        it = 13;
    }
    if (n >= 3000000)
    {
        it = 14;
    }
    if (n >= 10000000)
    {
        it = 15;
    }
    if (n >= 30000000)
    {
        it = 16;
    }
    if (n >= 100000000)
    {
        it = 17;
    }

    if (n >= 300000000)
    {
        it = 18;
    }
    if (n >= 1000000000)
    {
        it = 19;
    }

    for (int i = 0; i < it; i++)
    {
        x = 0.5*(x+n/x);
    }
    return x;
}

Die schnellste Implementierung ist jedoch:

float Q_rsqrt( float number )
{
    long i;
    float x2, y;
    const float threehalfs = 1.5F;

    x2 = number * 0.5F;
    y  = number;
    i  = * ( long * ) &y;                       // evil floating point bit level hacking
    i  = 0x5f3759df - ( i >> 1 );               // what the fuck?
    y  = * ( float * ) &i;
    y  = y * ( threehalfs - ( x2 * y * y ) );   // 1st iteration
//  y  = y * ( threehalfs - ( x2 * y * y ) );   // 2nd iteration, this can be removed

    return y;
}

float mysqrt(float n) {return 1/Q_rsqrt(n);}

Formula: root(number, <root>, <depth>) == number^(root^(-depth))

Usage: root(number,<root>,<depth>)

Example: root(16,2) == sqrt(16) == 4
Example: root(16,2,2) == sqrt(sqrt(16)) == 2
Example: root(64,3) == 4

Implementation in C#:

static double root(double number, double root = 2f, double depth = 1f)
{
    return Math.Pow(number, Math.Pow(root, -depth));
}

Bisherige Lösungen waren hauptsächlich Gleitkomma-Lösungen ... und es wurde auch angenommen, dass eine Divisionsanweisung verfügbar und schnell ist.

Hier ist eine einfache, unkomplizierte Routine, die weder FP noch Divide verwendet. Jede Zeile berechnet ein anderes Bit im Ergebnis, mit Ausnahme der ersten if-Anweisung, die die Routine beschleunigt, wenn die Eingabe klein ist.

constexpr unsigned int root(unsigned int x) {
  unsigned int i = 0;
  if (x >= 65536) {
    if ((i + 32768) * (i + 32768) <= x) i += 32768;
    if ((i + 16384) * (i + 16384) <= x) i += 16384;
    if ((i + 8192) * (i + 8192) <= x) i += 8192;
    if ((i + 4096) * (i + 4096) <= x) i += 4096;
    if ((i + 2048) * (i + 2048) <= x) i += 2048;
    if ((i + 1024) * (i + 1024) <= x) i += 1024;
    if ((i + 512) * (i + 512) <= x) i += 512;
    if ((i + 256) * (i + 256) <= x) i += 256;
  }
  if ((i + 128) * (i + 128) <= x) i += 128;
  if ((i + 64) * (i + 64) <= x) i += 64;
  if ((i + 32) * (i + 32) <= x) i += 32;
  if ((i + 16) * (i + 16) <= x) i += 16;
  if ((i + 8) * (i + 8) <= x) i += 8;
  if ((i + 4) * (i + 4) <= x) i += 4;
  if ((i + 2) * (i + 2) <= x) i += 2;
  if ((i + 1) * (i + 1) <= x) i += 1;
  return i;
}

So berechnen Sie die Quadratwurzel (ohne die eingebaute Funktion math.sqrt zu verwenden):

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();

    }

}

Es gibt etwas, das als babylonische Methode bezeichnet wird.

static float squareRoot(float n)
{

    /*We are using n itself as 
    initial approximation This 
    can definitely be improved */
    float x = n;
    float y = 1;

    // e decides the accuracy level
    double e = 0.000001;
    while(x - y > e)
    {
        x = (x + y)/2;
        y = n/x;
    }
    return x;
}

Weitere Informationen finden Sie unter: https://www.geeksforgeeks.org/square-root-of-a-perfect-square/

Für den Fall, dass es keine Spezifikationen gibt, ob die eingebaute Ceil- oder Round-Funktion nicht verwendet werden soll, finden Sie hier einen rekursiven Ansatz in Java, um die Quadratwurzel einer vorzeichenlosen Zahl mithilfe der Newton-Raphson-Methode zu ermitteln.

public class FindSquareRoot {

    private static double newtonRaphson(double N, double X, double oldX) {

        if(N <= 0) return 0;

        if (Math.round(X) == Math.ceil(oldX))
            return X;

        return newtonRaphson(N, X - ((X * X) - N)/(2 * X), X);
    }

    //Driver method
    public static void main (String[] args) {
        System.out.println("Square root of 48.8: " + newtonRaphson(48.8, 10, 0));
    }
}

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;
}

Nach meiner Lösung in Golang.

package main

import (
   "fmt"
)

func Sqrt(x float64) float64 {
   z := 1.0 // initial guess to be 1
   i := 0
   for int(z*z) != int(x) { // until find the first approximation
      // Newton root algorithm
      z -= (z*z - x) / (2 * z)
      i++
   }
   return z
}

func main() {
   fmt.Println(Sqrt(8900009870))
}

Nach einer klassischen / gemeinsamen Lösung.

package main

import (
"fmt"
"math"
)

func Sqrt(num float64) float64 {
   const DIFF = 0.0001 // To fix the precision
   z := 1.0

   for {
      z1 := z - (((z * z) - num) / (2 * z))
      // Return a result when the diff between the last execution 
      // and the current one is lass than the precision constant
      if (math.Abs(z1 - z) < DIFF) {
         break
      }
      z = z1
   }

   return z
}


func main() {
   fmt.Println(Sqrt(94339))
}

Weitere Informationen finden Sie hier

Verwendung : root (Anzahl, root, Tiefe)

Beispiel : root (16,2) == sqrt (16) == 4
Beispiel : root (16,2,2) == sqrt (sqrt (16)) == 2
Beispiel : root (64,3) == 4

Implementierung in C # :

double root(double number, double root, double depth = 1f)
{
    return number ^ (root ^ (-depth));
}

Verwendung : Sqrt (Anzahl, Tiefe)

Beispiel : Sqrt (16) == 4
Beispiel : Sqrt (8,2) == sqrt (sqrt (8))

double Sqrt(double number, double depth = 1) return root(number,2,depth);

Von: Imk0tter