정수 제곱근

수 이론에서, 양의 정수 n의 정수 제곱근(isqrt)은 n의 제곱근보다 작거나 같은 최대 정수인 양의 정수 m이다.

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

예를$$ 들어 ${\displaystyle \text{isqrt}(27}$)${\displaystyle }$= ${\displaystyle 5}$ ${\displaystyle {\mbox{isqrt}(27)=5}$ 왜냐하면 ${\displaystyle 5}$⋅ 5${\displaystyle }$= ${\displaystyle 25}$ ${\displaystyle \le }$ ${\displaystyle 27}$ ${\displaystyle 5=25\leq 27}$ 및 6= > > 27 ${\displaystyle 6=36_27$

단순 알고리즘

음수가 아닌 정수 $y{\displaystyle }$ ${\displaystyle y}$의 정수 제곱근을 다음과 같이 정의할 수 있다$$.

${\displaystyle \lfloor {\sqrt {y}\mu x(x+1)^{2}_y)}$

선형 검색을 사용한 알고리즘

다음의 C-프로그램은 간단한 구현이다.

// 정수 제곱근(선형 검색 사용) 서명이 없는 인트로 isqrt( 서명이 없는 인트로 y ) {  서명이 없는 인트로 x = 1;   하는 동안에( x * x <= y )   x = x + 1;   돌아오다 x - 1; } 

이진 검색을 사용한 알고리즘

이전 알고리즘은 선형 검색을 사용하여 x ${\displaystyle x}$에 도달할$$ 때까지 모든 값을 검사하며, 여기서 x> ${\displaystyle$ x$^{2}>y$

속도 향상은 바이너리 검색을 대신 사용하여 달성된다. 다음의 C-프로그램은 실행이다.

// 정수 제곱근(이진 검색 사용) 서명이 없는 인트로 isqrt( 서명이 없는 인트로 y ) {  서명이 없는 인트로 L = 0;  서명이 없는 인트로 M;  서명이 없는 인트로 R = y + 1;      하는 동안에( L != R - 1 )     {         M = (L + R) / 2;    만일( M * M <= y )    L = M;   다른    R = M;  }      돌아오다 L; } 

숫자 예제

예를 들어, 2진수 검색을 사용하여 2000000의 정수 제곱근을 계산하면 [${\displaystyle L}$, ${\displaystyle R}$ ${\displaystyle ]}$ ${\displaystyle [L,R]}$ 시퀀스를$$ 얻는다.

${\displaystyle {\regated}>[0,2000001]\오른쪽 화살표 [0,10000]\오른쪽 화살표 [0,50000]\오른쪽 화살표 [0,2500]\오른쪽 화살표 [0,670]\오른쪽 화살표 [0,3125]\오른쪽 화살표 [0,3125]\&\오른쪽 화살표 [0,7812]\오른쪽 화살표 [0,3906]\오른쪽 화살표 [0,3906]\오른쪽 화살표 [0,3906]\오른쪽 화살표 [976,1464]\오른쪽 화살표 [976,1464]\오른쪽 화살표 [122,1464]\오른쪽 화살표 [1403,1464]\&\오른쪽 화살표 [1403,1433]\오른쪽 화살표 [1403,1418]\오른쪽 화살표 [141,1418]\오른쪽 화살표 [1414,1418]\오른쪽 화살표 [1414,1416]\오른쪽 화살표 [14,1415]\끝{arged}}}}}}$

이 계산에는 21개의 반복 단계가 필요한 반면, 선형 검색에는 1414개의 단계가 필요하다.

뉴턴의 방법을 이용한 알고리즘

$n{\displaystyle \sqrt{}}$ ${\$과 ${\displaystyle \text{isqrt}}$($){\disqrt}}$을(를$)$ 계산하는 한 가지 방법은 뉴턴의 방법의 특수한 경우인 헤론의 방법을 사용하여 $식{\displaystyle {}^{}x}$2 = ${\displaystyle 0}$ =$${\$displaysty x^{2}-n=0}$을$($를)에 대한 해결책을 찾는 것으로서$$ 반복적인 공식을 제공한다.

