Schreiben Sie Ihre eigene Radizierfunktion
-
06-07-2019 - |
Frage
Wie schreiben Sie Ihre eigene Funktion für die genaueste Quadratwurzel einer ganzen Zahl zu finden?
es nach googeln, fand ich diese (Archiv von seinem Original-Link ), aber zuerst, ich habe es nicht vollständig erhalten, und zweitens, es ist zu annähernd.
Angenommen Quadratwurzel als nächste ganze Zahl (die eigentlichen root) oder einen Schwimmer.
Lösung
Folgende berechnet floor (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 des Newton-Verfahrens gegeben in Crandall & Pomerance "Primzahlen: A Computational Perspective". Der Grund, warum Sie diese Version verwenden sollten, ist, dass Menschen, die wissen, was sie tun, haben bewiesen, dass es genau auf den Boden der Quadratwurzel konvergiert, und es ist einfach, so ist die Wahrscheinlichkeit, zur Herstellung eines Implementierungsfehler klein ist. Es ist auch schnell (obwohl es möglich, einen noch schnelleren Algorithmus zu konstruieren - aber viel komplexer das richtig ist zu tun). Eine richtig implementiert binäre Suche kann für sehr kleines N schneller sein, aber es können Sie auch eine Lookup-Tabelle verwendet werden.
Zur Abrundung des nächsten integer, berechnen nur t = Boden (sqrt (4N)), um den Algorithmus oben. Wenn das niedrigstwertige Bit von T gesetzt ist, dann wählen, x = (t + 1) / 2; wählen sonst t / 2. Beachten Sie, dass diese auf einer Bindung abrundet; Sie könnten auch nach unten (oder rund sogar) runden, indem ich suchen, ob der Rest ist ungleich Null (das heißt, ob t ^ 2 == 4N).
Beachten Sie, dass Sie nicht brauchen, Gleitkomma-Arithmetik zu verwenden. In der Tat, sollten Sie nicht. Dieser Algorithmus sollte vollständig mit ganzen Zahlen umgesetzt werden (insbesondere der Boden () Funktionen nur zeigen, dass regelmäßige Integer-Division verwendet werden soll).
Andere Tipps
Je nach Bedarf, eine einfache Teile-und-Herrsche-Strategie verwendet werden. Es wird nicht als schnell , wie einige andere Methoden konvergieren, aber es kann viel einfacher für Anfänger zu verstehen sein. Darüber hinaus, da es sich um eine O (log n) Algorithmus (Halbieren der Suchraum jeder Iteration) ist, den schlimmsten Fall für einen 32-Bit-Float wird 32 Iterationen sein.
Angenommen, Sie haben die Quadratwurzel von 62,104 wollen. Sie wählen einen Wert auf halber Strecke zwischen 0 und das, und quadrieren sie. Wenn der Platz höher ist als Ihre Zahl ist, benötigen Sie weniger als der Mittelpunkt auf Zahlen zu konzentrieren. Ist sie zu niedrig ist, konzentrieren sich auf die höheren.
Mit einem realen Mathematik, könnten Sie halten den Suchraum in zwei Unterteile für immer (wenn es nicht eine rationale Quadratwurzel hat). In Wirklichkeit wird Computer schließlich aus Präzision ausgeführt werden, und Sie werden Ihre Annäherung haben. Das folgende C-Programm zeigt 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 ein paar Runs, so dass Sie hoffentlich eine Vorstellung bekommen, wie es funktioniert. 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
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 schnell) Methode, um die Quadratwurzel von X zu berechnen:
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 es definiert eine obere und eine untere Grenze für die Quadratwurzel und verengt sich die Grenze, bis seine Größe akzeptabel ist.
Es gibt effizientere Methoden, aber dies stellt den Prozess und ist leicht zu verstehen.
Nur hüte dich vor dem Errormargin auf 1 zu setzen, wenn ganze Zahlen, was Sie haben eine Endlosschleife verwendet wird.
Lassen Sie mich eine äußerst interessante Methode weisen darauf hin, der Berechnung einer inversen Quadratwurzel 1 / sqrt (x), die eine Legende in der Welt der Game-Design ist, weil es Geist-boggingly schnell. Oder warten, lesen Sie im 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 jeden Widerstand meinerseits überwand:)
Durch die Art und Weise, die oben genannte Artikel spricht auch über die langweilige Newton-Raphson Annäherung irgendwo.
Natürlich ist es ungefähre; das ist, wie Mathe mit Gleitkommazahlen Arbeit.
Wie auch immer, der normale Weg ist mit Newton-Verfahren . Das ist etwa die gleiche wie Taylor-Reihe verwenden, die andere Art und Weise, die sofort in den Sinn kommt.
Berechnen 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
Es ist eine gemeinsame Interviewfrage von Facebook usw. fragte ich glaube nicht, es ist eine gute Idee, die Newton-Methode in einem Interview zu verwenden. Was passiert, wenn der Interviewer Sie den Mechanismus der dem Newton-Verfahren fragen, wenn Sie nicht wirklich verstehen, oder?
I vorgesehen, um eine binäre Suche-basierte Lösung in Java, die ich jeden glauben kann, verstehen.
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)
Gefunden einen großen Artikel über Integer-Platz Roots .
Dies ist eine leicht verbesserte Version, die es dort präsentiert:
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;
}
Hier ist ein Weg, um eine Quadratwurzel zu erhalten mit Trigonometrie. Es ist nicht der schnellste Algorithmus, der von einem gewagtes Spiel, 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, die ich in der Schule gelernt, dass Sie genau Quadratwurzeln verwenden zu berechnen (oder beliebig großer Präzision, wenn die Wurzel eine irrationale Zahl ist). Es ist auf jeden Fall langsamer als Newtons Algorithmen, aber es ist genau. Lassen Sie uns sagen Sie die Quadratwurzel von 531.3025
berechnen wollen Das erste, was ist, dass Sie Ihre Nummer teilen aus dem Komma beginnen, sich in Gruppen von 2 Ziffern:
{5} {31}. {30} {25}
Dann:
1) Finden Sie die nächste Quadratwurzel für die erste Gruppe, die kleine oder gleich die tatsächlichen Quadratwurzel ersten Gruppe ist: sqrt ({5})> = 2. Diese Quadratwurzel ist die erste Ziffer Ihrer endgültigen Antwort. bezeichnen läßt die Ziffern haben wir schon von unserer letzten Quadratwurzel als B. gefunden Also im Moment B = 2
2) Als nächstes berechnen die Differenz zwischen {5} und B ^ 2: 5 - 4 = 1
3) Für alle nachfolgenden 2-stellige Gruppen wie folgt vor:
Multiplizieren der Rest bis 100, dann fügen sie zu der zweiten Gruppe: 100 + 31 = 131.
Finden X - nächste Stelle Ihrer Wurzel, so dass 131> = ((B * 20) + X) * X. X = 3. 43 * 3 = 129 <131 Nun B = 23. Auch, weil Sie nicht mehr 2-stellige Gruppen links von Dezimalstellen haben, haben Sie alle ganzzahligen Ziffern Ihrer endgültigen Wurzel gefunden.
4) Wiederholen Sie das gleiche 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 so kompliziert, aber es ist viel einfacher, wenn Sie es auf Papier tun die gleiche Schreibweise, die Sie für „long division“ verwenden Sie haben in der Schule gelernt, mit der Ausnahme, dass Sie Teilung nicht tun, sondern die Quadratwurzel berechnen.
Das erste, was mir in den Sinn kommt, ist: Das ist ein guter Ort, um durch dieses große Tutorials .)
Um die Quadratwurzel von vaule
zu finden, wir suchen die number
in (1..value)
wo der Prädiktor
ist zum ersten Mal wahr. Der Prädiktor 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 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);
}
}
}
Generell die Quadratwurzel einer ganzen Zahl (wie 2, zum Beispiel) können nur angenähert werden (nicht wegen der Probleme mit Fließkommaarithmetik, sondern weil sie irrationalen Zahlen sind, die sich nicht exakt berechnet werden).
Natürlich sind einige Annäherungen besser als andere. Ich meine, natürlich, dass der Wert 1.732 ist eine bessere Annäherung an die Quadratwurzel von 3, als 1,7
Die durch den Code verwendete Methode zu diesem Link Werke gab durch eine erste Annäherung zu nehmen und mit ihm einer besser Annäherung zu berechnen.
Dies ist Newton-Verfahren genannt, und man kann die Berechnung mit jeder neuen Annäherung wiederholen bis es ist genau genug für Sie.
In der Tat gibt muss eine Möglichkeit geben, zu entscheiden, wann die Wiederholung zu stoppen oder es läuft immer.
In der Regel würden Sie aufhören, wenn die Differenz zwischen Annäherungen ist weniger als ein Wert, den Sie entscheiden.
EDIT:. Ich glaube nicht, kann es eine einfachere Implementierung als die beiden bereits gefunden
Die inverse, wie der Name schon sagt, aber manchmal „nahe genug“ ist „nahe genug“; ein interessantes lesen sowieso.
Eine einfache Lösung, die mit Schwimmer Quadratwurzel und beliebiger Genauigkeit unter Verwendung von binärer Suche
umgehen kanncodiert in Ruby
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
Lassen Sie uns sagen, dass wir versuchen, die Quadratwurzel von 2 zu finden, und Sie haben ein Schätzwert von 1,5. Wir werden ein sagen = 2 und x = 1,5. Um eine bessere Schätzung zu berechnen, werden wir ein durch x teilen. Daraus ergibt sich ein neuer Wert y = 1,333333. Wir können aber nicht nur dies als unsere nächste Schätzung (warum nicht?). Wir müssen es mit der vorherige Schätzung mitteln. So ist unsere nächste Schätzung, xx wird (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 Annäherung sein muss. Die Funktion sollte die erste Annäherung zurückkehren x erhält sie, dass erfüllt abs (x * x - a). square_root(2, 1e-6)
Output: 1.4142141342163086
Nun gibt es bereits schon ein paar Antworten, aber hier geht Mine Es ist das einfachste Stück Code (für mich), hier ist die Algorithmus für sie.
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)
Um die Quadratwurzel aus einer Zahl mit Hilfe von eingebauter Funktion zu berechnen
# 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);
}