Egész négyzetgyök

Egy n természetes szám egész négyzetgyöke (isqrt) egy pozitív m szám , amely egyenlő azzal a legnagyobb egész számmal , amely kisebb vagy egyenlő n négyzetgyökével ,

{\mbox{isqrt}}(n)=\lfloor {\sqrt {n}}\rfloor .

Például mivel és . ${\mbox{isqrt}}(27)=5$ $5^{2}=25<27$ $6^{2}=36>27$

Algoritmus

A számítások egyik módja és a Newton-módszer használata az egyenlet megoldásának megtalálásához az iteratív képlet segítségével [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.

A sorozat négyzetesen konvergál a [3] ponthoz . Bizonyítható, hogy ha kiinduló értéknek választjuk, azonnal meg lehet állni $\{x_{k}\}$ ${\sqrt {n}}$ $k\to \infty$ $x_{0}=n$

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

annak biztosítására $\lfloor x_{k+1}\rfloor =\lfloor {\sqrt {n))\rfloor .$

Csak egész osztás használata

Nagyon nagy n egész számok kiszámításához mindkét osztási műveletben használhatja a hányados osztást maradékkal . Az előny az, hogy minden köztes értékhez csak egész számokat használunk, ami megszabadít a számok lebegőpontos számokként való ábrázolásától . Ez egyenértékű az iteratív képlet használatával $\lfloor {\sqrt {n}}\rfloor$

{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} .

Az alapján, hogy

\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 ,

kimutatható, hogy a sorozat véges számú iterációval ér el [4] . $\lfloor {\sqrt {n}}\rfloor$

Ez azonban nem feltétlenül a fenti iteratív képlet fix pontja . Meg lehet mutatni, hogy mi lesz fix pont akkor és csak akkor, ha nem tökéletes négyzet. Ha tökéletes négyzet, akkor a sorozat nem konvergál, hanem egy kettes hosszúságú ciklusba megy, felváltva és . A működés leállításához elegendő ellenőrizni, hogy a sorozat konvergál-e (az előző érték ismétlése), vagy a következő érték pontosan eggyel nagyobb-e az aktuálisnál, ez utóbbi esetben az új értéket el kell vetni. $\lfloor {\sqrt {n}}\rfloor$ $\lfloor {\sqrt {n}}\rfloor$ $n+1$ $n+1$ $\lfloor {\sqrt {n}}\rfloor$ $\lfloor {\sqrt {n}}\rfloor +1$

Bitenkénti műveletek használata

Ha *a szorzást <<jelenti, balra eltolást és >>jobbra logikai eltolást jelent, akkor a rekurzív algoritmus bármely természetes szám egész négyzetgyökének meghatározására a következő:

függvény integerSqrt(n): ha n < 0: hiba "integerSqrt csak nem negatív bemenettel működik" különben, ha n < 2: vissza n más: smallCandidate = integerSqrt(n >> 2) << 1 nagyJelölt = kicsiJelölt + 1 if largeCandidate*largeCandidate > n: return smallCandidate más: vissza nagyJelölt

Vagy iteráció rekurzió helyett:

függvény integerSqrt(n): ha n < 0: hiba "integerSqrt csak nem negatív bemenettel működik" # Keresse meg a legnagyobb eltolódást. műszak = 2 nShifted = n >> eltolás míg nShifted ≠ 0 és nShifted ≠ n: shift = shift + 2 nShifted = n >> eltolás műszak = váltás - 2 # Keresse meg az eredmény számjegyeit. eredmény = 0 miközben shift ≥ 0: eredmény = eredmény << 1 jelöltEredmény = eredmény + 1 ha jelöltEredmény*jelöltEredmény ≤ n >> műszak: eredmény = jelöltEredmény műszak = váltás - 2 vissza az eredményt

Számítási terület

Bár a legtöbb érték esetében irracionális szám , a sorozat csak racionális tagokat tartalmaz, ha racionális. Így ezzel a módszerrel nem szükséges kilépni a racionális számok mezőjéből a kiszámításához , aminek van némi elméleti előnye. ${\sqrt {n}}$ $n$ $\{x_{k}\}$ $x_0$ ${\mbox{isqrt}}(n)$

Stop Criteria

Megmutatható, hogy melyik a legnagyobb szám a leállási kritériumhoz $c=1$

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

amely biztosítja, hogy a fenti algoritmusban. $\lfloor x_{k+1}\rfloor =\lfloor {\sqrt {n))\rfloor$

Azokban az alkalmazásokban, amelyek nem racionális formátumokat használnak (például lebegőpontos), a leállítási állandót egynél kisebbre kell választani a kerekítési hibák elkerülése érdekében.

Lásd még

A négyzetgyök kiszámításának módszerei

Jegyzetek

↑ A módszert néha "babiloni"-nak is nevezik
↑ Fred Akalin, Computing the Integer Square Root , 2014
↑ SG Johnson, MIT Course 18.335, Square Roots via Newton's Method , 2015. február 4.
↑ Henry Cohen. Számítási algebrai számelmélet tanfolyam. - Berlin, Heidelberg, New York: Springer, 1996. - T. 138. - S. 38-49. — (Matematika érettségi szövegei). — ISBN 3-540-55640-0 .

Linkek

A négyzetgyök algoritmus geometriai nézete

Számelméleti algoritmusok
Egyszerűség tesztek	Molnár Miller – Rabin Luca - Lemaire pepina Agrawala – Kayala – Szászország Nightingale - Strassen
Prímszámok keresése	Iteráció osztók felett Eratoszthenész szita Atkin szitája Szita Sundarama
Faktorizáció	Iteráció osztók felett Fermat módszer p −1 Pollard-módszer Pollard ρ-algoritmusa Lehmann módszer Elliptikus görbe módszer (Lenstra-algoritmus) Dixon algoritmusa Négyzet alakú szita
Diszkrét logaritmus	Gelfond-Shanks algoritmus Polig-Hellman algoritmus Pollard ρ-módszere Pollard kenguru algoritmusa Adleman algoritmusa COS algoritmus
GCD keresése	Euklidész algoritmusa Speciális algoritmus Bináris algoritmus
Modulo aritmetika	Montgomery algoritmusa Kínai maradék tétel
Számok szorzása és osztása	Karatsuba algoritmus Toom-Cook algoritmus Schönhage-Strassen algoritmus Führer algoritmus Harvey-van der Hoeven algoritmus Burnickel-Ziegler algoritmus
A négyzetgyök kiszámítása	Tonelli-Shanks algoritmus Berlekamp-Rabin algoritmus