wake-up-neo.com

Schreiben Sie Ihre eigene Quadratwurzelfunktion

Wie schreibt man eine eigene Funktion zum Finden der genauesten Quadratwurzel einer ganzen Zahl?

Nachdem ich es gegoogelt hatte, fand ich this (archiviert von seinem ursprünglichen Link ), aber erstens habe ich es nicht vollständig verstanden, und zweitens ist es auch ungefähr.

Nehmen Sie die Quadratwurzel als nächste Ganzzahl (zur eigentlichen Wurzel) oder als Float an.

67
Pale Blue Dot

Das Folgende berechnet die Etage (sqrt (N)) für N> 0:

x = 2^ceil(numbits(N)/2)
loop:
    y = floor((x + floor(N/x))/2)
    if y >= x
        return x
    x = y

Dies ist eine Version von Newtons Methode, die in Crandall & Pomerance "Prime Numbers: A Computational Perspective" enthalten ist. Der Grund, warum Sie diese Version verwenden sollten, ist, dass Personen, die wissen, was sie tun, bewiesen haben, dass sie genau auf den Boden der Quadratwurzel zusammenlaufen, und dass die Wahrscheinlichkeit eines Implementierungsfehlers einfach ist. Es ist auch schnell (obwohl es möglich ist, einen noch schnelleren Algorithmus zu konstruieren - dies ist jedoch viel komplexer). Eine ordnungsgemäß implementierte binäre Suche kann für sehr kleines N schneller sein, aber dort können Sie auch eine Nachschlagetabelle verwenden.

Um zu runden nächste Ganzzahl, berechnen Sie einfach t = floor (sqrt (4N)) mit dem obigen Algorithmus. Wenn das niedrigstwertige Bit von t gesetzt ist, wählen Sie x = (t + 1)/2; ansonsten wähle t/2. Beachten Sie, dass dies auf ein Unentschieden endet. Sie können auch abrunden (oder auf gerundet), indem Sie prüfen, ob der Rest ungleich Null ist (d. h. ob t ^ 2 == 4N).

Beachten Sie, dass Sie keine Gleitkomma-Arithmetik verwenden müssen. Eigentlich sollten Sie nicht. Dieser Algorithmus sollte vollständig unter Verwendung von Ganzzahlen implementiert werden (insbesondere geben die floor () - Funktionen nur an, dass eine reguläre Ganzzahldivision verwendet werden sollte).

76

Je nach Ihren Anforderungen kann eine einfache Divide-and-Conquer-Strategie verwendet werden. Es wird nicht wie fast wie andere Methoden konvergieren, aber für einen Anfänger ist es möglicherweise viel einfacher zu verstehen. Da es sich dabei um einen O (log n) -Algorithmus handelt (wobei der Suchraum bei jeder Iteration halbiert wird), ist der schlechteste Fall für einen 32-Bit-Float 32 Iterationen.

Angenommen, Sie möchten die Quadratwurzel von 62.104. Sie wählen einen Wert auf halbem Weg zwischen 0 und so aus und quadrieren diesen. Wenn das Quadrat höher als Ihre Zahl ist, müssen Sie sich auf Zahlen konzentrieren, die unter dem Mittelpunkt liegen. Wenn es zu niedrig ist, konzentrieren Sie sich auf die höheren.

Mit echter Mathematik könnten Sie den Suchraum für immer in zwei teilen (wenn er keine vernünftige Quadratwurzel hat). In der Realität werden die Computer irgendwann an Genauigkeit verfallen und Sie haben Ihre Annäherung. Das folgende C-Programm veranschaulicht den Punkt:

#include <stdio.h>
#include <stdlib.h>

