[일반] 근대 어떻게 FFT로 큰 수 곱셈을 하나용?

[익명(211.42)]

크기가 n인 a[] b[] 있을 때 FFT 써서 크기가 2n인 c={a[0]b[0], a[0]b[1]+a[1]b[0], ... , a[n]b[n]} 만드는 건 알겠는데 그거랑 큰 수 곱셈이 뭔상관인진 모루겟소요..

[익명(114.207)]

123 = 1*10^2 + 2*10^1 + 3 * 10^0 이런식으로 생각하고 전개해보면 감이 올거임

[Dd(115.137)]

https://en.m.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strassen_algorithm
이걸
알아야 하는걸까요?

[익명(114.207)]

아니 전혀;

[익명(114.207)]

123 * 456 = (1*3)*10^4 + (1*5+2*4)*10^3 + (1*6+2*5+3*4)*10^2 + (2*6+3*5)*10^1 + (3*6)*10^0

[익명(114.207)]

결국엔 큰수곱셈 == 이산콘볼루션 구하기임

[Dd(115.137)]

아 그냥 합성곱이었네요 혼자 이상한 생각하고있었네 ㄱㅅㄱㅅ