푸리에 변환으로 곱셈 계산하기

http://en.wikipedia.org/wiki/Multiplication_algorithm#Fourier_transform_methods

이런게 있다.

번역을 해 보자.
Strassen의 아이디어다. (1968년)
가장 큰 정수 w를 고른다. w는 오버플로우는 내지 않도록 한다.
곱해야 할 두 수를, w비트인 m개의 그룹으로 나눈다.


그럼, 이제 이게 된다.


m보다 큰 i, j에 대해서 a와 b를 0으로 놓고, c는 a와 b의 convolution으로 놓는다.
convolution 정리에 따르면,
1.a와 b에 대해서 빠른 푸리에 변환을 한다.
2.두 계산 결과를 각각의 항 별로 곱한다
3.푸리에 역 변환을 계산한다
4.2^w보다 큰 c_k를 c_{k+1}에 더한다

이 계산 방법은 2007년 Furer에 의해 조금 개선되어서, 현재까지는 가장 빠른 곱셈법으로 알려져 있다.
Strassen의 원래 아이디어의 계산 복잡도는 대략 $\theta(n*ln(n)*ln(ln(n)))$정도이고, Furer 방법의 계산 복잡도는 $\theta(n*ln(n)*2^{(\theta(ln(n))})$ 정도라고 한다.

봐도 모르겠다...
나중에 논문 찾아서 읽어봐야지.
http://www.cse.psu.edu/~furer/Papers/mult.pdf
Furer의 논문이다. Strassen 알고리즘의 논문은 독일어 저널에 독일어 제목으로 실려 있는 것 같아서...보고싶지 않다...