int main (int argc, char *argv[]) {
    float val, low, high, mid, oldmid, midsqr;
    int step = 0;

    // Get argument, force to non-negative.

    if (argc < 2) {
        printf ("Usage: sqrt <number>\n");
        return 1;
    }
    val = fabs (atof (argv[1]));

    // Set initial bounds and print heading.

    low = 0;
    high = mid = val;
    oldmid = -1;

    printf ("%4s  %10s  %10s  %10s  %10s  %10s    %s\n",
        "Step", "Number", "Low", "High", "Mid", "Square", "Result");

    // Keep going until accurate enough.

    while (fabs(oldmid - mid) >= 0.00001) {
        oldmid = mid;

        // Get midpoint and see if we need lower or higher.

        mid = (high + low) / 2;
        midsqr = mid * mid;
        printf ("%4d  %10.4f  %10.4f  %10.4f  %10.4f  %10.4f  ",
            ++step, val, low, high, mid, midsqr);
        if (mid * mid > val) {
            high = mid;
            printf ("- too high\n");
        } else {
            low = mid;
            printf ("- too low\n");
        }
    }

    // Desired accuracy reached, print it.

    printf ("sqrt(%.4f) = %.4f\n", val, mid);
    return 0;
}

Hier sind ein paar Läufe, so dass Sie hoffentlich eine Vorstellung davon bekommen, wie es funktioniert. Für 77:

pax> sqrt 77
Step      Number         Low        High         Mid      Square    Result
   1     77.0000      0.0000     77.0000     38.5000   1482.2500  - too high
   2     77.0000      0.0000     38.5000     19.2500    370.5625  - too high
   3     77.0000      0.0000     19.2500      9.6250     92.6406  - too high
   4     77.0000      0.0000      9.6250      4.8125     23.1602  - too low
   5     77.0000      4.8125      9.6250      7.2188     52.1104  - too low
   6     77.0000      7.2188      9.6250      8.4219     70.9280  - too low
   7     77.0000      8.4219      9.6250      9.0234     81.4224  - too high
   8     77.0000      8.4219      9.0234      8.7227     76.0847  - too low
   9     77.0000      8.7227      9.0234      8.8730     78.7310  - too high
  10     77.0000      8.7227      8.8730      8.7979     77.4022  - too high
  11     77.0000      8.7227      8.7979      8.7603     76.7421  - too low
  12     77.0000      8.7603      8.7979      8.7791     77.0718  - too high
  13     77.0000      8.7603      8.7791      8.7697     76.9068  - too low
  14     77.0000      8.7697      8.7791      8.7744     76.9893  - too low
  15     77.0000      8.7744      8.7791      8.7767     77.0305  - too high
  16     77.0000      8.7744      8.7767      8.7755     77.0099  - too high
  17     77.0000      8.7744      8.7755      8.7749     76.9996  - too low
  18     77.0000      8.7749      8.7755      8.7752     77.0047  - too high
  19     77.0000      8.7749      8.7752      8.7751     77.0022  - too high
  20     77.0000      8.7749      8.7751      8.7750     77.0009  - too high
  21     77.0000      8.7749      8.7750      8.7750     77.0002  - too high
  22     77.0000      8.7749      8.7750      8.7750     76.9999  - too low
  23     77.0000      8.7750      8.7750      8.7750     77.0000  - too low
sqrt(77.0000) = 8.7750

Für 62.104:

pax> sqrt 62.104
Step      Number         Low        High         Mid      Square    Result
   1     62.1040      0.0000     62.1040     31.0520    964.2267  - too high
   2     62.1040      0.0000     31.0520     15.5260    241.0567  - too high
   3     62.1040      0.0000     15.5260      7.7630     60.2642  - too low
   4     62.1040      7.7630     15.5260     11.6445    135.5944  - too high
   5     62.1040      7.7630     11.6445      9.7037     94.1628  - too high
   6     62.1040      7.7630      9.7037      8.7334     76.2718  - too high
   7     62.1040      7.7630      8.7334      8.2482     68.0326  - too high
   8     62.1040      7.7630      8.2482      8.0056     64.0895  - too high
   9     62.1040      7.7630      8.0056      7.8843     62.1621  - too high
  10     62.1040      7.7630      7.8843      7.8236     61.2095  - too low
  11     62.1040      7.8236      7.8843      7.8540     61.6849  - too low
  12     62.1040      7.8540      7.8843      7.8691     61.9233  - too low
  13     62.1040      7.8691      7.8843      7.8767     62.0426  - too low
  14     62.1040      7.8767      7.8843      7.8805     62.1024  - too low
  15     62.1040      7.8805      7.8843      7.8824     62.1323  - too high
  16     62.1040      7.8805      7.8824      7.8815     62.1173  - too high
  17     62.1040      7.8805      7.8815      7.8810     62.1098  - too high
  18     62.1040      7.8805      7.8810      7.8807     62.1061  - too high
  19     62.1040      7.8805      7.8807      7.8806     62.1042  - too high
  20     62.1040      7.8805      7.8806      7.8806     62.1033  - too low
  21     62.1040      7.8806      7.8806      7.8806     62.1038  - too low
  22     62.1040      7.8806      7.8806      7.8806     62.1040  - too high
  23     62.1040      7.8806      7.8806      7.8806     62.1039  - too high
