cs Archives - How IT

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) = x^{2} - c

$p(x) = x^2 -c$ .

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

O (\lg n)

$O(\lg n)$ 뉴턴의 방법으로 충분하다.

뉴턴 방법의 각 반복 계산

x_{j + 1} = x_{j} - (x_{j}^{2} - c) / (2 x_{j}) = 0.5 x_{j} + \frac{c}{2 x_{j}} .

$x_{j+1} = x_j - (x_j^2 -c)/(2x_j) = 0.5 x_j + \frac{c}{2x_j}.$

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

\overset{}{O} (b \lg b)

$\stackrel{~}{O}(b \lg b)$ 두 곱하기 $b$

b

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

\lg \lg b

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

b

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

\overset{}{O} (n \lg n)

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

O (\lg n)

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

n

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

\overset{}{O} (n (\lg n)^{2})

$\stackrel{~}{O}(n (\lg n)^2)$ . 이것은 이차 이하입니다.

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

\overset{}{영형} (엔 \lg 엔)

$\stackrel{~}{O}(n \lg n)$ 러닝 타임 (각각 알아야 할 것을 고려하여 $x_{j}$

x_{j}

$x_j$ ~ 안에 $j$

j

$j$ 정밀도가 아닌 비트 $n$

n

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

답변

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

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

엑스

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

\frac{1}{\sqrt{엑스}}

$\frac{1}{\sqrt x}$ 반복 :

r_{i + 1} = \frac{1}{2} r_{i} (3 - x r_{i}^{2})

$r_{i+1} = \frac{1}{2} r_i (3 - x r_i^2)$

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

w_{i} = r_{i}^{2}

$w_i = r_i^2$

d_{i} = 1 - w_{i} x

$d_i = 1 - w_i x$

r_{i + 1} = r_{i} + \frac{r_{i} d_{i}}{2}

$r_{i+1} = r_i + \frac{r_i d_i}{2}$

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

이제 문제는 $r$

r

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

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

x

$x$ :

x^{'} = 2^{- 2 e} x

$x' = 2^{-2e} x$

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

x^{'}

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

1

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

x^{'}

$x'$ 대신에 $x$

x

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

r = \frac{1}{{\sqrt{x}}^{'}}

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

\sqrt{x} = 2^{e} r x^{'}

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

이제 나누자 $r$

r

$r$ 가수와 지수로 :

r_{i} = 2^{- e_{i}} r_{i}^{'}

$r_i = 2^{-e_i} r'_i$

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

r_{i}^{'}

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

e_{i}

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

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

e_{i + 1} = 2 e_{i}

$e_{i+1} = 2e_i$

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

e_{i + 1} = 2 e_{i}

$e_{i+1} = 2e_i$

w_{i} = {r_{i}^{'}}^{2}

$w_i = {r'_i}^2$

x_{i}^{'} = \frac{x}{2^{2 e - e_{i + 1}}}

$x'_i = \frac{x}{2^{2e - e_{i+1}}}$

d_{i} = 2^{e_{i + 1}} - \frac{w_{i}^{'} x_{i}^{'}}{2^{e_{i + 1}}}

$d_i = 2^{e_{i+1}} - \frac{w_i' x'_i}{2^{e_{i+1}}}$

r_{i + 1}^{'} = 2^{e_{i}} r_{i}^{'} - \frac{r_{i}^{'} d_{i}}{2^{e_{i} + 1}}

$r'_{i+1} = 2^{e_i} r'_i - \frac{r'_i d_i}{2^{e_i + 1}}$

반복 할 때마다 :

\sqrt{x} \approx \frac{r_{i}^{'} x}{2^{e + e_{i}}}

$\sqrt{x} \approx \frac{r'_i x}{2^{e + e_i}}$

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

x = 2^{63}

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

2^{31} \sqrt{2}

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

\frac{1}{\sqrt{2}} 2^{- 31}

$\frac{1}{\sqrt{2}} 2^{-31}$ 그래서 우리는 설정합니다 $e = 31$

e = 31

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

r_{0}^{'} = 3

$r'_0 = 3$ 과 $e_{0} = 2$

e_{0} = 2

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

\frac{3}{4}

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

\frac{1}{\sqrt{2}}

$\frac{1}{\sqrt{2}}$ .)

그때:

e_{1} = 4, r_{1}^{'} = 11

$e_1 = 4, r'_1 = 11$

e_{2} = 8, r_{2}^{'} = 180

$e_2 = 8, r'_2 = 180$

e_{3} = 16, r_{3}^{'} = 46338

$e_3 = 16, r'_3 = 46338$

e_{4} = 32, r_{4}^{'} = 3037000481

$e_4 = 32, r'_4 = 3037000481$

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

e_{i}

$e_i$ 에 $e$

e

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

e_{i} > 2 e

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

\sqrt{2^{63}} \approx \frac{3037000481 \times 2^{63}}{2^{31 + 32}} = 3037000481

$\sqrt{2^{63}} \approx \frac{3037000481 \times 2^{63}}{2^{31+32}} = 3037000481$

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

3037000499

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

e_{i}

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

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

b

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

O (b \log b)

$O(b \log b)$ operations. However, we have arranged things so that $r_{i}^{'} < 2^{e_{i}}$

r_{i}^{'} < 2^{e_{i}}

$r'_i < 2^{e_i}$ . So the multiplication to calculate $w_{i}$

w_{i}

$w_i$ multiplies two $e_{i}$

e_{i}

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

e_{i + 1}

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

e_{i + 1}

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

2 e_{i + 1}

$2e_{i+1}$ -bit number.

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

O (e_{i} \log e_{i})

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

O (\log e)

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

O (2 e \log 2 e)

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

O (e \log^{2} e)

$O(e \log^2 e)$ operations, which is sub-quadratic in the number of bits in $x$

x

$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}}$

\frac{a b}{2^{c}}

$\frac{ab}{2^c}$ . Clearly it's wasteful to compute the all the bits of $a b$

a b

$ab$ only to throw $c$

c

$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

언제든지 물어보세요.

카테고리 보관물: cs

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

답변

답변

답변