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.

Die ganzzahlige Quadratwurzel (kurz isqrt von englisch integer square root ist eine Funktion der Zahlentheorie, die eine natürliche Zahl auf die größte Zahl abbildet, sodass ist. Insbesondere ist dann .

Beispielsweise ist ,denn and .

Newtonmethode

Bearbeiten

Eine Möglichkeit,   und   zu berechnen, ist die Newtonmethode für Nullstellen der Funktion  . Die Iteration

 

Die Folge   konvergiert quadratisch gegen  . Allgemein ist für den Anfangswert  

 

wodurch   folgt.

Aussschließlich mit Ganzzahloperationen

Bearbeiten

Um  für große   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

 

Weil

 

lässt sich zeigen, dass   nach endlich viele Schritten erreicht wird.

Jedoch ist   nicht notwendigerweise ein Fixpunkt der Iterationsoperation. Konkret ist   genau dann ein Fixpunkt, wenn   eine Quadratzahl ist. Andernfalls springt die Iteration zwischen   und   und konvergiert nicht. Insgesamt genügt es zu überprüfen, ob die Zahl konvergiert hat oder um genau   gewachsen zu sein.

Berechnung

Bearbeiten

Obwohl   für viele   irrational ist, enthält die Folge   ausschließlich rationale Zahlen, wenn  rational ist. Daher ist es nicht nötig, den rationalen Zahlenbereich zu verlassen, was theoretische Vorteile mit sich bringt.

Abbruchkriterium

Bearbeiten

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

 

sicherstellt, dass  

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

Ziffer-für-Ziffer-Algorithmus

Bearbeiten

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  . If stopping after the one's place, the result computed will be the integer square root.

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.

Bearbeiten

[[Kategorie:Zahlentheorie]]