$\begingroup$

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$

$\endgroup$ 4

1 Answer

$\begingroup$

-- 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).

$\endgroup$ 2

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy