Rădăcină pătrată întreagă

Rădăcina pătrată întreagă (isqrt) a unui număr natural n este un număr pozitiv m , care este egal cu cel mai mare număr întreg mai mic sau egal cu rădăcina pătrată a lui n ,

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

De exemplu, din moment ce și . ${\mbox{isqrt}}(27)=5$ $5^{2}=25<27$ $6^{2}=36>27$

Algoritm

Una dintre modalitățile de a calcula și este de a folosi metoda lui Newton pentru a găsi o soluție a ecuației folosind formula iterativă [1] [2] ${\sqrt {n}}$ ${\mbox{isqrt}}(n)$ $x^{2}-n=0$

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

Secvența converge pătratic la [ 3] . Se poate dovedi că, dacă este ales ca valoare inițială, se poate opri imediat $\{x_{k}\}$ ${\sqrt {n}}$ $k\to \infty$ $x_{0}=n$

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

a se asigura ca $\lfloor x_{k+1}\rfloor =\lfloor {\sqrt {n)}\rfloor .$

Folosind doar diviziunea întregi

Pentru a calcula pentru numere întregi foarte mari n , puteți utiliza diviziunea de coeficient cu un rest în ambele operațiuni de împărțire. Avantajul este utilizarea numai a numerelor întregi pentru fiecare valoare intermediară, ceea ce eliberează utilizarea reprezentării numerelor ca numere în virgulă mobilă . Acest lucru este echivalent cu utilizarea formulei iterative $\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} .

Pe baza faptului că

\left\lfloor {\frac {1}{2}}\left(x_{k}+\left\lfloor {\frac {n}{x_{k)}}\right\rfloor \right)\ dreapta\rfloor =\left\lfloor {\frac {1}{2}}\left(x_{k}+{\frac {n}{x_{k))}\right)\right\rfloor ,

se poate arăta că şirul ajunge într-un număr finit de iteraţii [4] . $\lfloor {\sqrt {n}}\rfloor$

Cu toate acestea, nu va fi neapărat punctul fix al formulei iterative de mai sus. Se poate arăta ce va fi un punct fix dacă și numai dacă nu este un pătrat perfect. Dacă este un pătrat perfect, secvența nu converge, ci intră într-un ciclu de lungime doi, schimbându-se alternativ și . Pentru a opri funcționarea, este suficient să verificați fie că secvența converge (repetând valoarea anterioară), fie că următoarea valoare este exact cu una mai mare decât cea actuală, în acest din urmă caz noua valoare fiind aruncată. $\lfloor {\sqrt {n}}\rfloor$ $\lfloor {\sqrt {n}}\rfloor$ $n+1$ $n+1$ $\lfloor {\sqrt {n}}\rfloor$ $\lfloor {\sqrt {n}}\rfloor +1$

Folosind operații pe biți

Dacă *înseamnă înmulțire, <<înseamnă deplasare la stânga și înseamnă >>deplasare logică la dreapta, algoritmul recursiv pentru găsirea rădăcinii pătrate întregi a oricărui număr natural este următorul:

funcția integerSqrt(n): dacă n < 0: eroare „integerSqrt funcționează numai cu intrare nenegativă” altfel, dacă n < 2: întoarcere n altceva: smallCandidate = integerSqrt(n >> 2) << 1 candidat mare = candidat mic + 1 dacă candidat mare*candidat mare > n: return smallCandidate altceva: return largeCandidate

Sau iterație în loc de recursivitate:

funcția integerSqrt(n): dacă n < 0: eroare „integerSqrt funcționează numai cu intrare nenegativă” # Găsiți cea mai mare tură. deplasare = 2 n Deplasat = n >> deplasare în timp ce nShifted ≠ 0 și nShifted ≠ n: shift = shift + 2 n Deplasat = n >> deplasare shift = shift - 2 # Găsiți cifrele rezultatului. rezultat = 0 în timp ce schimbarea ≥ 0: rezultat = rezultat << 1 candidateResult = rezultat + 1 dacă candidateResult*candidateResult ≤ n >> shift: rezultat = candidateResult shift = shift - 2 returnează rezultatul

Zona de calcul

Deși este un număr irațional pentru majoritatea valorilor , secvența conține numai membri raționali dacă este rațional. Astfel, folosind această metodă, nu este necesar să ieși din câmpul numerelor raționale pentru a calcula , ceea ce are un anumit avantaj teoretic. ${\sqrt {n}}$ $n$ $\{x_{k}\}$ $x_0$ ${\mbox{isqrt}}(n)$

Criterii de oprire

Se poate arăta care este cel mai mare număr pentru criteriul de oprire $c=1$

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

ceea ce asigură că în algoritmul de mai sus. $\lfloor x_{k+1}\rfloor =\lfloor {\sqrt {n)}\rfloor$

În aplicațiile care utilizează alte formate decât cele raționale (de exemplu, virgulă mobilă), constanta de oprire trebuie aleasă să fie mai mică de unu pentru a evita erorile de rotunjire.

Vezi și

Metode de calcul al rădăcinilor pătrate

Note

↑ Metoda este uneori numită „babilonian”
^ Fred Akalin, Computing the Integer Square Root , 2014
↑ SG Johnson, MIT Curs 18.335, Square Roots via Newton's Method , 4 februarie 2015
↑ Henry Cohen. Un curs în teoria numerelor algebrice computaționale. - Berlin, Heidelberg, New York: Springer, 1996. - T. 138. - S. 38-49. — (Texte universitare de matematică). — ISBN 3-540-55640-0 .

Link -uri

O vedere geometrică a algoritmului rădăcinii pătrate

Algoritmi teoretici numerelor
Teste de simplitate	Miller Miller - Rabin Luca - Lemaire pepina Agrawala - Kayala - Saxonia Privighetoarea - Strassen
Găsirea numerelor prime	Iterarea peste divizori Sita lui Eratosthenes sita lui Atkin Sieve Sundarama
Factorizarea	Iterarea peste divizori Metoda Fermat p −1 Metoda Pollard Algoritmul ρ al lui Pollard metoda Lehmann Metoda curbei eliptice (algoritmul lui Lenstra) algoritmul lui Dixon Sita pătrată
Logaritm discret	Algoritmul Gelfond-Shanks Algoritmul Polig-Hellman Metoda ρ a lui Pollard Algoritmul Cangurului lui Pollard Algoritmul lui Adleman Algoritmul COS
Găsirea GCD	algoritmul lui Euclid Algoritm avansat Algoritm binar
Modul de aritmetică	Algoritmul lui Montgomery Teorema chineză a restului
Înmulțirea și împărțirea numerelor	Algoritmul Karatsuba Algoritmul Toom-Cook Algoritmul Schönhage-Strassen Algoritmul Fuhrer Algoritmul Harvey-van der Hoeven Algoritmul Burnickel-Ziegler
Calcularea rădăcinii pătrate	Algoritmul Tonelli-Shanks Algoritmul Berlekamp-Rabin