sqrt(62.1040) = 7.8806

Für 49:

pax> sqrt 49
Step      Number         Low        High         Mid      Square    Result
   1     49.0000      0.0000     49.0000     24.5000    600.2500  - too high
   2     49.0000      0.0000     24.5000     12.2500    150.0625  - too high
   3     49.0000      0.0000     12.2500      6.1250     37.5156  - too low
   4     49.0000      6.1250     12.2500      9.1875     84.4102  - too high
   5     49.0000      6.1250      9.1875      7.6562     58.6182  - too high
   6     49.0000      6.1250      7.6562      6.8906     47.4807  - too low
   7     49.0000      6.8906      7.6562      7.2734     52.9029  - too high
   8     49.0000      6.8906      7.2734      7.0820     50.1552  - too high
   9     49.0000      6.8906      7.0820      6.9863     48.8088  - too low
  10     49.0000      6.9863      7.0820      7.0342     49.4797  - too high
  11     49.0000      6.9863      7.0342      7.0103     49.1437  - too high
  12     49.0000      6.9863      7.0103      6.9983     48.9761  - too low
  13     49.0000      6.9983      7.0103      7.0043     49.0598  - too high
  14     49.0000      6.9983      7.0043      7.0013     49.0179  - too high
  15     49.0000      6.9983      7.0013      6.9998     48.9970  - too low
  16     49.0000      6.9998      7.0013      7.0005     49.0075  - too high
  17     49.0000      6.9998      7.0005      7.0002     49.0022  - too high
  18     49.0000      6.9998      7.0002      7.0000     48.9996  - too low
  19     49.0000      7.0000      7.0002      7.0001     49.0009  - too high
  20     49.0000      7.0000      7.0001      7.0000     49.0003  - too high
  21     49.0000      7.0000      7.0000      7.0000     49.0000  - too low
  22     49.0000      7.0000      7.0000      7.0000     49.0001  - too high
  23     49.0000      7.0000      7.0000      7.0000     49.0000  - too high
sqrt(49.0000) = 7.0000
37
paxdiablo

Eine einfache (aber nicht sehr schnelle) Methode zur Berechnung der Quadratwurzel von X:

squareroot(x)
    if x<0 then Error
    a = 1
    b = x
    while (abs(a-b)>ErrorMargin) 
        a = (a+b)/2
        b = x/a
    endwhile
    return a;

Beispiel: squareroot (70000)

    a       b
    1   70000
35001       2
17502       4
 8753       8
 4381      16
 2199      32
 1116      63
  590     119
  355     197
  276     254
  265     264

Wie Sie sehen, definiert es eine obere und eine untere Grenze für die Quadratwurzel und verengt die Grenze, bis ihre Größe akzeptabel ist.

Es gibt effizientere Methoden, aber diese veranschaulichen den Prozess und sind leicht verständlich.

Denken Sie nur daran, den Errormargin auf 1 zu setzen, wenn Sie Ganzzahlen verwenden.

15
Toon Krijthe

Lassen Sie mich auf eine äußerst interessante Methode zur Berechnung einer inversen Quadratwurzel 1/sqrt (x) hinweisen, die in der Welt des Spieldesigns eine Legende ist, weil sie unglaublich schnell ist. Oder warten Sie, lesen Sie den folgenden Beitrag:

