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.
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).
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
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.
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.
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.
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
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;
}
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)
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);
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.
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;
}
// 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;
}
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);
}
}
}
Die Umkehrung, wie der Name sagt, aber manchmal "nah genug" ist "nahe genug"; eine interessante Lektüre trotzdem.
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.
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
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)
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