Schreiben Sie Ihre eigene Quadratwurzelfunktion

74

Wie schreibt man eine eigene Funktion, um die genaueste Quadratwurzel einer ganzen Zahl zu finden?

Nachdem es googeln, fand ich diese (aus seinem archivierten Original - Link ), aber zuerst habe ich es nicht vollständig erhalten, und zweitens ist es zu annähernd.

Nehmen Sie die Quadratwurzel als nächste Ganzzahl (zur tatsächlichen Wurzel) oder als Gleitkomma an.

Hellblauer Punkt
quelle
2
Sie geben nicht an, ob das Ergebnis eine Ganzzahl sein muss oder float sein kann.
Ölmessstab
10
Eine ganzzahlige Quadratwurzel und eine Quadratwurzel einer ganzen Zahl sind völlig verschiedene Tiere.
JFS
1
find where [it](http://nlindblad.org/2007/04/04/write-your-own-square-root-function/) has been movedLassen Sie mich das Webarchiv einbinden, anstatt zu beschuldigen, es nicht als lahme Ausrede tun zu können .
Graubart

Antworten:

82

Das Folgende berechnet den Boden (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 in Crandall & Pomerance, "Prime Numbers: A Computational Perspective". Der Grund, warum Sie diese Version verwenden sollten, ist, dass Personen, die wissen, was sie tun, bewiesen haben, dass sie genau auf dem Boden der Quadratwurzel konvergiert. Dies ist einfach, sodass die Wahrscheinlichkeit eines Implementierungsfehlers gering ist. Es ist auch schnell (obwohl es möglich ist, einen noch schnelleren Algorithmus zu konstruieren - aber das richtig zu machen ist viel komplexer). Eine ordnungsgemäß implementierte binäre Suche kann für sehr kleine N schneller sein, aber dort können Sie auch eine Nachschlagetabelle verwenden.

Um auf die nächste ganze Zahl zu runden , 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; Andernfalls wählen Sie t / 2. Beachten Sie, dass dies auf ein Unentschieden rundet; Sie können auch abrunden (oder auf gerade runden), indem Sie prüfen, ob der Rest ungleich Null ist (dh ob t ^ 2 == 4N).

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

Fredrik Johansson
quelle
4
Newtwons Methode wäre der Weg, den ich gehen würde. Es konvergiert in einer quadratischen Anzahl von Iterationen und verhält sich für die meisten anfänglichen Vermutungen sehr gut.
ldog
7
Ganzzahlige Quadratwurzel ist nicht "die genaueste Quadratwurzel einer Ganzzahl".
JFS
@fredrikj: Ihre Antwort immer ergibt sich eine ganze Zahl . Schlagen Sie vor, dass "die genaueste Quadratwurzel einer ganzen Zahl" immer eine ganze Zahl ist ?
JFS
11
Offensichtlich ist "die genaueste Quadratwurzel" die Quadratwurzel selbst. Für eine numerische Annäherung müssen Sie also angeben, ob Sie die nächste Ganzzahl, einen Gleitkommawert mit gegebener Genauigkeit oder etwas anderes möchten. In diesem Fall hat das Poster nach der "nächsten Ganzzahl" gefragt, die dieser Algorithmus Ihnen gibt.
Fredrik Johansson
2
@NairG Angenommen, Sie schreiben eine Nummer Sund Shaben KZiffern. Dann 10^K <= S <= 10^{K+1}. Dies impliziert 10^(2K) <= S**2 < 10^(2k+2). Das heißt, wenn Sie Quadratwurzel von finden möchten N, hat es eine Länge zwischen der Hälfte der Länge von Nund eine Nummer eins größer. Letzteres ist also ein guter Ausgangspunkt. Diese Zeile macht es, aber mit 2 als Basis.
Ende
38

Abhängig von Ihren Anforderungen kann eine einfache Divide-and-Conquer-Strategie verwendet werden. Es konvergiert nicht so schnell wie einige andere Methoden, aber für Anfänger ist es möglicherweise viel einfacher zu verstehen. Da es sich um einen O (log n) -Algorithmus handelt (der den Suchraum bei jeder Iteration halbiert), beträgt 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 diesem und quadrieren ihn. Wenn das Quadrat höher als Ihre Zahl ist, müssen Sie sich auf Zahlen konzentrieren, die kleiner als der Mittelpunkt sind. 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 Teile teilen (wenn er keine rationale Quadratwurzel hat). In der Realität wird den Computern irgendwann die Präzision ausgehen 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, damit 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
paxdiablo
quelle
Das ist sehr langsam im Vergleich zu Newtons Methode.
Starblue
32
Daher mein erster Absatz - die Absicht dieser Antwort war es, einen Weg aufzuzeigen, der kein Verständnis des Kalküls erfordert. Wenn Sie die Newton-Methode blind (ohne Verständnis) verwenden möchten, ist das natürlich in Ordnung - es wird meine Methode aus dem Wasser sprengen. Aber ich habe nicht alle diese Tabellen in meine Antwort aufgenommen, um ihre Geschwindigkeit zu beweisen - sie sind da, um zu erziehen.
Paxdiablo
4
Wie kann Newtons Methode schneller sein als O (log n)? Was ist die zeitliche Komplexität der Newtonschen Methode?
Tito
lol unbewusst folgt mein Verstand dem gleichen Algorithmus, während ich Quadrate von Dezimalzahlen mit einem Taschenrechner errate !!
Max Payne
16

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: Quadratwurzel (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 können, 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 veranschaulicht den Prozess und ist leicht zu verstehen.

Achten Sie nur darauf, die Errormargin auf 1 zu setzen, wenn Sie Ganzzahlen verwenden. Andernfalls haben Sie eine Endlosschleife.

Toon Krijthe
quelle
Das ist der beste mir bekannte Algorithmus zum Berechnen einer ganzzahligen Quadratwurzel, aber ich bin nicht sicher, ob der Rundungsmodus deterministisch ist (es sieht so aus, als ob er auf die nächste ganze Zahl gerundet ist, aber ich bin nicht sicher, ob dies immer der Fall ist). Am Ende gebe ich das kleinere von a und b zurück, so dass die Funktion immer den Boden zurückgibt (sqrt (x)).
Victor Liu
Dies ist ein sehr guter und berühmter Algorithmus. Es wird auch Reiher oder babylonische Methode genannt. Sehr einfach zu implementieren! en.wikipedia.org/wiki/Babylonian_method#Babylonian_method
Tag318
Wenn Sie stattdessen a do … while(a-b>ErrorMargin)verwenden, vermeiden Sie die Verwendung der abs () -Funktion und machen sie etwas schneller
Cyril
13

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ß, du willst nur die Quadratwurzel, aber die Eleganz des Bebens hat meinen ganzen Widerstand überwunden :)

Übrigens spricht der oben erwähnte Artikel auch irgendwo über die langweilige Newton-Raphson-Näherung.

Kshitij Saxena -KJ-
quelle
1
Ich erinnere mich, dass ich vor einiger Zeit darüber gelesen habe. Ich bin es nicht wert, in der Gegenwart
James Davies
4
oh komm schon ... es ist nur Newton-Raphson;)
Stefano Borini
4
Die Methode ist Newton-Raphson - nur mit einer Single-Iteration-Näherung mit einem Bit-Fiddling-Hack. Newton-Raphson kann viele inverse Funktionen berechnen, nicht nur die Quadratwurzel.
Steve314
4
Wenn Sie die Quadratwurzel möchten, nehmen Sie die inverse Quadratwurzel und multiplizieren Sie sie mit der ursprünglichen Zahl.
Jason S
9

Natürlich ist es ungefähr; So funktioniert Mathe mit Gleitkommazahlen.

Wie auch immer, der Standardweg ist die Newtonsche Methode . Dies entspricht in etwa der Verwendung von Taylors Serie, die mir sofort in den Sinn kommt.

Jrockway
quelle
1
Es wäre großartig, wenn Sie als Antwort etwas aus Sicht der Implementierung vorschlagen würden.
Hellblauer Punkt
WRT den Algorithmus, es kann ungefähr sein, aber nur innerhalb bestimmter Grenzen, die Sie frei definieren können. Sie können die Schleife wiederholen, bis diese Grenzen so klein sind, wie Sie es benötigen - im Prinzip (wenn Sie sehr vorsichtig sind, wie Sie sie codieren) können Sie die gleiche Genauigkeit wie bei der Darstellung Ihrer Gleitkommazahl erreichen. Also ja, es bleibt ungefähr - aber nur, weil Gleitkomma immer ungefähr ist. Selbst 0,1 kann nur annähernd im binären Gleitkomma dargestellt werden.
Steve314
@ Ravi: Newtons Methode wird durch den Algorithmus implementiert, mit dem Sie verknüpft sind - verwenden Sie ihn also einfach. Als Ausgangspunkt sollten Sie die 2 ^ n suchen, die der Zahl am nächsten kommt, deren Wurzel Sie ziehen möchten, und dann 2 ^ (n / 2) als Ausgangspunkt verwenden. Da die Funktion f(x)=x^2jedoch überall konvex ist, funktioniert die Newton-Methode unabhängig vom Startpunkt recht gut.
Martin B
1
Newtons Methode ist wirklich eine Taylor-Reihe von O (h ^ 2). Sie verfeinern nur den Punkt, um den Sie sich erweitern
ldog
Ich habe die beiden nur unterschieden, weil die Newton-Methode so lange wiederholt wird, bis Sie "nah genug" sind. Sie können auch eine Taylor-Serie, die nach Belieben erweitert wurde, hart codieren und zur Laufzeit auswerten.
Jrockway
9

Berechnen Sie die Quadratwurzel mit beliebiger Genauigkeit in Python

#!/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
jfs
quelle
6

Es ist eine häufige Interviewfrage, die von Facebook usw. gestellt wird. 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 Newtonschen Methode fragt, wenn Sie ihn nicht wirklich verstehen?

Ich habe eine binäre suchbasierte Lösung in Java bereitgestellt, die meiner Meinung nach 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)

ChuanRocks
quelle
Es ist nicht so schwer zu verstehen. Newton-Raphson ist nur eine normale Taylor-Serie ...
Patrik
6

Fand einen großartigen Artikel über Integer Square Roots .

Dies ist eine leicht verbesserte Version, die dort vorgestellt 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;
}
Egon
quelle
Hier ist ein weiterer Artikel, der diesen Algorithmus erklärt (der einfach genug ist, um ihn mit Papier und Bleistift von Hand auszuführen): mathforum.org/library/drmath/view/52610.html
Nibot
4

Hier ist eine Möglichkeit, mithilfe der Trigonometrie eine Quadratwurzel 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);
Squarcle
quelle
4

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

Als erstes teilen Sie Ihre Zahl beginnend mit dem Dezimalpunkt in zweistellige Gruppen:
{5} {31}. {30} {25}
Dann:
1) Finden Sie die nächste Quadratwurzel für die erste Gruppe, die kleiner oder gleich der ist tatsächliche Quadratwurzel der ersten Gruppe: sqrt ({5})> = 2. Diese Quadratwurzel ist die erste Ziffer Ihrer endgültigen Antwort. Bezeichnen wir die Ziffern, die wir bereits von unserer letzten Quadratwurzel gefunden haben, als B. Also
berechnen Sie 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 Zweistellige Gruppen führen Folgendes aus:
Multiplizieren Sie den Rest mit 100 und fügen Sie ihn dann der zweiten Gruppe hinzu: 100 + 31 = 131.
Finden Sie X - nächste Ziffer Ihrer Wurzel, so dass 131> = ((B * 20) + X) * X. X = 3. 43 * 3 = 129 <131. Jetzt B = 23. Auch weil Sie keine zweistelligen Gruppen mehr links von den Dezimalstellen haben, haben Sie alle ganzzahligen Ziffern Ihrer endgültigen Wurzel gefunden.
4) Wiederholen Sie dies für {30} und {25}. Sie haben also:
{30}: 131 - 129 = 2. 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 es ist viel einfacher, wenn Sie ihn auf Papier mit derselben Notation ausführen, die Sie für die "lange Teilung" verwenden, die Sie in der Schule gelernt haben, außer dass Sie keine Teilung durchführen, sondern stattdessen die Quadratwurzel berechnen.

