DWORD 배열로 표현되는 큰 정수를 제곱하는 가장 빠른 알고리즘은 무엇입니까?

빠른 빅넘 제곱 계산

이 글의 목적은 부호 없는 DWORD의 동적 배열로 표현된 bigint에 대해 y = x^2를 계산하는 가장 빠른 방법을 결정하는 것입니다.

문제 설명

bigint x를 배열로 표현하면 DWORD:

DWORD x[n+1] = { LSW, ......, MSW };

여기서:

• n 1은 사용된 DWORD 수입니다.
• x = x[0] x[1]<< 32 ... x[N]<<32*(n)

정밀도를 잃지 않고 최대한 빨리 y = x^2의 값을 구합니다.

가정:

• 계산은 C 및 32비트 정수 연산을 사용하여 수행됩니다. carry.

순진한 접근 방식(O(n^2) 곱셈)

순진한 접근 방식은 x를 자체적으로 곱하는 것으로, O(n^2) 시간이 걸립니다. 이는 다음과 같이 표현될 수 있습니다:

y = x * x
y = (x0 + x1 + x2 + ...xn)*(x0 + x1 + x2 + ...xn)

곱셈을 확장하면 다음과 같은 결과가 나옵니다.

y0     = x0*x0
y1     = x1*x0 + x0*x1
y2     = x2*x0 + x1*x1 + x0*x2
y3     = x3*x0 + x2*x1 + x1*x2
...
y(2n-3) = xn(n-2)*x(n  ) + x(n-1)*x(n-1) + x(n  )*x(n-2)
y(2n-2) = xn(n-1)*x(n  ) + x(n  )*x(n-1)
y(2n-1) = xn(n  )*x(n  )

Karatsuba 곱셈

Karatsuba 알고리즘을 사용하여 곱셈 속도를 높일 수 있습니다. O(n^log2(3)). 유망해 보이지만 알고리즘의 재귀적 특성으로 인해 큰 숫자에 상당한 성능 오버헤드가 발생할 수 있습니다.

최적화된 Schönhage-Strassen 곱셈

Schönhage-Strassen 알고리즘은 O( nlog(n)(log(log(n)))) 분할 정복 사용 접근하다. 그러나 이 알고리즘은 오버플로 문제와 부호 없는 정수에 대한 모듈러 산술의 필요성으로 인해 실질적인 제한이 있습니다.

결론

더 작은 숫자의 경우 간단한 O(n^2) 곱셈 접근 방식은 다음과 같습니다. 가장 효율적입니다. 더 큰 숫자의 경우 Karatsuba 곱셈 알고리즘을 권장합니다. 성능을 향상시키기 위해 FFT(Fast Fourier Transform) 또는 NTT(Number Theoretic Transform)를 사용하는 등 추가 최적화를 모색할 수 있습니다.

위 내용은 DWORD 배열로 표현되는 큰 정수를 제곱하는 가장 빠른 알고리즘은 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!