http://betterexplained.com/articles/understanding-quakes-fast-inverse-square-root/

PS: Ich weiß, dass Sie nur die Quadratwurzel wollen, aber die Eleganz des Bebens hat jeden Widerstand von mir überwunden :)

Übrigens spricht der oben erwähnte Artikel auch irgendwo von der langweiligen Newton-Raphson-Näherung.

13

Natürlich ist es ungefähr; So funktioniert Mathematik mit Fließkommazahlen.

Auf jeden Fall ist der Standardweg mit Newtons Methode . Dies ist ungefähr das Gleiche wie bei der Verwendung von Taylors Serie.

9
jrockway

Quadratwurzel mit beliebiger Genauigkeit in Python berechnen

#!/usr/bin/env python
import decimal

def sqrt(n):
    assert n > 0
    with decimal.localcontext() as ctx:
        ctx.prec += 2 # increase precision to minimize round off error
        x, prior = decimal.Decimal(n), None
        while x != prior: 
            prior = x
            x = (x + n/x) / 2 # quadratic convergence 
    return +x # round in a global context


decimal.getcontext().prec = 80 # desirable precision
r = sqrt(12345)
print r
print r == decimal.Decimal(12345).sqrt()

Ausgabe:

111.10805551354051124500443874307524148991137745969772997648567316178259031751676
True
9
jfs

Ich habe einen großartigen Artikel über Ganzzahlwurzeln gefunden.

Dies ist eine etwas verbesserte Version, die dort präsentiert wird:

unsigned long sqrt(unsigned long a){
    int i;
    unsigned long rem = 0;
    unsigned long root = 0;
    for (i = 0; i < 16; i++){
        root <<= 1;
        rem = (rem << 2) | (a >> 30);
        a <<= 2;
        if(root < rem){
            root++;
            rem -= root;
            root++;
        }
    }
    return root >> 1;
}
6
Egon

Es ist eine häufige Interviewfrage von Facebook usw. Ich denke nicht, dass es eine gute Idee ist, die Newton-Methode in einem Interview zu verwenden. Was ist, wenn der Interviewer Sie nach dem Mechanismus der Newton-Methode fragt, wenn Sie ihn nicht wirklich verstehen?

Ich habe eine auf binärer Suche basierende Lösung in Java bereitgestellt, von der ich glaube, dass sie jeder verstehen kann.

public int sqrt(int x) {

    if(x < 0) return -1;
    if(x == 0 || x == 1) return x;

    int lowerbound = 1;
    int upperbound = x;
    int root = lowerbound + (upperbound - lowerbound)/2;

    while(root > x/root || root+1 <= x/(root+1)){
        if(root > x/root){
            upperbound = root;
        } else {
            lowerbound = root;
        }
        root = lowerbound + (upperbound - lowerbound)/2;
    }
    return root;
}

Sie können meinen Code hier testen: leetcode: sqrt (x)

6
ChuanRocks

Hier ist eine Möglichkeit, eine Quadratwurzel mithilfe der Trigonometrie zu erhalten. Es ist nicht der schnellste Algorithmus, aber es ist präzise. Code ist in Javascript:

var n = 5; //number to get the square root of
var icr = ((n+1)/2); //intersecting circle radius
var sqrt = Math.cos(Math.asin((icr-1)/icr))*icr; //square root of n
alert(sqrt);
4
squarcle

Es gibt einen Algorithmus, den ich in der Schule studiert habe, mit dem Sie genaue Quadratwurzeln berechnen können (oder eine beliebig große Genauigkeit, wenn die Wurzel eine irrationale Zahl ist). Es ist definitiv langsamer als die Algorithmen von Newton, aber es ist exakt . Nehmen wir an, Sie möchten die Quadratwurzel von 531.3025 berechnen