${\displaystyle {x}_{k+1}={\frac {1}{1}:{2}}:\좌측(x_{k}+{\frac {n}{x_{k}}\우측)\192 k\geq 0,\message x_{0}}}0}0)0.}$

$\{{\displaystyle }$ ${\displaystyle {}_{}}$ ${\displaystyle k_{}}$ ${\displaystyle \{x_{k}\}\}$ 순서는 2차적으로 $n{\displaystyle \sqrt{}}$ ${\$에 $k{\displaystyle }$→$【\displaystyle k\to \fty}$로 수렴된다$.$

정지기준

$c{\displaystyle }$= ${\displaystyle 1}$ ${\displaystyle c=1$}이$($가) 정지 기준이 될 수 있는 가장 큰 숫자임을$$ 증명할^{[citation needed]} 수 있다.

${\displaystyle x_{k+1}-x_{k} <c}$

${\displaystyle {위}_{}}$의 알고리즘에서${\displaystyle {+}_{}}$ ${\displaystyle {\mathrm{x}}_{}}$ k${\displaystyle {}_{}}$+${\displaystyle }$1 ${\displaystyle \lfloor }$ = ${\displaystyle \rfloor n\sqrt{}}$ \n ${\displaystyle \lfloor x_{k+1}\rfloor =\\sqrt{n$}\$qloor$}을$($를) 보장한다.

모든 합리적인 숫자를 정확하게 나타낼 수 없는 숫자 형식(예: 부동 소수점)을 사용하는 구현에서는 1보다 작은 정지 상수를 사용하여 반올림 오류로부터 보호해야 한다.

계산 영역

$n{\displaystyle }$ ${\$$displaystyle$ {\$sqrt{n}}$은(는) 많은 n ${\displaystyle n$${\displaystyle {}_{}}$에 대해 비합리적이지만$,$ ${\displaystyle {순서\mathrm{}}_{}}$$${${\displaystyle {xk}_{}}$} {\$displaystyle \{x_$${k}\}}}}}$은(는) 합리적 용어만$$ 포함하고 있다$$. 따라서, 이 방법으로는 이론적 이점이 있는$$${\displaystyle \text{사실}}$인${\displaystyle \mathrm{isqrt}}$(n$$){\$displaystyle {\mbox{isqrt}(n)}$를 계산하기 위해 합리적인 숫자의 필드를 벗어날 필요가 없다.

정수 분할만 사용

매우 큰 정수 n에 대한$$ $\lfloor {\displaystyle n\sqrt{}}$ ${\displaystyle \rfloor }$ ${\displaystyle \lfloor {\sqrt{n}\rfloor }$을(를) 계산하는 경우, 두 분할 작업 모두에 유클리드 분할의 몫을 사용할 수 있다. 이는 각 중간값에만 정수를 사용할 수 있는 장점이 있어 큰 숫자의 부동소수 표현을 사용할 필요가 없다. 반복식을 사용하는 것과 같다.

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

라는 사실을 이용하여

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

한정된 반복 횟수 내에서$$ $\lfloor {\displaystyle n\sqrt{}}$ $⌋{\displaystyle \lfloor{\sqrt{n}\rfloor }$에 도달한다는 것을 보여줄 수 있다.

원래 버전에서는, 한}}k에 ≥ 1{\displaystyle k\geq 1}, k>)k+1{\displaystyle{)}_{k}>, xk대리자에{)}_{k+1}};n{\displaystyle{)}_{k}>,{\sqrt{n}}}. 그래서 정수 버전에 팔짱 k⌋ ≥ ⌊ ⌊다 k≥ n{\displaystyle{)}_{k}\geq{\sqrt{n}라는 주주가 가지고 있다. n⌋{)$displaystyle \lfloor {x}_{k}\rfloor \geq \lfloor {\sqrt {n}}\rfloor }$ and ${\displaystyle {x}_{k}\geq \lfloor {x}_{k}\rfloor >{x}_{k+1}\geq \lfloor {x}_{k+1}\rfloor }$ until the final solution ${\displaystyle {x}_{s}}$ is reached. For the final solution ${\displaystyle {x}_{s}}$, one has ${\displaystyle \lfloor {\sqrt {n}}\rfloor \leq \lfloor {x}_{s}\rfloor \leq {\sqrt {n}}}$ and ${\displaystyle \lfloor {x}_{s+1}\rfloor \geq \lfloor {x}_{s}\rfloor }$, so the stopping criterion is ${\displaystyle \lfloor }$ ${\displaystyle {}_{}}$ ${\displaystyle {}_{}}$+ ${\displaystyle 1_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle \rfloor }$ x x ${\displaystyle {}_{}}${ { { ${$ \$displaystyle \llfloor {x}_{k+1}\rfloor \geq \lllfloor {x}_{k}\rfloor$ $\}.$

단,${{\displaystyle \lfloor{\sqrt{n}\rfloor}}$는 반드시 위의 반복식의 고정점이라고 할$$ 수는 없다. 실제로 $1 {\displaystyle$$\lfloor{\sqrt{n$$}}\$$rfloor }$은$($는) 완벽한 사각형이 아닌$$ 경우에만 고정점임을$$ 알 수 있다. $n{\displaystyle }$+ ${\displaystyle 1}$ ${\displaystyle n+1$}이$($가) 완벽한 정사각형인 경우, 시퀀스는 수렴$$ 대신$\{\displaystyle$\$lfloor$${\$$sqloor{$$n}$와 $\lfloor {\displaystyle }$ ${\displaystyle n\sqrt{}}$ ${\displaystyle \backslash }$+ ${\displaystystyle$\$n$} 사이의 2 사이클로 끝나게 된다.

C에서의 구현 예

// 정수의 제곱근 서명이 없는 인트로 int_sqrt ( 서명이 없는 인트로 s ) {  서명이 없는 인트로 x0 = s / 2;   // 초기 추정치                             // s가 최대 표현 가능한 값일 때는 오버플로우를 피하십시오.   // 건전성 검사  만일 ( x0 != 0 )  {   서명이 없는 인트로 x1 = ( x0 + s / x0 ) / 2; // 업데이트      하는 동안에 ( x1 < x0 )    // 사이클도 점검한다.   {    x0 = x1;    x1 = ( x0 + s / x0 ) / 2;   }      돌아오다 x0;  }  다른  {   돌아오다 s;  } } 

숫자 예제

예를 들어 위의 알고리즘을 사용하여 2,000 000의 정수 제곱근을 계산하면, 1,000, 500 001, 250 002, 125 004, 62 509, 31 270, 15 666, 7 896, 4 074, 2 282, 1 579, 1 422, 1 414, 1 414의 시퀀스를 얻는다. 총 13개의 반복 단계가 필요하다. 헤론의 방법은 2차적으로 용액에 가깝게 수렴되지만, 초기에는 반복당 1비트 미만의 정밀도를 얻는다. 이것은 초기 추정치의 선택이 알고리즘의 성능에 매우 중요하다는 것을 의미한다.

2진수 로그의 정수 부분 또는 비트 길이(예: C++20)에 대한 빠른 계산을 사용할 수 있는 경우 에서 시작하는 것이 좋다.

${\displaystyle x_{}}$ ${\displaystyle {0\mathrm{}}_{}}$= ${\displaystyle {\mathrm{}}^{}}$ ${\displaystyle {\lfloor }^{}}$ ${\displaystyle {(2}^{}}$ ${\displaystyle {{}_{}}^{}}$ n${\displaystyle {}^{}}$)${\displaystyle {}^{}}$/ ${\displaystyle 2^{}}$⌋${\displaystyle {}^{}}$+ 1 ${\$+1$\},$

which is the least power of two bigger than ${\displaystyle {\sqrt {n}}}$. In the example of the integer square root of 2 000 000, ${\displaystyle \lfloor \log _{2}n\rfloor =20}$, ${\displaystyle x_{0}=2^{11}=2048}$, and the resulting sequence is 2 048, 1 512, 1 417, 1 414, 1 414. 이 경우 4회 반복 단계만 필요하다.

자릿수 알고리즘

$정사각형{\displaystyle \sqrt{}}$ 루트$$n {\$displaystyle {\sqrt{n}}$을(를) 계산하기 위한 기존의 펜-페이퍼 알고리즘은 더 높은 자리수에서 더 낮은 자리까지 작업하는 것을 기본으로 하며$$, 새로운 자리마다 여전히 정사각형 $\le {\displaystyle n}$ ${\displaystyle \leq$ n$}$을 산출할 가장 큰 자리를 선택하므로$,$ 만약 한 자리 뒤에 정지하면 계산된 결과는 정수 sq가 될 것이다.뿌리째 뽑다

비트 연산 사용

베이스 2에서 작업할 경우 숫자 선택은 0('작은 후보')에서 1('큰 후보')로 단순화되며, 숫자 조작은 2진수 교대조 운영의 관점에서 표현할 수 있다. 와 함께 * 곱하기, << 왼쪽 교대조에서 >> 논리 오른쪽 이동인 경우, 자연수의 정수 제곱근을 찾는 재귀 알고리즘은 다음과 같다.

반항하다 정수_sqrt(n: 인트로) -> 인트로:     주장하다 n >= 0, "sqrt는 음이 아닌 입력에만 작동"     만일 n < 2:         돌아오다 n      # 재귀 호출:     작은_캔들 = 정수_sqrt(n >> 2) << 1     대형_캔들 = 작은_캔들 + 1     만일 대형_캔들 * 대형_캔들 > n:         돌아오다 작은_캔들     다른:         돌아오다 대형_캔들   # 동등하게: 반항하다 정수_sqrt_iter(n: 인트로) -> 인트로:     주장하다 n >= 0, "sqrt는 음이 아닌 입력에만 작동"     만일 n < 2:         돌아오다 n      # 시프트 금액을 찾아라. 참고 항목 [[첫 번째 집합 찾기]],     # shift = ceil(log2(n) * 0.5) * 2 = ceil(ffs(n) * 0.5) * 2     교대시키다 = 2     하는 동안에 (n >> 교대시키다) != 0:         교대시키다 += 2      # 비트설정 루프를 푼다.     결과 = 0     하는 동안에 교대시키다 >= 0:         결과 = 결과 << 1         대형_캔들 = (             결과 + 1         )  # 결과 ^ 1 (xor)과 동일하며, 마지막 비트는 항상 0이기 때문이다.         만일 대형_캔들 * 대형_캔들 <= n >> 교대시키다:             결과 = 대형_캔들         교대시키다 -= 2      돌아오다 결과 

숫자별 알고리즘의 전통적인 펜앤페이퍼 표시는 위의 코드에는 존재하지 않는 다양한 최적화를 포함하며, 특히 이전 자릿수의 제곱을 미리 추론하는 수법은 일반적인 곱셈 단계를 불필요하게 만든다. 예를 들어 제곱근 계산 방법 § 이진수 시스템(기준 2)을 참조하십시오.^[1]

프로그래밍 언어에서

일부 프로그래밍 언어는 일반 사례 외에 정수 제곱근 계산에 명시적 연산을 할애하거나 라이브러리에 의해 이를 위해 확장할 수 있다.

• (isqrt x): Common Lisp.^[2]
• math.isqrt(x):^[3] 파이톤. (버전 3.8 이후)

참고 항목

• 제곱근 계산 방법

참조

외부 링크

• 제곱근 알고리즘의 기하학적 뷰