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

이런게 있다.

번역을 해 보자.

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))})$ 정도라고 한다.