Celočíselná odmocnina - Integer square root - Wikipedia

v teorie čísel, druhá odmocnina (isqrt) z kladné celé číslo n je kladné celé číslo m který je největší celé číslo menší nebo rovno do odmocnina z n,

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

Například, ${ displaystyle { mbox {isqrt}} (27) = 5}$ protože ${ displaystyle 5 cdot 5 = 25 leq 27}$ a ${ displaystyle 6 cdot 6 = 36> 27}$.

Algoritmus využívající Newtonovu metodu

Jeden způsob výpočtu ${ displaystyle { sqrt {n}}}$ a ${ displaystyle { mbox {isqrt}} (n)}$ je použít Newtonova metoda najít řešení pro rovnici ${ displaystyle x ^ {2} -n = 0}$, což dává iterativní vzorec

${ displaystyle {x} _ {k + 1} = { frac {1} {2}} vlevo (x_ {k} + { frac {n} {x_ {k}}} vpravo), quad k geq 0, quad x_ {0}> 0.}$

The sekvence ${ displaystyle {x_ {k} }}$ konverguje kvadraticky na ${ displaystyle { sqrt {n}}}$ tak jako ${ displaystyle k to infty}$. Je dokázáno, že pokud ${ displaystyle x_ {0} = n}$ je vybrán jako počáteční odhad, lze zastavit, jakmile

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

zajistit to ${ displaystyle lfloor x_ {k + 1} rfloor = lfloor { sqrt {n}} rfloor.}$

Používá se pouze celočíselné dělení

Pro výpočet ${ displaystyle lfloor { sqrt {n}} rfloor}$ pro velmi velká celá čísla n, lze použít podíl z Euklidovské dělení pro obě operace divize. To má tu výhodu, že se pro každou mezilehlou hodnotu používají pouze celá čísla, a proto se používá plovoucí bod reprezentace velkého počtu zbytečné. Je to ekvivalentní použití iteračního vzorce

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

Použitím skutečnosti, že

${ displaystyle 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,}$

lze ukázat, že to dosáhne ${ displaystyle lfloor { sqrt {n}} rfloor}$ v konečném počtu iterací.

Nicméně, ${ displaystyle lfloor { sqrt {n}} rfloor}$ není nutně a pevný bod výše uvedeného iteračního vzorce. Je skutečně možné ukázat, že ${ displaystyle lfloor { sqrt {n}} rfloor}$ je pevný bod právě tehdy, když ${ displaystyle n + 1}$ není dokonalý čtverec. Li ${ displaystyle n + 1}$ je dokonalý čtverec, posloupnost končí v cyklu dvou období mezi ${ displaystyle lfloor { sqrt {n}} rfloor}$ a ${ displaystyle lfloor { sqrt {n}} rfloor +1}$ místo konvergence.

Doména výpočtu

Ačkoli ${ displaystyle { sqrt {n}}}$ je iracionální pro mnoho ${ displaystyle n}$, sekvence ${ displaystyle {x_ {k} }}$ obsahuje pouze Racionální podmínky kdy ${ displaystyle x_ {0}}$ je racionální. U této metody tedy není nutné opouštět pole racionálních čísel za účelem výpočtu ${ displaystyle { mbox {isqrt}} (n)}$, což má některé teoretické výhody.

Kritérium zastavení

Dá se to dokázat ${ displaystyle c = 1}$ je největší možné číslo, pro které je kritérium zastavení

${ displaystyle | x_ {k + 1} -x_ {k} |$

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

V implementacích, které používají formáty čísel, které nemohou přesně reprezentovat všechna racionální čísla (například s plovoucí desetinnou čárkou), by měla být použita konstantní konstanta menší než jedna k ochraně před chybami zaokrouhlování.

Příklad implementace v C

// Druhá odmocnina celého číslanepodepsaný dlouho int_sqrt ( nepodepsaný dlouho s ){	nepodepsaný dlouho x0 = s >> 1;				// Počáteční odhad	// Kontrola duševního zdraví	-li ( x0 )	{		nepodepsaný dlouho x1 = ( x0 + s / x0 ) >> 1;	// Aktualizace				zatímco ( x1 < x0 )				// Tím se také zkontroluje cyklus		{			x0 = x1;			x1 = ( x0 + s / x0 ) >> 1;		}				vrátit se x0;	}	jiný	{		vrátit se s;	}}

Algoritmus číslice po číslici

Tradiční algoritmus pero a papír pro výpočet druhé odmocniny ${ displaystyle { sqrt {n}}}$ je založen na práci z míst s vyššími číslicemi na nižší a s každou novou číslicí vyberte největší, které bude stále přinášet čtverec ${ displaystyle leq n}$. Pokud se zastavíte za místem někoho, bude vypočítaným výsledkem celá druhá odmocnina.

Použití bitových operací

Pokud pracujete v základna 2 „je volba číslice zjednodušena na volbu mezi 0 („ malý kandidát “) a 1 („ velký kandidát “) a manipulace s číslicemi lze vyjádřit pomocí operací binárního posunu. S * množení, << při levém posunu a >> být logickým posunem doprava, a rekurzivní algoritmus k vyhledání celé odmocniny jakéhokoli čísla přirozené číslo je:

def integer_sqrt(n: int) -> int:    tvrdit n >= 0, "sqrt funguje pouze pro nezáporné vstupy"    -li n < 2:        vrátit se n    # Rekurzivní volání:    small_cand = integer_sqrt(n >> 2) << 1    large_cand = small_cand + 1    -li large_cand * large_cand > n:        vrátit se small_cand    jiný:        vrátit se large_cand# ekvivalentně:def integer_sqrt_iter(n: int) -> int:    tvrdit n >= 0, "sqrt funguje pouze pro nezáporné vstupy"    -li n < 2:        vrátit se n    # Najděte částku směny. Viz také [[najít první sadu]],    # shift = strop (log2 (n) * 0,5) * 2 = strop (ffs (n) * 0,5) * 2    posun = 2    zatímco (n >> posun) != 0:        posun += 2    # Odviňte smyčku nastavení bitů.    výsledek = 0    zatímco posun >= 0:        výsledek = výsledek << 1        large_cand = (            výsledek + 1        )  # Stejné jako výsledek ^ 1 (xor), protože poslední bit je vždy 0.        -li large_cand * large_cand <= n >> posun:            výsledek = large_cand        posun -= 2    vrátit se výsledek

Tradiční prezentace algoritmu digit-by-digit perem a papírem zahrnují různé optimalizace, které nejsou obsaženy ve výše uvedeném kódu, zejména trik předčtení čtverce předchozích číslic, díky kterému je obecný krok násobení zbytečný. Vidět Metody výpočtu druhé odmocniny § Woo počítadlo například.^[1]

Viz také

• Metody výpočtu druhé odmocniny

Reference

externí odkazy

• Geometrický pohled na druhou odmocninu