Eugen
quelle
3
// 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;
}
P_P
quelle
3

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

Um die Quadratwurzel von zu vaulefinden, suchen wir nach dem Ort, numberan (1..value)dem der Prädiktor 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;
 }
pierrotlefou
quelle
2

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);
        }
    }
}
Dheeraj Sachan
quelle
Verwenden Sie Floats anstelle von Int, um das genaue Ergebnis zu erhalten
Nikita P
1

Im Allgemeinen kann die Quadratwurzel einer Ganzzahl (wie z. B. 2) nur angenähert werden (nicht aufgrund von Problemen mit der Gleitkomma-Arithmetik, sondern weil es sich um irrationale Zahlen handelt, 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 der Code unter dem von Ihnen angegebenen Link verwendet, funktioniert, indem eine erste Näherung verwendet und zur Berechnung einer besseren Näherung verwendet wird.

Dies wird als Newtonsche Methode bezeichnet, und Sie können die Berechnung mit jeder neuen Näherung wiederholen, bis sie für Sie genau genug ist.

Tatsächlich muss es eine Möglichkeit geben, zu entscheiden, wann die Wiederholung gestoppt werden soll, sonst läuft sie für immer.

Normalerweise hören Sie auf, wenn der Unterschied zwischen den Näherungen geringer ist als ein von Ihnen festgelegter Wert.

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

Pavium
quelle
In acht nehmen! Willst du wie Hippasus sterben? en.wikipedia.org/wiki/Hippasus ?
Stefano Borini
Wenn irrationale Zahlen tödlich wären, wären wir alle tot, wenn wir über Kreise sprechen würden.
Pavium
Klingt nach dem altgriechischen Äquivalent des DCMA.
Stephen C
0

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

in Rubin 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
Chihung Yu
quelle
0

Angenommen, 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 unsere nächste Schätzung nehmen (warum nicht?). Wir müssen es mit der vorherigen Schätzung mitteln. Unsere nächste Schätzung, xx, wird also (x + y) / 2 oder 1,416666 sein.

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 erhaltene Näherung x zurückgeben, die abs (x * x - a) <epsilon erfüllt, wobei abs (x) der absolute Wert von x ist.

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

Nun, es gibt bereits einige Antworten, aber hier ist meine. Es ist der einfachste 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)
Hubatrix
quelle
-5

Berechnung der Quadratwurzel einer Zahl mit Hilfe der eingebauten Funktion

# include"iostream.h"
# include"conio.h"
# include"math.h"
void main()
{
clrscr();
float x;
cout<<"Enter the Number";
cin>>x;

 float squreroot(float);  
 float z=squareroot(x);
 cout<<z;


float squareroot(int x)
    {


 float s;
 s = pow(x,.5)  
 return(s);
 }    
Suyash
quelle