임의 정밀도 정수 제곱근 알고리즘? x -= inc

n비트 정수의 제곱근의 바닥을 계산하기위한 알려진 이차 알고리즘이 있습니까?

순진한 알고리즘은

def sqrt(x):
    r = 0
    i = x.bit_length() // 2
    while i >= 0:
        inc = (r << (i+1)) + (1 << (i*2))
        if inc <= x:
            x -= inc
            r += 1 << i
        i -= 1
    return r

이 작업에는 O(n)반복 작업 이 필요합니다 . 각 작업에는 O(n)시간 이 더해진 작업이 포함 되므로 O(n^2)전체 시간입니다. 더 빠른 것이 있습니까? 곱셈의 경우 2 차 시간보다 나은 특수 알고리즘이 있지만 제곱근에 대해서는 아무것도 찾을 수 없다는 것을 알고 있습니다.

답변

다항식의 근에 근사값을 구하기 위해 Newton의 방법 또는 다른 여러 방법을 사용할 수 있습니다 $p (x) = x^{2} - c$

p(x)=x2−c

Newton의 방법에 대한 수렴 속도는 2 차적입니다. 즉, 올바른 반복 횟수는 각 반복에서 두 배가됩니다. 이것은 의미 $O (\lg n)$

O(lg⁡n)

뉴턴의 방법으로 충분하다.

뉴턴 방법의 각 반복 계산

엑스 j + 1 = 엑스 제이 - (엑스 2 제이 - c) / (2 엑스 제이) = 0.5 엑스 제이 + 씨 2 엑스 제이 .

곱셈의 비트 복잡성은 $\overset{}{O} (b \lg b)$

O (blg⁡b)

두 곱하기 $b$

비트 정수 (무시) $\lg \lg b$

lg⁡lg⁡b

요인). 나누기의 비트 복잡도 $b$

정밀도의 비트)는 동일합니다. 따라서 각 반복은 $\overset{}{O} (n \lg n)$

O (nlg⁡n)

작업. 에 의해 곱하기 $O (\lg n)$

O(lg⁡n)

반복, 우리는 제곱근을 계산하는 전체 실행 시간을 $n$

정밀한 비트는 $\overset{}{O} (n (\lg n)^{2})$

O (n(lg⁡n)2)

. 이것은 이차 이하입니다.

더 신중한 분석에 따르면 이것이 향상 될 수 있다고 생각합니다. $\overset{}{O} (n \lg n)$

영형 (엔lg⁡엔)

러닝 타임 (각각 알아야 할 것을 고려하여 $x_{j}$

~ 안에 $j$

정밀도가 아닌 비트 $n$

정밀한 비트). 그러나 더 기본적인 분석조차도 이미 이차적 인 실행 시간을 보여줍니다.

답변

Newton의 방법의 문제점 중 하나는 각 반복마다 나누기 연산이 필요하다는 것입니다. 이는 가장 느린 기본 정수 연산입니다.

그러나 역 제곱근에 대한 뉴턴의 방법은 그렇지 않습니다. 만약 $x$

엑스

찾고자하는 번호입니다 $\frac{1}{\sqrt{x}}$

1엑스

반복 :

아르 자형 나는 + 1 = 1 2 아르 자형 나는 (3 - x r 2 i)

이것은 종종 다음과 같이 표현됩니다 :

w i = r 2 i

d i = 1 - w i x

r i + 1 = r i + r i d i 2

세 번의 곱셈 연산입니다. 2 개로 나누는 것은 오른쪽 이동으로 구현할 수 있습니다.

이제 문제는 $r$

정수가 아닙니다. 그러나 부동 소수점을 수동으로 구현하고 적절한 경우 보상하기 위해 많은 시프트 연산을 수행하여이를 조작 할 수 있습니다.

먼저 크기를 조정하겠습니다 $x$

x' = 2 - 2 e x