Als Erstes teilen Sie Ihre Zahl vom Dezimalpunkt aus in 2-stellige Gruppen:
{5} {31}. {30} {25}
Dann:
1) Finden Sie die nächstgelegene Quadratwurzel für die erste Gruppe, die kleiner oder gleich der tatsächlichen Quadratwurzel der ersten Gruppe ist: sqrt ({5})> = 2. Diese Quadratwurzel ist die erste Ziffer Ihrer endgültigen Antwort. Wir bezeichnen die Ziffern, die wir bereits von unserer letzten Quadratwurzel gefunden haben, als B. Also im Moment B = 2.
2) Berechnen Sie als nächstes die Differenz zwischen {5} und B ^ 2: 5 - 4 = 1.
3) Für alle nachfolgenden 2-stelligen Gruppen machen Sie Folgendes:
Multipliziere den Rest mit 100 und füge ihn der zweiten Gruppe hinzu: 100 + 31 = 131.
Finde X - nächste Ziffer deines Stammes, so dass 131> = ((B * 20) + X) * X ist. X = 3. 43 * 3 = 129 <131. Nun ist B = 23. Da Sie keine zweistelligen Gruppen mehr vor den Dezimalstellen haben, haben Sie alle ganzzahligen Stellen Ihrer endgültigen Wurzel gefunden.
4) Wiederholen Sie dasselbe für {30} und {25}. Also hast du:
{30}: 131 - 129 = 2 · 100 + 30 = 230 · (23 · 2 · 10 + X) · X -> X = 0 -> B = 23,0 
{25}: 230 - 0 = 230. 230 * 100 + 25 = 23025. 23025> = (230 * 2 * 10 + X) * X -> X = 5 -> B = 23,05 
Endergebnis = 23.05.
Der Algorithmus sieht auf diese Weise kompliziert aus, aber er ist viel einfacher, wenn Sie ihn auf Papier mit derselben Notation machen, die Sie für die "lange Division" verwenden, die Sie in der Schule gelernt haben, mit der Ausnahme, dass Sie keine Division durchführen, sondern das Quadrat berechnen Wurzel.

4
Eugen

Das erste, was mir einfällt, ist: Dies ist ein guter Ort, um die binäre Suche zu verwenden (inspiriert von diesen großartigen Tutorials .)

Um die Quadratwurzel von vaule zu finden, durchsuchen wir die number in (1..value), wobei der Predictor zum ersten Mal wahr ist. Der Prädiktor, den wir wählen, ist number * number - value > 0.00001.

double square_root_of(double value)
{
     assert(value >= 1);
     double lo = 1.0;
     double hi = value;

     while( hi - lo > 0.00001)
     {
          double mid = lo + (hi - lo) / 2 ;
          std::cout << lo << "," << hi << "," << mid << std::endl;
          if( mid * mid - value > 0.00001)    //this is the predictors we are using 
          {
              hi = mid;
          } else {
              lo = mid;
          }

     }

    return lo;
 }
4
pierrotlefou
// Fastest way I found, an (extreme) C# unrolled version of:
// http://www.hackersdelight.org/hdcodetxt/isqrt.c.txt         (isqrt4)

// It's quite a lot of code, basically a binary search (the "if" statements)
// followed by an unrolled loop (the labels).
// Most important: it's fast, twice as fast as "Math.Sqrt".
// On my pc: Math.Sqrt ~35 ns, sqrt <16 ns (mean <14 ns)

