Heltals kvadratrod

Heltalskvadratroden (isqrt) af et naturligt tal n er et positivt tal m , som er lig med det største heltal mindre end eller lig med kvadratroden af n ,

{\mbox{isqrt}}(n)=\lgulv {\sqrt {n}}\rgulv .

For eksempel siden og . ${\mbox{isqrt}}(27)=5$ $5^{2}=25<27$ $6^{2}=36>27$

Algoritme

En af måderne at beregne og er at bruge Newtons metode til at finde en løsning på ligningen ved hjælp af den iterative formel [1] [2] ${\sqrt {n}}$ ${\mbox{isqrt}}(n)$ $x^{2}-n=0$

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

Sekvensen konvergerer kvadratisk til ved [3] . Det kan bevises, at hvis det vælges som startværdi, kan man stoppe så snart $\{x_{k}\}$ ${\sqrt {n}}$ $k\to \infty$ $x_{0}=n$

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

at sikre det $\lfloor x_{k+1}\rfloor =\lfloor {\sqrt {n))\rfloor .$

Bruger kun heltals division

For at beregne meget store heltal n kan du bruge kvotientdivision med en rest i begge divisionsoperationer. Fordelen er brugen af kun heltal for hver mellemværdi, hvilket frigør brugen af at repræsentere tal som flydende kommatal . Dette svarer til at bruge den iterative formel $\lgulv {\sqrt {n}}\rgulv$

{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}\i \mathbb {Z} .

Baseret på det faktum, at

\left\lfloor {\frac {1}{2}}\left(x_{k}+\left\lfloor {\frac {n}{x_{k))}\right\rfloor \right)\ højre\rgulv =\venstre\lgulv {\frac {1}{2}}\left(x_{k}+{\frac {n}{x_{k))}\right)\right\rgulv ,

det kan vises, at sekvensen når i et endeligt antal iterationer [4] . $\lgulv {\sqrt {n}}\rgulv$

Det vil dog ikke nødvendigvis være det faste punkt i den iterative formel ovenfor. Man kan vise, hvad der vil være et fikspunkt, hvis og kun hvis ikke er et perfekt kvadrat. Hvis er et perfekt kvadrat, konvergerer sekvensen ikke, men går ind i en cyklus af længde to, skiftevis skiftende og . For at stoppe med at arbejde er det nok at kontrollere, at enten sekvensen konvergerer (gentagelse af den forrige værdi), eller at den næste værdi er nøjagtigt en større end den nuværende, i sidstnævnte tilfælde kasseres den nye værdi. $\lgulv {\sqrt {n}}\rgulv$ $\lgulv {\sqrt {n}}\rgulv$ $n+1$ $n+1$ $\lgulv {\sqrt {n}}\rgulv$ $\lfloor {\sqrt {n}}\rfloor +1$

Brug af bitvise operationer

Hvis *middel gange, <<betyder skift til venstre og betyder >>logisk skift til højre, er den rekursive algoritme til at finde heltalskvadratroden af ethvert naturligt tal som følger:

funktion heltalSqrt(n): hvis n < 0: fejl "integerSqrt virker kun med ikke-negativ input" ellers hvis n < 2: retur n andet: smallCandidate = heltalSqrt(n >> 2) << 1 storKandidat = lilleKandidat + 1 hvis storCandidate*largeCandidate > n: returnere lilleKandidat andet: returner storKandidat

Eller iteration i stedet for rekursion:

funktion heltalSqrt(n): hvis n < 0: fejl "integerSqrt virker kun med ikke-negativ input" # Find det største skift. skift = 2 nSkiftet = n >> skift mens nShifted ≠ 0 og nShifted ≠ n: skift = skift + 2 nSkiftet = n >> skift skift = skift - 2 # Find cifrene i resultatet. resultat = 0 mens skift ≥ 0: resultat = resultat << 1 kandidatResultat = resultat + 1 hvis kandidatResultat*kandidatResultat ≤ n >> skift: resultat = kandidatResultat skift = skift - 2 returnere resultat

Beregningsområde

Selvom det er et irrationelt tal for de fleste værdier , indeholder sekvensen kun rationelle medlemmer, hvis de er rationelle. Ved hjælp af denne metode er det således ikke nødvendigt at gå uden for feltet af rationelle tal for at beregne , hvilket har en teoretisk fordel. ${\sqrt {n}}$ $n$ $\{x_{k}\}$ $x_0$ ${\mbox{isqrt}}(n)$

Stopkriterier

Det kan vises, hvilket er det største tal for standsningskriteriet $c=1$

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

som sikrer, at i ovenstående algoritme. $\lfloor x_{k+1}\rfloor =\lfloor {\sqrt {n))\rfloor$

I applikationer, der bruger andre formater end rationale (f.eks. flydende komma), skal stopkonstanten vælges til at være mindre end én for at undgå afrundingsfejl.

Se også

Metoder til beregning af kvadratrødder

Noter

↑ Metoden kaldes nogle gange "babylonsk"
↑ Fred Akalin, Computing the Integer Square Root , 2014
↑ SG Johnson, MIT Course 18.335, Square Roots via Newton's Method , 4. februar 2015
↑ Henry Cohen. Et kursus i beregningsmæssig algebraisk talteori. - Berlin, Heidelberg, New York: Springer, 1996. - T. 138. - S. 38-49. — (Kandidattekster i matematik). — ISBN 3-540-55640-0 .

Links

En geometrisk visning af kvadratrodsalgoritmen

Talteoretiske algoritmer
Enkelthedstest	Miller Miller - Rabin Luca - Lemaire pepina Agrawala - Kayala - Sachsen Nightingale - Strassen
At finde primtal	Iteration over divisorer Sigte af Eratosthenes Atkins si Sigte Sundarama
Faktorisering	Iteration over divisorer Fermat metode p −1 Pollard metode Pollards ρ-algoritme Lehmanns metode Elliptisk kurvemetode (Lenstras algoritme) Dixons algoritme Firkantet sigte
Diskret logaritme	Gelfond-Shanks algoritme Polig-Hellman algoritme Pollards ρ-metode Pollards kængurualgoritme Adlemans algoritme COS algoritme
Finder GCD	Euklids algoritme Avanceret algoritme Binær algoritme
Modulo aritmetik	Montgomerys algoritme Kinesisk restsætning
Multiplikation og division af tal	Karatsuba algoritme Toom-Cook algoritme Schönhage-Strassen algoritme Fuhrer algoritme Harvey-van der Hoeven algoritme Burnickel-Ziegler algoritme
Beregning af kvadratroden	Tonelli-Shanks algoritme Berlekamp-Rabin algoritme