우리가 원하는 곳 $x^{'}$

x′

보다 크지 만 가까이 있어야합니다 $1$

. 위의 알고리즘을 실행하면 $x^{'}$

x′

대신에 $x$

, 우리는 찾는다 $r = \frac{1}{{\sqrt{x}}^{'}}$

r=1x′

. 그때, $\sqrt{x} = 2^{e} r x^{'}$

x=2erx′

이제 나누자 $r$

가수와 지수로 :

r i = 2 - e i r' i

어디 $r_{i}^{'}$

ri′

정수입니다. 직관적으로 $e_{i}$

답의 정확성을 나타냅니다.

우리는 뉴턴의 방법이 정확한 유효 자릿수의 두 배를 가짐을 알고 있습니다. 그래서 우리는 선택할 수 있습니다 :

e i + 1 = 2 e i

약간의 조작만으로 우리는 다음을 발견합니다.

e i + 1 = 2 e i

w i = r' i 2

x' i = x 2 2 e - e i + 1

d i = 2 e i + 1 - w ' i x ' i 2 e i + 1

r' i + 1 = 2 e i r' i - r ' i d i 2 e i + 1

반복 할 때마다 :

x - - \sqrt \approx r ' i x 2 e + e i

예를 들어, 제곱근을 계산해 봅시다 $x = 2^{63}$

x=263

. 우리는 그 답이 $2^{31} \sqrt{2}$

2312

. 상호 제곱근은 $\frac{1}{\sqrt{2}} 2^{- 31}$

122−31

그래서 우리는 설정합니다 $e = 31$

e=31

(이것은 문제의 규모입니다) 첫 번째 추측을 위해 우리는 선택할 것입니다 $r_{0}^{'} = 3$

r0′=3

과 $e_{0} = 2$

e0=2

. (즉, 우리는 $\frac{3}{4}$

초기 추정치 $\frac{1}{\sqrt{2}}$

그때:

e 1 = 4, r' 1 = 11

e 2 = 8, r' 2 = 180

e 3 = 16, r' 3 = 46338

e 4 = 32, r' 4 = 3037000481

우리는 반복을 멈추는 시점을 비교하여 해결할 수 있습니다. $e_{i}$

에 $e$

; 내가 정확하게 계산했다면 $e_{i} > 2 e$

ei>2e

충분해야합니다. 우리는 여기서 멈추고 다음을 찾습니다.

263 - - - \sqrt \approx 3037000481 \times 2 63 2 31 + 32 = 3037000481

올바른 정수 제곱근은 $3037000499$

3037000499

우리는 아주 가깝습니다. 또 다른 반복을 수행하거나 최적화되지 않은 최종 반복을 수행 할 수 있습니다. $e_{i}$

. 세부 사항은 연습으로 남습니다.

To analyse the complexity of this method, note that multiplying two $b$

-bit integers takes $O (b \log b)$

O(blog⁡b)

operations. However, we have arranged things so that $r_{i}^{'} < 2^{e_{i}}$

ri′<2ei

. So the multiplication to calculate $w_{i}$

multiplies two $e_{i}$

-bit numbers to produce a $e_{i + 1}$

ei+1

-bit number, and the other two multiplications multiply two $e_{i + 1}$

ei+1

-bit numbers to produce a $2 e_{i + 1}$

2ei+1

-bit number.

In each case, the number of operations per iteration is $O (e_{i} \log e_{i})$

O(eilog⁡ei)

, and there are $O (\log e)$

O(log⁡e)

iterations required. The final multiplication is on the order of $O (2 e \log 2 e)$

O(2elog⁡2e)

operations. So the overall complexity is $O (e \log^{2} e)$

O(elog2⁡e)

operations, which is sub-quadratic in the number of bits in $x$

. That ticks all the boxes.

However, this analysis hides an important principle which everyone working with large integers should keep in mind: because multiplication is superlinear in the number of bits, any multiplication operations should only be performed on integers which have the roughly the magnitude of the current precision (and, I might add, you should try to multiply numbers together which have a similar order of magnitude). Using integers larger than that is a waste of effort. Constant factors matter, and for large integers, they matter a lot.

As a final observation, two of the multiplications are of the form $\frac{a b}{2^{c}}$

ab2c

. Clearly it's wasteful to compute the all the bits of $a b$

only to throw $c$

of them away with a right-shift. Implementing a smart multiplication method which takes this into account is also left as an exercise.

How IT

언제든지 물어보세요.

임의 정밀도 정수 제곱근 알고리즘? x -= inc

답변

답변

답변