He de algunos problemas en la comprensión de enteros multiplicación de uso de la FFT.
Estoy utilizando el algoritmo descrito en la wikipedia.
Aquí es un ejemplo de cómo entiendo este algoritmo:
$$a=173$$
$$b=95$$
Permite llevar a $w=4$, luego tenemos
$$a=13*2^{4\cdot 0}+10*2^{4\cdot1}$$
$$b=15*2^{4\cdot 0}+5*2^{4\cdot1}$$
En la notación de vector se parece a esto:
$$a = \left[ \begin{array}{cc} 13 \\ 10 \end{array} \right]$$
$$b = \left[ \begin{array}{cc} 15 \\ 5 \end{array} \right]$$
La FFT de esos vectores son:
$$f(a) = \left[ \begin{array}{cc} \frac{23}{\sqrt{2}} \\ \frac{3}{\sqrt{2}} \end{array} \right]$$
$$f(b) = \left[ \begin{array}{cc} \frac{20}{\sqrt{2}} \\ \frac{10}{\sqrt{2}} \end{array} \right]$$
El producto de los resultados de la entrada por entrada es:
$$c = \left[ \begin{array}{cc} 230 \\ 15 \end{array} \right]$$
La FFT inversa de a $c$ es:
$$f^{-1}(c)= \left[ \begin{array}{cc} \frac{245}{\sqrt{2}} \\ \frac{215}{\sqrt{2}} \end{array} \right]$$
Y ahora, ¿qué se debe hacer?
Editar
Como me di cuenta de los vectores debe ser 4dimensional en lugar de dos dimensiones. Aquí son correctos los cálculos (en caso de que alguien tiene un problema similar):
$$a = \left[ \begin{array}{cc} 13 \\ 10 \\ 0 \\ 0 \end{array} \right]$$
$$b = \left[ \begin{array}{cc} 15 \\ 5 \\ 0 \\ 0 \end{array} \right]$$
La FFT de esos vectores son:
$$f(a) = \left[ \begin{array}{cc} 11.5 \\ 6.5+5i \\ 1.5 \\ 6.5-5i \end{array} \right]$$
$$f(b) = \left[ \begin{array}{cc} 10 \\ 7.5+2.5i \\ 5 \\ 7.5-2.5i \end{array} \right]$$
El producto de los resultados de la entrada por entrada es:
$$c = \left[ \begin{array}{cc} 115 \\ 36.25+53.75i \\ 7.5 \\ 36.25-53.75i \end{array} \right]$$
La FFT inversa de a $c$ es:
$$f^{-1}(c)= \left[ \begin{array}{cc} 195 \\ 215 \\ 50 \\ 0 \end{array} \right]$$
Así que el resultado final es $ab=195\cdot 2^{0} + 215 \cdot 2^{4} + 50 \cdot 2^{8} = 16435$
