Schreiben Sie Ihre eigene Quadratwurzelfunktion

Question 1

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.

Question 2

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).

Question 3

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

Question 4

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.

Question 5

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.

Question 6

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.

Question 7

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

Question 8

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)

Question 9

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

Question 10

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

Question 11

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.

Question 12

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

Question 13

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

Question 14

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

Question 15

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.

Question 16

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

Ursprung von Quake3s Fast InvSqrt ()

Question 17

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

Question 18

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

Question 19

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)

Question 20

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

Answer 1

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.

algorithm function math square-root newtons-method 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

en.wikipedia.org/wiki/Methods_of_computing_square_roots

Nibot

en.wikipedia.org/wiki/Integer_square_root

Nibot

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

Answer 2

2

Sie geben nicht an, ob das Ergebnis eine Ganzzahl sein muss oder float sein kann.

Ölmessstab

Answer 3

10

Eine ganzzahlige Quadratwurzel und eine Quadratwurzel einer ganzen Zahl sind völlig verschiedene Tiere.

JFS

Answer 4

en.wikipedia.org/wiki/Methods_of_computing_square_roots

Nibot

Answer 5

en.wikipedia.org/wiki/Integer_square_root

Nibot

Answer 6

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

Answer 7

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).

Answer 8

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

Answer 9

7

Ganzzahlige Quadratwurzel ist nicht "die genaueste Quadratwurzel einer Ganzzahl".

JFS

Answer 10

@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

Answer 11

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

Answer 12

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

Answer 13

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

Answer 14

Das ist sehr langsam im Vergleich zu Newtons Methode.

Starblue

Answer 15

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

Answer 16

4

Wie kann Newtons Methode schneller sein als O (log n)? Was ist die zeitliche Komplexität der Newtonschen Methode?

Tito

Answer 17

lol unbewusst folgt mein Verstand dem gleichen Algorithmus, während ich Quadrate von Dezimalzahlen mit einem Taschenrechner errate !!

Max Payne

Answer 18

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

Answer 19

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

Answer 20

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

Answer 21

Wenn Sie stattdessen a do … while(a-b>ErrorMargin)verwenden, vermeiden Sie die Verwendung der abs () -Funktion und machen sie etwas schneller

Cyril

Answer 22

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

Answer 23

1

Ich erinnere mich, dass ich vor einiger Zeit darüber gelesen habe. Ich bin es nicht wert, in der Gegenwart

James Davies

Answer 24

4

oh komm schon ... es ist nur Newton-Raphson;)

Stefano Borini

Answer 25

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

Answer 26

4

Wenn Sie die Quadratwurzel möchten, nehmen Sie die inverse Quadratwurzel und multiplizieren Sie sie mit der ursprünglichen Zahl.

Jason S

Answer 27

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

Answer 28

1

Es wäre großartig, wenn Sie als Antwort etwas aus Sicht der Implementierung vorschlagen würden.

Hellblauer Punkt

Answer 29

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

Answer 30

@ 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

Answer 31

1

Newtons Methode ist wirklich eine Taylor-Reihe von O (h ^ 2). Sie verfeinern nur den Punkt, um den Sie sich erweitern

ldog

Answer 32

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

Answer 33

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

Answer 34

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)

Answer 35

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

Patrik

Answer 36

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

Answer 37

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

Answer 38

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

Answer 39

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.

Answer 40

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

Answer 41

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

Answer 42

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

Answer 43

Verwenden Sie Floats anstelle von Int, um das genaue Ergebnis zu erhalten

Nikita P

Answer 44

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.

Answer 45

In acht nehmen! Willst du wie Hippasus sterben? en.wikipedia.org/wiki/Hippasus ?

Stefano Borini

Answer 46

Wenn irrationale Zahlen tödlich wären, wären wir alle tot, wenn wir über Kreise sprechen würden.

Pavium

Answer 47

Klingt nach dem altgriechischen Äquivalent des DCMA.

Stephen C

Answer 48

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

Ursprung von Quake3s Fast InvSqrt ()

Answer 49

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

Answer 50

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

Answer 51

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)

Answer 52

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

Schreiben Sie Ihre eigene Quadratwurzelfunktion

Antworten:

Berechnen Sie die Quadratwurzel mit beliebiger Genauigkeit in Python