Celá odmocnina

Celá odmocnina (isqrt) přirozeného čísla n je kladné číslo m , které se rovná největšímu celému číslu menšímu nebo rovnému druhé odmocnině z n ,

{\mbox{isqrt}}(n)=\lpodlaží {\sqrt {n}}\rpodlaží .

Například od a . ${\mbox{isqrt}}(27)=5$ $5^{2}=25<27$ $6^{2}=36>27$

Algoritmus

Jedním ze způsobů výpočtu a je použít Newtonovu metodu k nalezení řešení rovnice pomocí iteračního vzorce [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.

Posloupnost konverguje kvadraticky k [3 ] . Lze dokázat, že pokud je zvolena jako výchozí hodnota, lze okamžitě přestat $\{x_{k}\}$ ${\sqrt {n}}$ $k\to \infty$ $x_{0}=n$

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

abychom to zajistili $\lfloor x_{k+1}\rfloor =\lfloor {\sqrt {n))\rfloor .$

Použití pouze celočíselného dělení

Pro výpočet pro velmi velká celá čísla n můžete použít podílové dělení se zbytkem v obou operacích dělení. Výhodou je použití pouze celých čísel pro každou mezihodnotu, což osvobozuje od používání reprezentace čísel jako čísel s pohyblivou řádovou čárkou . To je ekvivalentní použití iteračního vzorce $\lpodlaží {\sqrt {n}} \rpodlaží$

{x}_{k+1}=\left\lpatro {\frac {1}{2}}\left(x_{k}+\left\lpatro {\frac {n}{x_{k} }}\vpravo\rpodlaží \vpravo)\vpravo\rpodlaží ,\quad k\geq 0,\quad x_{0}>0,\quad x_{0}\in \mathbb {Z} .

Na základě toho, že

\left\lpatro {\frac {1}{2}}\left(x_{k}+\left\lpatro {\frac {n}{x_{k))}\right\rfloor \right)\ vpravo\rpatro =\left\lpatro {\frac {1}{2}}\left(x_{k}+{\frac {n}{x_{k))}\vpravo)\pravo\rpatro ,

lze ukázat, že sekvence dosáhne v konečném počtu iterací [4] . $\lpodlaží {\sqrt {n}} \rpodlaží$

Nebude to však nutně pevný bod výše uvedeného iteračního vzorce. Jeden může ukázat, co bude pevným bodem tehdy a jen tehdy , když to není dokonalý čtverec. Jestliže je dokonalý čtverec, posloupnost nekonverguje, ale jde do cyklu délky dvě, střídavě se mění a . K zastavení práce stačí zkontrolovat, že buď sekvence konverguje (opakování předchozí hodnoty), nebo že další hodnota je přesně o jednu větší než aktuální, v druhém případě se nová hodnota zahodí. $\lpodlaží {\sqrt {n}} \rpodlaží$ $\lpodlaží {\sqrt {n}} \rpodlaží$ $n+1$ $n+1$ $\lpodlaží {\sqrt {n}} \rpodlaží$ $\lfloor {\sqrt {n}}\rfloor +1$

Použití bitových operací

Pokud *znamená násobit, <<znamená posun doleva a znamená >>logický posun doprava, rekurzivní algoritmus pro nalezení celé druhé odmocniny libovolného přirozeného čísla je následující:

funkce integerSqrt(n): pokud n < 0: chyba "integerSqrt funguje pouze s nezáporným vstupem" jinak pokud n < 2: vrátit n jiný: smallCandidate = integerSqrt(n >> 2) << 1 velký Kandidát = malý Kandidát + 1 if largeCandidate*largeCandidate > n: vrátit malý Kandidát jiný: vrátit velkýKandidát

Nebo iterace místo rekurze:

funkce integerSqrt(n): pokud n < 0: chyba "integerSqrt funguje pouze s nezáporným vstupem" # Najděte největší posun. posun = 2 nPosunuto = n >> posun zatímco nPosunuto ≠ 0 a nPosunuto ≠ n: posun = posun + 2 nPosunuto = n >> posun posun = posun - 2 # Najděte číslice výsledku. výsledek = 0 zatímco posun ≥ 0: výsledek = výsledek << 1 kandidátVýsledek = výsledek + 1 pokud kandidátResult*candidateResult ≤ n >> posun: výsledek = kandidátVýsledek posun = posun - 2 vrátit výsledek

Výpočetní oblast

Ačkoli je pro většinu hodnot iracionální číslo , posloupnost obsahuje pouze racionální členy, je-li racionální. Při použití této metody tedy není nutné jít mimo obor racionálních čísel, abychom mohli počítat , což má určitou teoretickou výhodu. ${\sqrt {n}}$ $n$ $\{x_{k}\}$ $x_0$ ${\mbox{isqrt}}(n)$

Kritéria zastavení

Lze ukázat, které je největší číslo pro kritérium zastavení $c=1$

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

což zajišťuje, že ve výše uvedeném algoritmu. $\lfloor x_{k+1}\rfloor =\lfloor {\sqrt {n))\rfloor$

V aplikacích, které používají jiné formáty než racionální (například s plovoucí desetinnou čárkou), by měla být koncová konstanta zvolena menší než jedna, aby se předešlo chybám při zaokrouhlování.

Viz také

Metody výpočtu odmocnin

Poznámky

↑ Metoda se někdy nazývá „babylonská“
↑ Fred Akalin, Computing the Integer Square Root , 2014
↑ SG Johnson, kurz MIT 18.335, druhé odmocniny pomocí Newtonovy metody , 4. února 2015
↑ Henry Cohen. Kurz výpočetní algebraické teorie čísel. - Berlín, Heidelberg, New York: Springer, 1996. - T. 138. - S. 38-49. — (Absolventské texty z matematiky). — ISBN 3-540-55640-0 .

Odkazy

Geometrický pohled na algoritmus druhé odmocniny

Číselné teoretické algoritmy
Testy jednoduchosti	Mlynář Miller - Rabin Luca - Lemaire pepina Agravala - Kayala - Sasko Slavík - Strassen
Hledání prvočísel	Iterace přes dělitele Eratosthenovo síto Atkinovo síto Síto Sundarama
Faktorizace	Iterace přes dělitele Fermatova metoda p −1 Pollardova metoda Pollardův ρ-algoritmus Lehmannova metoda Metoda eliptické křivky (Lenstrův algoritmus) Dixonův algoritmus Čtvercové síto
Diskrétní logaritmus	Gelfond-Shanksův algoritmus Polig-Hellmanův algoritmus Pollardova ρ-metoda Pollardův algoritmus klokana Adlemanův algoritmus COS algoritmus
Hledání GCD	Euklidův algoritmus Pokročilý algoritmus Binární algoritmus
Modulová aritmetika	Montgomeryho algoritmus Čínská věta o zbytku
Násobení a dělení čísel	Algoritmus Karatsuba Toom-Cookův algoritmus Schönhage-Strassenův algoritmus Fuhrerův algoritmus Algoritmus Harvey-van der Hoeven Burnickel-Zieglerův algoritmus
Výpočet druhé odmocniny	Tonelli-Shanksův algoritmus Algoritmus Berlekamp-Rabin