Benutzer:DerSpezialist/Ganzzahlige Quadratwurzel

Dieser Artikel (Ganzzahlige Quadratwurzel) ist im Entstehen begriffen und noch nicht Bestandteil der freien Enzyklopädie Wikipedia.

Wenn du dies liest:

• Der Text kann teilweise in einer Fremdsprache verfasst, unvollständig sein oder noch ungeprüfte Aussagen enthalten.
• Wenn du Fragen zum Thema hast, nimm am besten Kontakt mit dem Autor DerSpezialist auf.

Wenn du diesen Artikel überarbeitest:

• Bitte denke daran, die Angaben im Artikel durch geeignete Quellen zu belegen und zu prüfen, ob er auch anderweitig den Richtlinien der Wikipedia entspricht (siehe Wikipedia:Artikel).
• Nach erfolgter Übersetzung kannst du diese Vorlage entfernen und den Artikel in den Artikelnamensraum verschieben. Die entstehende Weiterleitung kannst du schnelllöschen lassen.
• Importe inaktiver Accounts, die länger als drei Monate völlig unbearbeitet sind, werden gelöscht.

Vorlage:Importartikel/Wartung-2018-11

Die ganzzahlige Quadratwurzel (kurz isqrt von englisch integer square root ist eine Funktion der Zahlentheorie, die eine natürliche Zahl $n$ auf die größte Zahl $s\in \mathbb {N}$ abbildet, sodass $s\cdot s\leq n$ ist. Insbesondere ist dann $(s+1)\cdot (s+1)>n$.

Beispielsweise ist $\operatorname {isqrt} (27)=5$,$\operatorname {isqrt} (27)=5$denn $5\cdot 5=25\leq 27$ and $6\cdot 6=36>27$.

Newtonmethode

Eine Möglichkeit, ${\sqrt {n}}$ und ${\mbox{isqrt}}(n)$ zu berechnen, ist die Newtonmethode für Nullstellen der Funktion $x^{2}-n=0$. Die Iteration

${x}_{k+1}={\frac {1}{2}}\left(x_{k}+{\frac {n}{x_{k}}}\right),\quad k\geq 0,\quad x_{0}>0.$

Die Folge $(x_{k})_{k}$ konvergiert quadratisch gegen ${\sqrt {n}}$. Allgemein ist für den Anfangswert $x_{0}=n$

$|x_{k+1}-x_{k}|<1$

wodurch $\lfloor x_{k+1}\rfloor =\lfloor {\sqrt {n}}\rfloor$ folgt.

Aussschließlich mit Ganzzahloperationen

Um $\lfloor {\sqrt {n}}\rfloor$für große $n$ zu berechnen, kann man den Quotienten der Euklidischen Division für beide Divisionen verwenden.Dadurch entstehen nur natürliche Zahlen als Zwischenergebnisse und es werden keine Fließkommazahlen benötigt. Somit ist es äquivalent, die Iterationsformel

${x}_{k+1}=\left\lfloor {\frac {1}{2}}\left(x_{k}+\left\lfloor {\frac {n}{x_{k}}}\right\rfloor \right)\right\rfloor ,\quad k\geq 0,\quad x_{0}>0,\quad x_{0}\in \mathbb {Z} .$

Weil

$\left\lfloor {\frac {1}{2}}\left(x_{k}+\left\lfloor {\frac {n}{x_{k}}}\right\rfloor \right)\right\rfloor =\left\lfloor {\frac {1}{2}}\left(x_{k}+{\frac {n}{x_{k}}}\right)\right\rfloor ,$

lässt sich zeigen, dass $\left\lfloor {\sqrt {n}}\right\rfloor$ nach endlich viele Schritten erreicht wird.

Jedoch ist $\left\lfloor {\sqrt {n}}\right\rfloor$ nicht notwendigerweise ein Fixpunkt der Iterationsoperation. Konkret ist $\left\lfloor {\sqrt {n}}\right\rfloor$ genau dann ein Fixpunkt, wenn $n+1$ eine Quadratzahl ist. Andernfalls springt die Iteration zwischen $\left\lfloor {\sqrt {n}}\right\rfloor$ und $\left\lfloor {\sqrt {n}}\right\rfloor +1$ und konvergiert nicht. Insgesamt genügt es zu überprüfen, ob die Zahl konvergiert hat oder um genau $1$ gewachsen zu sein.

Berechnung

Obwohl ${\sqrt {n}}$ für viele $n$ irrational ist, enthält die Folge $(x_{k})_{k}$ ausschließlich rationale Zahlen, wenn $x_{0}$rational ist. Daher ist es nicht nötig, den rationalen Zahlenbereich zu verlassen, was theoretische Vorteile mit sich bringt.

Abbruchkriterium

Man zeigt leicht, dass $c=1$die größtmögliche Zahl ist, für die das Abbruchkriterium

$|x_{k+1}-x_{k}|<c$

sicherstellt, dass $\lfloor x_{k+1}\rfloor =\lfloor {\sqrt {n}}\rfloor$

Implementierungen, die ungenaue Zahlendarstellungen verwenden, z. B. Fließkommazahlen, sollte die Abbruchkonstante $c$ aufgrund von Rundungsfehlern kleiner als $1$ sein.

Ziffer-für-Ziffer-Algorithmus

Der gängige Algorithmus für Stift und Papier, um die Quadratwurzel zu berechnen, arbeitet von höherwertigen Ziffern aus based on working from higher digit places to lower, and as each new digit pick the largest that will still yield a square $\leq n$. If stopping after the one's place, the result computed will be the integer square root.

Using bitwise operations

If working in base 2, the choice of digit is simplified to that between 0 (the "small candidate") and 1 (the "large candidate"), and digit manipulations can be expressed in terms of binary shift operations. With * being multiplication, << being left shift, and >> being logical right shift, a recursive algorithm to find the integer square root of any natural number is:

import std.traits : isIntegral;

T sqrt(T)(T number) pure nothrow @nogc @safe
if (isIntegral!T)
in (number >= 0)
{
    T place = T(1) << (T.sizeof * 8 - 2);

    while (place > number) place /= 4;
    T root = 0;
    while (place != 0)
    {
        if (number >= root + place)
        {
            number -= root + place;
            root += place * 2;
        }
        root >>>= 1;
        place >>>= 2;
    }
    return root;
}

Traditional pen-and-paper presentations of the digit-by-digit algorithm include various optimisations not present in the code above, in particular the trick of presubtracting the square of the previous digits which makes a general multiplication step unnecessary.

Weblinks

• Eine geometrische Betrachtung des Quadratwurzel-Algorithmus

[[Kategorie:Zahlentheorie]]