큰 숫자의 곱

Question

알고리즘을 분석하는 동안 우리는 일반적으로 단일 컴퓨터 명령을 취하기 위해 곱셈을 가정한다고 봅니다. 그러나이 가정은 숫자의 크기 (비트 수와 관련하여)가 적절하지 않을 때 발생합니다. 가장 기본적인 형태의 곱셈에서 두 개의 n 비트 숫자를 곱하는 것은 일반적으로 O (n^2)입니다. 이 맥락에서, x^n (x의 n 승) 계산에 대한 복잡성 (비트 연산 관점에서)은 무엇일까요? Explain 된 방식으로

는 나에게 복잡성은

Answer 1

x^n을 계산하는 복잡도는 물론 전력 계산에 사용되는 알고리즘과 곱셈에 달려 있습니다. 지수에 의한 제곱 당 힘을 계산하면 O (log n) 곱셈이 필요합니다. 각 단계에서 하나의 숫자를 정사각형으로 표시하거나 두 개의 숫자를 곱해서 두 개의 숫자 중 하나를 정사각형으로 표시합니다. x가 d(x) 숫자를 가지고

경우 x^n는 Θ가 (n 개 * (D)가 (X)) 자리 마지막 단계에서는 약 n/2*d(x) 자릿수를 정사각형 (및 가능한 한 작게하여 그 수를 곱) 및 보유 알고리즘은 누적 기와 함께 반복 된 사분면 x^(2^k)을 2^k <= n < 2^(k+1)으로 곱함으로써 완성됩니다.

하자가 m -digit 번호 제곱의 선정 될 S(m) (또는 선정 된 임의의 두 m -digit 숫자를 곱한 M(m) 동일하지 않을 수 있음). 그 다음 squarings은 대략

S(2^(k-1)*d(x)) + S(2^(k-2)*d(x)) + S(2^(k-3)*d(x)) + ... 

work가 필요합니다. S(m) >= m부터 S(2^(k-1)*d(x))과 2*S(2^(k-1)*d(x)) 사이입니다. 그래서 squarings에 대한 작업은 마지막 단계에 의해 지배됩니다. 누적 기와 함께 x^(2^s)을 곱하면, 같은 결과가 얻어지며 최종 곱셈이 작업을 지배합니다. 최종 누산기 반복 제곱만큼 클 수 있으므로 반복 제곱하여 n 번째 전력 x 상승의 총 비용은 Θ(M(n*d(x)))이다

Θ(M(2^k*d(x)), 

이다. 순수한 곱셈 (M(m) = O(m^2))을 사용하면 총 비용은 O(n^2*d(x)^2)이됩니다. 더 진보 된 곱셈 알고리즘 (Karatsuba, Toom-Cook, Schönhage-Strassen, ...)을 사용하면 훨씬 낮은 복잡성을 갖게되고, O(n*d(x)*log (n*d(x)) * log log (n*d(x))) 조금 약간 아래로 내려갑니다.

n 단계, x 곱하여 반복적 컴퓨팅 파워

는 M(m,k)가 k -digit 번호가 포함 m -digit 수를 곱한 비용을 표시하자. 하나의 요인은 항상 x 때문에, 총 비용은 비용 M(m,k) = m*k와 교과서 알고리즘으로

M(d(x),d(x)) + M(d(x),2*d(x)) + M(d(x),3*d(x)) + ... + M(d(x),(n-1)*d(x)) 

입니다,이 n*(n-1)/2*d(x)^2에 요약, 그래서 총 비용은 다시 Θ(n^2*d(x)^2)입니다. 그러나 상수 계수는 반복 된 제곱에 의한 지수화보다 큽니다. , m < k 경우 1 자리로 숫자를 볼 - 많은 Θ(m*k) 아래의 비용 M(m,k)을 줄일 - 내가 아는까지로 -, 당신이 할 수없는 몇 번 반복 한 후 여기에 어떻게 당신이 크게 다른 길이의 숫자를 곱 있습니다

숫자와 r- 자리 숫자 (r*m <= k < (r+1)*m)를 b^m으로 설정하면 m이 충분히 큰 경우 더 나은 알고리즘을 사용하여 "숫자"를 곱하는 비용을 줄일 수 있지만 r 요소는 줄일 수 없습니다. 따라서이 알고리즘은 O(n^2*M(d(x)))의 복잡도를 가지므로 n^2 인수는 제거 할 수 없습니다.

Answer 2

Wikipedia 다양한 곱셈 알고리즘의 복잡성 시간의 좋은 개요를 n 개의 기하 급수적으로 (그러나 정확한 그림의 확실하지 않은) 것 같다.

2 개의 m 자리 숫자 (O (m^2)의 복잡성을 가짐)와 그 자체로 숫자를 곱하여 힘을 모으는 순진한 방법을 곱하는 단순한 교과서 방법을 가정 해 보겠습니다. 시간은, 단순히 N 승산, O (n 개 *의 m^2)의 때문에 복잡성 또는 O (㎚^2)

Answer 3

N^K 비용이 (N)

O((log(n))^k) 

로그 - 비트 - n의 표현 n

^k - 두 개의 n 자릿수 O 비용 (n^2)