<s>[INST] Integer multiplication using FFT I've some trouble in understanding integer multiplication using FFT.
I'm using the algorithm described on wikipedia.
Here is an example of how I understand this algorithm:
$$a=173$$
$$b=95$$
Lets take $w=4$, then we have
$$a=13*2^{4\cdot 0}+10*2^{4\cdot1}$$
$$b=15*2^{4\cdot 0}+5*2^{4\cdot1}$$
In the vector notation it looks like this:
$$a = \left[ \begin{array}{cc} 13 \\ 10 \end{array} \right]$$
$$b = \left[ \begin{array}{cc} 15 \\ 5 \end{array} \right]$$
The FFT of those vectors are:
$$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]$$
The product of those results entry by entry is:
$$c = \left[ \begin{array}{cc} 230 \\ 15 \end{array} \right]$$
The inverse FFT of $c$ is:
$$f^{-1}(c)= \left[ \begin{array}{cc} \frac{245}{\sqrt{2}} \\ \frac{215}{\sqrt{2}} \end{array} \right]$$
And now what should be done?
Edit
As Myself noticed those vectors should be 4dimensional instead of two dimensional. Here are correct calculations (in case anyone has similar problem): 
$$a = \left[ \begin{array}{cc} 13 \\ 10 \\ 0 \\ 0 \end{array} \right]$$
$$b = \left[ \begin{array}{cc} 15 \\ 5 \\ 0 \\ 0 \end{array} \right]$$
The FFT of those vectors are:
$$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]$$
The product of those results entry by entry is:
$$c = \left[ \begin{array}{cc} 115 \\ 36.25+53.75i \\ 7.5 \\ 36.25-53.75i \end{array} \right]$$
The inverse FFT of $c$ is:
$$f^{-1}(c)= \left[ \begin{array}{cc} 195 \\ 215 \\ 50 \\ 0 \end{array} \right]$$
So the final result is $ab=195\cdot 2^{0} + 215 \cdot 2^{4} + 50 \cdot 2^{8} = 16435$
 [/INST] -- answer first posted as comment -- 
At this point I think you're supposed to reinterpret this result as a natural number that's the product of the numbers you started with. Wait, $\sqrt{2}$? Have you double-checked the calculations? Also I think your vectors should have 4 positions because now the result will be cropped (i.e. the circular convolution gives a different result than the real convolution).
</s>