private static uint sqrt(uint x)
{
    uint y, z;
    if (x < 1u << 16)
    {
        if (x < 1u << 08)
        {
            if (x < 1u << 04) return x < 1u << 02 ? x + 3u >> 2 : x + 15u >> 3;
            else
            {
                if (x < 1u << 06)
                { y = 1u << 03; x -= 1u << 04; if (x >= 5u << 02) { x -= 5u << 02; y |= 1u << 02; } goto L0; }
                else
                { y = 1u << 05; x -= 1u << 06; if (x >= 5u << 04) { x -= 5u << 04; y |= 1u << 04; } goto L1; }
            }
        }
        else                                             // slower (on my pc): .... y = 3u << 04; } goto L1; }
        {
            if (x < 1u << 12)
            {
                if (x < 1u << 10)
                { y = 1u << 07; x -= 1u << 08; if (x >= 5u << 06) { x -= 5u << 06; y |= 1u << 06; } goto L2; }
                else
                { y = 1u << 09; x -= 1u << 10; if (x >= 5u << 08) { x -= 5u << 08; y |= 1u << 08; } goto L3; }
            }
            else
            {
                if (x < 1u << 14)
                { y = 1u << 11; x -= 1u << 12; if (x >= 5u << 10) { x -= 5u << 10; y |= 1u << 10; } goto L4; }
                else
                { y = 1u << 13; x -= 1u << 14; if (x >= 5u << 12) { x -= 5u << 12; y |= 1u << 12; } goto L5; }
            }
        }
    }
    else
    {
        if (x < 1u << 24)
        {
            if (x < 1u << 20)
            {
                if (x < 1u << 18)
                { y = 1u << 15; x -= 1u << 16; if (x >= 5u << 14) { x -= 5u << 14; y |= 1u << 14; } goto L6; }
                else
                { y = 1u << 17; x -= 1u << 18; if (x >= 5u << 16) { x -= 5u << 16; y |= 1u << 16; } goto L7; }
            }
            else
            {
                if (x < 1u << 22)
                { y = 1u << 19; x -= 1u << 20; if (x >= 5u << 18) { x -= 5u << 18; y |= 1u << 18; } goto L8; }
                else
                { y = 1u << 21; x -= 1u << 22; if (x >= 5u << 20) { x -= 5u << 20; y |= 1u << 20; } goto L9; }
            }
        }
        else
        {
            if (x < 1u << 28)
            {
                if (x < 1u << 26)
                { y = 1u << 23; x -= 1u << 24; if (x >= 5u << 22) { x -= 5u << 22; y |= 1u << 22; } goto La; }
                else
                { y = 1u << 25; x -= 1u << 26; if (x >= 5u << 24) { x -= 5u << 24; y |= 1u << 24; } goto Lb; }
            }
            else
            {
                if (x < 1u << 30)
                { y = 1u << 27; x -= 1u << 28; if (x >= 5u << 26) { x -= 5u << 26; y |= 1u << 26; } goto Lc; }
                else
                { y = 1u << 29; x -= 1u << 30; if (x >= 5u << 28) { x -= 5u << 28; y |= 1u << 28; } }
            }
        }
    }
    z = y | 1u << 26; y /= 2; if (x >= z) { x -= z; y |= 1u << 26; }
Lc: z = y | 1u << 24; y /= 2; if (x >= z) { x -= z; y |= 1u << 24; }
Lb: z = y | 1u << 22; y /= 2; if (x >= z) { x -= z; y |= 1u << 22; }
La: z = y | 1u << 20; y /= 2; if (x >= z) { x -= z; y |= 1u << 20; }
L9: z = y | 1u << 18; y /= 2; if (x >= z) { x -= z; y |= 1u << 18; }
L8: z = y | 1u << 16; y /= 2; if (x >= z) { x -= z; y |= 1u << 16; }
L7: z = y | 1u << 14; y /= 2; if (x >= z) { x -= z; y |= 1u << 14; }
L6: z = y | 1u << 12; y /= 2; if (x >= z) { x -= z; y |= 1u << 12; }
L5: z = y | 1u << 10; y /= 2; if (x >= z) { x -= z; y |= 1u << 10; }
L4: z = y | 1u << 08; y /= 2; if (x >= z) { x -= z; y |= 1u << 08; }
L3: z = y | 1u << 06; y /= 2; if (x >= z) { x -= z; y |= 1u << 06; }
L2: z = y | 1u << 04; y /= 2; if (x >= z) { x -= z; y |= 1u << 04; }
L1: z = y | 1u << 02; y /= 2; if (x >= z) { x -= z; y |= 1u << 02; }
L0: return x > y ? y / 2 | 1u : y / 2;
}
3
P_P

verwenden Sie die binäre Suche

public class FindSqrt {

    public static void main(String[] strings) {

        int num = 10000;
        System.out.println(sqrt(num, 0, num));
    }

