이동 n번째 루트 알고리즘

이 글에는 출처가 없다 신뢰할 수 있는 출처에 인용문을 추가하여 이 기사를 개선할 수 있도록 도와주십시오. 공급되지 않은 재료는 도전하여 제거할 수 있다. 출처 찾기: "n번째 루트 알고리즘 변경" – 뉴스 · 신문 · 책 · 학자 · JSTOR (2010년 5월) (이 템플릿 메시지를 제거하는 방법과 시기 학습)

이동 n번째 루트 알고리즘은 가장 유의한 것부터 시작하여 라디칸드의 n자리로 이동하여 반복적으로 진행되며 각 반복에 긴 분할과 유사한 방식으로 한 자리수의 루트를 생성하는 양의 실수의 n번째 루트를 추출하는 알고리즘이다.

알고리즘.

표기법

B를 당신이 사용하고 있는 숫자 시스템의 기초가 되게 하고, n을 추출할 뿌리의 정도가 되게 하라.$x{\displaystyle }$ ${\displaystyle x}$을(를) 지금까지 처리된 radicand로 하고$$ $y{\displaystyle }$ ${\displaystyle y}$을(를) 지금까지 추출한 루트로 하며$$ $r{\displaystyle }$ ${\displaystyle r}$을(를) 나머지 루트로 한다$$.$\alpha {\displaystyle }$ ${\displaystyle \alpha}$을(를) 라디칸드의 $다음{\displaystyle }$ n ${\displaystyle n}$자리로$$ 하고$$ $\beta {\displaystyle }$ ${\displaystyle \beta}$을(를) 루트의 다음 자릿수로 한다.$x{\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$ ${\$ x$'}$을(를) 다음 반복에 $대한$ x ${\displaystyle$ $x$$}$의 새 값으로 하고$$, $y{\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$ ${\displaystyle$ $y$$'}$을(를) 다음 반복에 $대한$$$ $r{\displaystyle }$ ${\displaystyle r}$의 새 값으로 한다$$.이것들은 모두 정수다.

불변제

각 반복 시 불변 y ${\displaystyle n^{}}$+ ${\displaystyle r}$= ${\displaystyle x}$ ${\displaystyle$ y$^{n}+r=x}$가 유지된다.불변성+ 1) > ${\displaystyle (y+1)^{n}>x}$이(가) 유지된다.따라서 $y{\displaystyle }$ ${\displaystyle y}$은(는) $x{\displaystyle }$ ${\displaystyle x}$의 n번째 루트보다 작거나 같은 최대 정수이고$,$ $r{\displaystyle }$ ${\displaystyle r}$은(는) 나머지다.

초기화

$x{\displaystyle }$${\displaystyle }$, ${\displaystyle y}$ ${\displaystyle x,y}$및 r ${\displaystyle r}$의 초기 값은 0이어야 한다$$.첫 번째 반복에 대한$$ $\alpha {\displaystyle }$ ${\displaystyle \alpha }$ 값은 radicand의 $n{\displaystyle }$ ${\displaystyle n}$자리의$$ 가장 유의한 정렬 블록이어야 한다.$n{\displaystyle }$ ${\displaystyle n}$자리의$$ 정렬 블록은 소수점이 블록 사이에 오도록 정렬된 자릿수 블록을 의미한다.예를 들어 123.4에서 두 자리수의 가장 유의한 정렬 블록은 01이고, 다음으로 유의한 블록은 23이며, 세 번째로 유의한 블록은 40이다.

메인 루프

