Kokonaisluvun neliöjuuri

Luonnollisen luvun n kokonaisluvun neliöjuuri (isqrt) on positiivinen luku m , joka on yhtä suuri kuin suurin kokonaisluku, joka on pienempi tai yhtä suuri kuin n : n neliöjuuri ,

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

Esimerkiksi vuodesta ja . ${\mbox{isqrt}}(27)=5$ $5^{2}=25<27$ $6^{2}=36>27$

Algoritmi

Yksi tapa laskea ja on käyttää Newtonin menetelmää yhtälön ratkaisun löytämiseen iteratiivisen kaavan [1] [2] avulla. ${\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.

Sekvenssi konvergoi neliöllisesti kohtaan [ 3 ] . Voidaan todistaa, että jos aloitusarvoksi valitaan, voidaan lopettaa heti $\{x_{k}\}$ ${\sqrt {n}}$ $k\to \infty$ $x_{0}=n$

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

varmistaakseen $\lfloor x_{k+1}\rfloor =\lfloor {\sqrt {n))\rfloor .$

Käyttämällä vain kokonaislukujakoa

Jos haluat laskea erittäin suuria kokonaislukuja n , voit käyttää osamäärän jakoa jäännöksellä molemmissa jakooperaatioissa. Etuna on vain kokonaislukujen käyttö kullekin väliarvolle, mikä vapauttaa lukujen esittämisen liukulukuina . Tämä vastaa iteratiivisen kaavan käyttöä $\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} .

Perustuu siihen tosiasiaan, että

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

voidaan osoittaa, että sekvenssi saavuttaa äärellisen määrän iteraatioita [4] . $\lfloor {\sqrt {n}}\rfloor$

Se ei kuitenkaan välttämättä ole yllä olevan iteratiivisen kaavan kiinteä piste . Voidaan näyttää, mikä on kiinteä piste, jos ja vain jos se ei ole täydellinen neliö. Jos on täydellinen neliö, sekvenssi ei lähenty, vaan menee sykliin, jonka pituus on kaksi, vuorotellen muuttuen ja . Toiminnan lopettamiseksi riittää, että tarkistetaan, että sekvenssi konvergoi (toistaa edellisen arvon) tai että seuraava arvo on täsmälleen yhtä suurempi kuin nykyinen, jälkimmäisessä tapauksessa uusi arvo hylätään. $\lfloor {\sqrt {n}}\rfloor$ $\lfloor {\sqrt {n}}\rfloor$ $n+1$ $n+1$ $\lfloor {\sqrt {n}}\rfloor$ $\lfloor {\sqrt {n}}\rfloor +1$

Bittikohtaisten operaatioiden käyttö

Jos *tarkoittaa kertoa, <<tarkoittaa siirtoa vasemmalle ja tarkoittaa >>loogista siirtoa oikealle, rekursiivinen algoritmi minkä tahansa luonnollisen luvun kokonaisluvun neliöjuuren löytämiseksi on seuraava:

funktio integerSqrt(n): jos n < 0: virhe "integerSqrt toimii vain ei-negatiivisen syötteen kanssa" muuten jos n < 2: paluu n muu: smallCandidate = kokonaislukuSqrt(n >> 2) << 1 isoEhdokas = pieniEhdokas + 1 jos suuriEhdokas*suuriEhdokas > n: palauta pieniEhdokas muu: palauta suuriEhdokas

Tai iterointi rekursion sijaan:

funktio integerSqrt(n): jos n < 0: virhe "integerSqrt toimii vain ei-negatiivisen syötteen kanssa" # Etsi suurin muutos. vaihto = 2 nSiirretty = n >> siirto kun taas nSiirretty ≠ 0 ja nSiirtynyt ≠ n: vaihto = vaihto + 2 nSiirretty = n >> siirto vaihto = vaihto - 2 # Etsi tuloksen numerot. tulos = 0 kun vaihto ≥ 0: tulos = tulos << 1 ehdokasTulos = tulos + 1 jos ehdokasTulos*ehdokasTulos ≤ n >> vaihto: tulos = ehdokasTulos vaihto = vaihto - 2 palauttaa tuloksen

Laskennallinen alue

Vaikka se on irrationaalinen luku useimmille arvoille , sekvenssi sisältää vain rationaalisia jäseniä, jos se on rationaalinen. Näin ollen tätä menetelmää käytettäessä ei tarvitse mennä rationaalisten lukujen kentän ulkopuolelle laskeakseen , jolla on teoreettista etua. ${\sqrt {n}}$ $n$ $\{x_{k}\}$ $x_0$ ${\mbox{isqrt}}(n)$

Stop Criteria

Voidaan näyttää, mikä on pysäytyskriteerin suurin luku $c = 1$

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

mikä varmistaa, että yllä olevassa algoritmissa. $\lfloor x_{k+1}\rfloor =\lfloor {\sqrt {n))\rfloor$

Sovelluksissa, jotka käyttävät muita muotoja kuin rationaaleja (esimerkiksi liukulukua), pysäytysvakio tulee valita pienemmäksi kuin yksi pyöristysvirheiden välttämiseksi.

Katso myös

Neliöjuurien laskentamenetelmät

Muistiinpanot

↑ Menetelmää kutsutaan joskus "babylonialaiseksi"
↑ Fred Akalin, Computing the Integer Square Root , 2014
↑ SG Johnson, MIT Course 18.335, Square Roots via Newton's Method , 4. helmikuuta 2015
↑ Henry Cohen. Laskennallisen algebrallisen lukuteorian kurssi. - Berliini, Heidelberg, New York: Springer, 1996. - T. 138. - S. 38-49. — (Matematiikan tutkinnon tekstit). — ISBN 3-540-55640-0 .

Linkit

Geometrinen näkymä neliöjuurialgoritmista

Lukuteoreettiset algoritmit
Yksinkertaisuustestit	Miller Miller - Rabin Luca - Lemaire pepina Agrawala - Kayala - Saksi Nightingale - Strassen
Alkulukujen löytäminen	Iterointi jakajien yli Eratosthenesin seula Atkinin seula Seula Sundarama
Faktorisointi	Iterointi jakajien yli Fermat menetelmä p −1 Pollardin menetelmä Pollardin ρ-algoritmi Lehmannin menetelmä Elliptisen käyrän menetelmä (Lenstran algoritmi) Dixonin algoritmi Neliömäinen seula
Diskreetti logaritmi	Gelfond-Shanks -algoritmi Polig-Hellman-algoritmi Pollardin ρ-menetelmä Pollardin kenguru-algoritmi Adlemanin algoritmi COS-algoritmi
GCD:n löytäminen	Eukleideen algoritmi Kehittynyt algoritmi Binäärinen algoritmi
Modulo-aritmetiikka	Montgomeryn algoritmi Kiinan jäännöslause
Lukujen kerto- ja jakolasku	Karatsuba-algoritmi Toom-Cook-algoritmi Schönhage-Strassen-algoritmi Fuhrer-algoritmi Harvey-van der Hoeven-algoritmi Burnickel-Ziegler-algoritmi
Neliöjuuren laskeminen	Tonelli-Shanks-algoritmi Berlekamp-Rabin-algoritmi