    private static int sqrt(int num, int min, int max) {
        int middle = (min + max) / 2;
        int x = middle * middle;
        if (x == num) {
            return middle;
        } else if (x < num) {
            return sqrt(num, middle, max);
        } else {
            return sqrt(num, min, middle);
        }
    }
}
2
Dheeraj Sachan

Die Umkehrung, wie der Name sagt, aber manchmal "nah genug" ist "nahe genug"; eine interessante Lektüre trotzdem.

Ursprung von Quake3s Fast InvSqrt ()

1
user166390

Im Allgemeinen kann die Quadratwurzel einer ganzen Zahl (wie zum Beispiel 2) nur approximiert werden (nicht wegen Problemen mit der Gleitkomma-Arithmetik, sondern weil sie sind irrationale Zahlen, die nicht genau berechnet werden können.

Natürlich sind einige Annäherungen besser als andere. Ich meine natürlich, dass der Wert 1,732 eine bessere Annäherung an die Quadratwurzel von 3 ist als 1,7

Die Methode, die von dem Code verwendet wird, den Sie bei diesem Link angegeben haben, funktioniert, indem Sie eine erste Näherung verwenden und eine bessere Näherung berechnen.

Dies nennt man Newtons Methode, und Sie können die Berechnung mit jeder neuen Näherung wiederholen, bis für Sie genau genug ist.

In der Tat gibt es muss eine Möglichkeit zu entscheiden, wann die Wiederholung zu stoppen ist, oder sie wird für immer ausgeführt.

Normalerweise würden Sie aufhören, wenn der Unterschied zwischen den Näherungen kleiner ist als ein von Ihnen bestimmter Wert.

EDIT: Ich glaube nicht, dass es eine einfachere Implementierung geben kann als die beiden, die Sie bereits gefunden haben.

1
pavium

Eine einfache Lösung, die mit der binären Suche mit Float-Quadratwurzeln und beliebiger Genauigkeit umgehen kann

in Ruby codiert

include Math

def sqroot_precision num, precision
  upper   = num
  lower   = 0
  middle  = (upper + lower)/2.0

  while true do
    diff = middle**2 - num

    return middle if diff.abs <= precision

    if diff > 0
      upper = middle
    else diff < 0
      lower = middle
    end

    middle = (upper + lower)/2.0
  end 
end

puts sqroot_precision 232.3, 0.0000000001
0
Chihung Yu

Nun, es gibt schon einige Antworten, aber hier gehts meins Es ist das einfachste Stück Code (für mich), hier ist der Algorithmus dafür. 

Und Code in Python 2.7:

from __future__ import division 
val = 81
x = 10
def sqr(data,x):
    temp = x - ( (x**2 - data)/(2*x))
    if temp == x:
        print temp
        return
    else:
        x = temp
        return sqr(data,x)
    #x =temp 
    #sqr(data,x)
sqr(val,x)
0
hubatrix

Nehmen wir an, wir versuchen, die Quadratwurzel von 2 zu finden, und Sie haben eine Schätzung von 1,5. Wir sagen a = 2 und x = 1,5. Um eine bessere Schätzung zu berechnen, teilen wir a durch x. Dies ergibt einen neuen Wert y = 1.333333. Wir können dies jedoch nicht einfach als unseren nächsten Schätzwert betrachten (warum nicht?). Wir müssen es mit der vorherigen Schätzung mitteln. Unsere nächste Schätzung, xx, lautet (x + y)/2 oder 1,416666.

Double squareRoot(Double a, Double epsilon) {
    Double x = 0d;
    Double y = a;
    Double xx = 0d;

    // Make sure both x and y != 0.
    while ((x != 0d || y != 0d) && y - x > epsilon) {
        xx = (x + y) / 2;

        if (xx * xx >= a) {
            y = xx;
        } else {
            x = xx;
        }
    }

    return xx;
}

Epsilon bestimmt, wie genau die Approximation sein muss. Die Funktion sollte die erste Näherung x zurückgeben, die erhalten wird und abs (x * x - a) <epsilon erfüllt, wobei abs (x) der absolute Wert von x ist.

square_root(2, 1e-6)
Output: 1.4142141342163086
0
S_R