Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

--- algo:wurzel [2022-08-12 11:13] – rainer
+++ algo:wurzel [2022-09-03 14:39] (aktuell) – datum rainer
@@ Zeile 3: / Zeile 3: @@
 Autor: Rainer Glaschick
-Datum: 2011-10-15
+Datum: 2011-10-15, 2022-09-02
 Die Berechnung der Quadratwurzel ist bekannt;
@@ Zeile 329: / Zeile 329: @@
 Diese Methode wurde bereits von Konrad Zuse bei dem Rechner Z3 verwendet;
-sie kann bei Hardware-Implementationen nützlich sein.
+sie kann nützlich sein, wenn eine Division nicht vorhanden oder aufwändig ist.
-Es wird wieder die Abfrage `a/x > x` anstelle von `a > x^2` verwendet,
+Es werden die Potenzen von 2 absteigend verprobt, ob ihre Addition
-um einen Überlauf aus dem Zahlenraum zu vermeiden, auch wenn die Division
+das Ergebnis verbessert:
-mehr Rechenzeit benötigt; dies kann ggf. noch optimiert werden.
+    sqrt(n):
+        assert n<2^31
+        b = 2^15
+        r = 0
+        while b > 0
+            if (r+b)^2 <= n
+                r =+ b
+            b = b / 2
+        return r
-Hierbei werden fortlaufend die Potenzen von zwei gebildet
+Ein aufsteigendes Verproben ist nicht möglich, wie man sich am Beispiel
-und jeweils geprüft, ob deren Hinzufügen noch richtig ist:
+der Wurzel aus 16 leicht klarmacht.
-    p = 1
-    x = 0
-    while a/p > p
-       z = x + p
-       if a/z > z
-         x = z
-       p *= 2
-Allerdings wird so nur die der Wurzel nächstniedrigeren Ganzzahl
+Hingegen kann vorab die größte Potenz von 2 ermittelt werden,
-bestimmt, da mit `1` angefangen wird.
+deren Quadrat kleiner ist:
+    int sqrt(n):
+        b = 2
+        while b^2 < n
+            b = b * 2
+        r = 0
+        while b > 0
+            if (r+b)^2 <= n
+                r =+ b
+            b = b / 2
+        return r
+Dies kann aber zum Überlauf bei der Berechnung von 'b^2' führen,
+wenn n nahe am Ende des Rechenbereichs liegt;
+dies kann vermieden werden, ist aber geringfügig langsamer:
+    int sqrt(n):
+        b = 2
+        while b^2 <= n
+            if b^2 = n
+                :> b
+            b = b * 2
+        r = 0
+        while b > 0
+            if (r+b)^2 <= n
+                r =+ b
+            b = b / 2
+        return r
+Dies kann leicht für Wurzeln höheren Grades erweiteret werden:
+    int (e) root (n):
+        b = 2
+        while b^e <= n
+            b = b * 2
+        r = 0
+        while b > 0
+            if (r+b)^e <= n
+                r =+ b
+            b = b / 2
+        return r
-Man könnte auch mit der größtmöglichen Zweierpotenz anfangen
-und dann absteigen; dann werden, da die meisten Zahlen den Zahlenraum
+Bei einer Fließkomma-Arithmetik mit Zweier-Exponenten ist
-nicht ausnutzen, zu Anfang fast immer nutzlose Iterationen durchgeführt.
+gleichfalls eine Multiplikation mit 2 bzw. Division durch 2
+sehr einfach.
-Daher wird zunächst die nächstgrößere Zweierpotenz bestimmt
+Da die Heron-Folge für die Quadratwurzel weniger Iterationen benötigt als die
-und dann diese wieder halbiert, ggf. auch kleiner als 1,
+Intervallschachtelung, ist sie effzienter, wenn eine Division verfügbar ist.
-bis die vorgegebene Genauigkeit erreicht ist.
-Dabei wird immer die nächste Zweierpotenz subtrahiert;
-d.h. der laufende Wert von `x` ist in der Iteration stets zu groß:
-    y = 1
-    while a/y > y
-      y *= 2
-    x = y
-    while a/x < x
-      y = y/2
-      z = x - y
-      if a/z > z
-        x = z
-      y = y / 2
 Iterative Akkumulation
@@ Zeile 404: / Zeile 431: @@
 Auf Basis dieser Methode, jedoch erheblich optimiert,
 wurde in der ENIAC die Wurzelberechnung realisiert:
-[http://www4.wittenberg.edu/academics/mathcomp/bjsdir/ENIACSquareRoot.htm]
+[https://bshelburne.wittenberguniversity.org/HowTheENIACTookASquareRoot011909.pdf]