On each iteration we shift in ${\displaystyle n}$ digits of the radicand, so we have ${\displaystyle x'=B^{n}x+\alpha }$ and we produce one digit of the root, so we have ${\displaystyle y'=By+\beta }$. The first invariant implies that ${\displaystyle r'=x'-y'$$^{n$ 위에서 설명한 불변성이 유지되도록$$ $\beta {\displaystyle }$ ${\displaystyle \beta }$을(를) 선택하고자 한다.아래에서 증명할 수 있듯이, 언제나 그러한 선택은 정확히 한 가지인 것으로 밝혀졌다.

요약하면, 각 반복에 대해:

1. $\alpha {\displaystyle }$ ${\displaystyle \alpha }$을(를) 반지름에서 다음 정렬된 자릿수 블록으로$$ 두십시오.
2. $let{\displaystyle {}^{}}$ x ${\displaystyle {\prime }^{}}$= ${\displaystyle {}^{}}$ ${\displaystyle n^{}}$ ${\displaystyle {}^{}}$ +${\displaystyle \alpha }$ ${\displaystyle x'=B^{n}x+\alpha }$
3. $\beta {\displaystyle }$ ${\displaystyle \beta }$을(를${\displaystyle )}$ 가장 큰 $\beta {\displaystyle }$ ${\displaystyle \$${\displaystyle \mathrm{beta}}$ ${\displaystyle {}^{}}$이(가) 되도록 두십시오$+\beta$ ) n ${\displaystyle {}^{}}$ ${\displaystyle {}^{}}$ ${\displaystyle n^{}}$ ${\displaystyle {}^{}}$ {\$displaystystyle(By$+)^{$n}\lq$ B$^{n}x+\alpha }$x+\alpha }}}}}}}}}}}}.
4. $y{\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$= ${\displaystyle B}$ ${\displaystyle y}$+ ${\displaystyle \beta }$ ${\displaystyle$ y$'=By+\beta }$
5. r${\displaystyle {}^{}}r{\displaystyle {}^{}}$= ${\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$- ${\displaystyle {}^{}}$ ${\displaystyle {\prime n}^{}}$ ${\$

$이제{\displaystyle }$x = ${\displaystyle {}^{}n}$ + r$${\$displaystyle x=y^{n}+r},$ 따라서 조건$.$

${\displaystyle (By+\beta )^{n}\leq B^{n}x+\alpha }$

와 같다

${\displaystyle (By+\beta )^{n}-B^{n}y^{n}\leq B^{n}r+\alpha }}$

그리고

${\displaystyle r'=x'-y'^{n}=B^{n}x+\알파 -(By+\beta )^{n}}}$

와 같다

${\displaystyle r'=B^{n}r+\alpha -(By+\beta )^{n}-B^{n}y^{n}}}}$

따라서, 우리는 이후 r))− yn{\displaystyle r=x-y^{n}}과 x의<>(y+1)n{\displaystyle x<,{(y+1)^ n}}, r<>(y+1)n− x{\displaystyle)}yn{\displaystyle r<,(y+1)^{n}-y^{n}},<>nyn− 1+O(yn− 2){\displaystyle r<, ny^{n-1}+O(y^{n이 필요하지 않는다.2})},,<>N)n− 1n+O()n− 2n){\displaystyle r<, nx^{{n-1}\over n}+O(nx^{{n-2}\over})}, 그렇게 사용하여 r{r\displaystyle}대신 낙하{\displaystyle)}우리가 절약되는 시간과 공간에의 1/n{n\displaystyle}. 또한, Bn이 n{\displaystyle B^{n}y^{n}}우리는을 뺀다면의 새로운 시험이다. 없어$({\displaystyle B}$ ${\displaystyle y}$+ ${\displaystyle \beta {}^{}}$)${\displaystyle n^{}}$ ${\$에 있는 것을 ncels하기 때문에 이제$$ 우리가 평가해야 $할{\displaystyle }$ y$${\$displaysty y}$의 최고 ${\displaystyle {힘}^{}}$은 y ${\$$^{$$n}$가 아니라$$ ${\displaystyle {\mathrm{y}}^{}}$- ${\displaystyle 1^{}}$ ${\$ y^{$n-1}$이다$.$

요약

1. $r{\displaystyle }$ ${\displaystyle r}$ 및$$ $y{\displaystyle }$ ${\displaystyle y}$을(를) 0으로$$ 초기화하십시오.
2. 원하는 정밀도를 얻을 때까지 반복하십시오.
   1. $\alpha {\displaystyle }$ ${\displaystyle \alpha }$을(를) 반지름에서 다음 정렬된 자릿수 블록으로$$ 두십시오.
   2. $\beta {\displaystyle }$ ${\displaystyle \beta }$을(를${\displaystyle )}$ 가장 큰 $\beta {\displaystyle }$ ${\displaystyle \beta$${\displaystyle {}^{}}$$}$이(가) 되도록$By+\beta)^{n^{n$}-$B^{n}r+\alpha).$
   3. $y{\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$= ${\displaystyle B}$ ${\displaystyle y}$+ ${\displaystyle \beta }$ ${\displaystyle y'=By+\beta }$을(를) 놓으십시오$.$
   4. $r{\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$= ${\displaystyle {}^{}}$ ${\displaystyle {}^{}}$ r${\displaystyle }$+ ${\displaystyle \alpha }$-${\displaystyle }$(${\displaystyle }$(${\displaystyle B}$ ${\displaystyle y}$+ ${\displaystyle \beta {}^{}}$) n${\displaystyle {}^{}}$- ${\displaystyle B^{}}$ ${\displaystyle {}^{}}$ ${\displaystyle y^{}}$ n${\displaystyle {}^{}}$)${\displaystyle }$. ${\displaystyle r'=B^{n}r+\alpha -$ $(By+\beta )^{n}-B^{n}y$^{n}y$^{n}$y^{n}}}.$}$
   5. $y{\displaystyle }$ ${\displaystyle \leftarrow }$ ${\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$ ${\$ y$\leftarrow$ y$'}$ 및$$ $r{\displaystyle }$ ${\displaystyle \leftarrow }$ ${\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$. ${\displaystyle$ r$\leftarrow r'$을 할당하십시오.$}$
3. Y{이\displaystyle}은 가장 큰 정수와 yn<>)Bk{\displaystyle y^{n}<, xB^{k}}, y n+r=-1Bk{\displaystyle y^{n}+r=xB^{k}}, k{k\displaystyle}은 숫자의 자릿수 근호 속의 수 후 소수 점이 돼 온 소비된 음수가 알고리즘을 가지고 있다.not는 아직 소수점에 도달했다.)

종이와 펜슬 n번째 뿌리

위에서 언급한 바와 같이, 이 알고리즘은 긴 분할과 유사하며, 다음과 같은 표기법을 사용한다.

1.44224—————————————————————— 즉 3연료 000000000000\/ 1=3(10×0)2×1 +3(10×0)×12 +13 — 20001744년=3(10×1)2×4 +3(10×1)×42 +43 ————— 256만 241명 984년=3(10×14)2×4 +3(10×14)×42 +43 ——————— 14016000입니다.    12458 888            = 3(10×144)2×2   +3(10×144)×22   +23         ——————————          1 557 112 000          1 247 791 448        = 3(10×1442)2×2  +3(10×1442)×22  +23          —————————————            309 320 552 000            249 599 823 424    = 3(10×14422)2×4 +3(10×14422)×42 +43            ———————————————             59 720 728 576

Note that after the first iteration or two the leading term dominates the ${\displaystyle (By+\beta )^{n}-B^{n}y^{n}}$, so we can get an often correct first guess at ${\displaystyle \beta }$ by dividing ${\displaystyle B^{n}r+\alpha }$ by ${\display$$스타일 nB^{n-1}y^{n-1$}y^{n-1$}$.

퍼포먼스

각 반복에서 가장 많은 시간이 소요되는 작업은 $\beta {\displaystyle }$ ${\displaystyle \beta }$을(를) 선택하는 것이다$.$ $우리$는 B ${\displaystyle B}$의 가능한 값이 있기 때문에 $O{\displaystyle (\mathrm{로그}}$ ${\displaystyle }$ ${\displaystyle (B}$ ${\displaystyle )}$ ${\displaystystyle O(\log(B))}$을(를) $비교$해서$β$ {\displaystystytype $\$displaystyption $stytype$ \displaystytype B}을 찾을 수 있다.Each comparison will require evaluating ${\displaystyle (By+\beta )^{n}-B^{n}y^{n}}$. In the kth iteration, ${\displaystyle y}$ has ${\displaystyle k}$ digits, and the polynomial can be evaluated with ${\displaystyle 2n-4}$ multiplications of up to ${\displa$$ystyle k(n-1)}$ digits and ${\displaystyle n-2}$ additions of up to ${\displaystyle k(n-1)}$ digits, once we know the powers of ${\displaystyle y}$ and ${\displaystyle \beta }$ up through ${\displaystyle n-1}$ for ${\displaystyle y}$ and ${\displaystyle n}$ for ${\dis$$playstyle \cHB }$ .$$β {\$displaystyle$\cHB}의 범위가 제한되어 있으므로$$β$$ ${\\displaystyle \cHB }$의 힘을 일정한 시간에 얻을 수 있다.$n{\displaystyle }$ -${\displaystyle 2}$ ${\displaystyle n-2}$ 배수로$$ 최대$$ $k{\displaystyle }$( ${\displaystyle n}$- ${\displaystyle 1}$ )${\displaystyle k(n-1)}$자리까지$$ y ${\displaystyle y}$의 힘을 얻을 수 있다.Assuming ${\displaystyle n}$-digit multiplication takes time ${\displaystyle O(n^{2})}$ and addition takes time ${\displaystyle O(n)}$, we take time ${\displaystyle O(k^{2}n^{2})}$ for each comparison, or time ${\displaystyle O(k^{2}n^{2}\$$log(B))}$ to pick ${\displaystyle \beta }$. The remainder of the algorithm is addition and subtraction that takes time ${\displaystyle O(k)}$, so each iteration takes ${\displaystyle O(k^{2}n^{2}\log(B))}$. For all ${\displaystyle k}$ digits, we need time ${\displaystyle O(k^3{n}^2}$${\displaystyle {}^{}\mathrm{로그}}$log${\displaystyle }$(${\displaystyle B}$)${\displaystyle O(k^{3}n^{2}\log(B)}}$.

필요한 유일한 내부 $스토리지$는 r$${\$displaystyle r}$이고$,$ 이 값은 k번째 반복에서 $O{\displaystyle (k}$ ${\displaystyle )}$ ${\displaystyle O(k)}$자리$$ 입니다.이 알고리즘에 경계 메모리 사용이 없다는 것은 더 기본적인 산술 알고리즘과는 달리 정신적으로 계산할 수 있는 자릿수에 상한선을 둔다.불행히도 주기적인 입력을 가진 경계 메모리 상태 기계는 주기적인 출력만 생산할 수 있기 때문에 이성적인 것으로부터 비합리적인 숫자를 계산할 수 있는 그런 알고리즘이 없고 따라서 경계 메모리 루트 추출 알고리즘도 없다.

베이스를 증가시키면 $\beta {\displaystyle }$ ${\displaystyle \$${\displaystyle \mathrm{beta}}$ $}$을(를${\displaystyle )}$ O${\displaystyle (}$로그 $increases$ ( ) $displaystyle O(\log(B$의 계수만큼 선택하는데 필요한 시간이 증가하지만$,$ 동일한 팩터에 의해 주어진 정밀도를 달성하는데 필요한 자릿수가 감소하고 알고리즘이 자릿수에 입방 시간이므로 베이스를 증가시키면 o가 된다는 점에 유의한다.$Verall{\displaystyle }$ speedup of O${\displaystyle }$( ${\displaystyle {\log }^{}}$ ${\displaystyle {2\mathrm{}}^{}}$ ${\displaystyle {}^{}}$ ${\displaystyle (B}$ ${\displaystyle$ O$(\log ^{2}(B$ 베이스가 radicand보다 크면 알고리즘이 바이너리 검색으로 변질되기 때문에 이 알고리즘은 항상 훨씬 단순한 바이너리 검색에 의해 능가되고 동일한 메모리 복잡성을 가지고 있기 때문에 컴퓨터와의 루트를 계산하는 데 유용하지 않다..

예

2의 제곱근(이진수)

1. 0  1  1  0  1     ------------------ _  / 10.00 00 00 00 00     1  \/   1                  + 1      -----               ----       1 00                100          0               +  0      --------            -----       1 00 00             1001         10 01            +   1      -----------         ------          1 11 00          101011 01 01 + 1 -------- 11 00 101100 0 + 0 ------------ 1 11 00 1011001 1 01 10 01 - 나머지 1 01 11

3의 제곱근

1. 7  3  2  0  5     ---------------------- _  / 3.00 00 00 00 00  \/  1 = 20×0×1+1^2      -      2 00      1 89 = 20×1×7+7^2 (27 x 7)      ----        11 00        10 29 = 20×17×3+3^2  (343 x 3)        -----           71 00           69 24 = 20×173×2+2^2 (3462 x 2)           -----            1 76 00                  0 = 20×1732×0+0^2 (34640 x0) -------- 1 76 00 00 1 73 20 25 = 20×17320×5+5^2(346405 x 5) --------------- 2 79 75

큐브 루트 5

1.  7   0   9   9   7     ---------------------- _ 3/ 5. 000 000 000 000 000  \/  1 = 300×(0^2)×1+30×0×(1^2)+1^3      -      4 000      3 913 = 300×(1^2)×7+30×1×(7^2)+7^3      -----         87 000              0 = 300×(17^2×0+30×17×(0^2)+0^3        -------         87 000 000         78 443 829 = 300×(170^2)×9+30×170×(9^2)+9^3         ----------          8 556 171 000          7 889 992 299 = 300×(1709^2)×9+30×1709×(9^2)+9^3          -------------            666 178 701 000            614 014 317 973 = 300×(17099^2)×7+30×17099×(7^2)+7^3            ---------------             52 164 383 027

7의 네 번째 뿌리

1.   6    2    6    5    7     --------------------------- _ 4/ 7.0000 0000 0000 0000 0000  \/  1 = 4000×(0^3)×1+600×(0^2)×(1^2)+40×0×(1^3)+1^4      -      6 0000      5 5536 = 4000×(1^3)×6+600×(1^2)×(6^2)+40×1×(6^3)+6^4      ------        4464 0000        3338 7536 = 4000×(16^3)×2+600×(16^2)×(2^2)+40×16×(2^3)+2^4        ---------        11252464 0000        1026 0494 3376 = 4000×(162^3)×6+600×(162^2)×(6^2)+40×162×(6^3)+6^4        --------------          99 1969 6624 0000          86 0185 1379 0625 = 4000×(1626^3)×5+600×(1626^2)×(5^2)+          -----------------   40×1626×(5^3)+5^4          13 1784 5244 9375 0000          12 0489 2414 6927 3201 = 4000×(16265^3)×7+600×(16265^2)×(7^2)+----------------------   40×16265×(7^3)+7^4           1 1295 2830 2447 6799

참고 항목

• 제곱근 계산 방법
• n번째 루트 알고리즘

외부 링크

• 제곱근 알고리즘이 "홈 스쿨 수학"을 하는 이유.또한 네모난 뿌리를 위한 긴 분할형 연필과 종이 방법의 예를 보여주는 관련 페이지.
• 두 "중간"의 제곱근에 대한 반사.C++ 구현의 예와 함께.