6
$\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$

  • 0
    I'm not sure what's the "good" thing to do but I reposted my comment as an answer anyway so the question can be tagged as answered, since it seems to solve the mystery.2011-03-17

1 Answers 1

1

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

  • 0
    I think this is because here $DFT(a)\bullet DFT(b) = DFT(ab)$ (bullet = componentwise product) is only true if for DFT you use the 'real' Fourier transform. If you decide to use a scaled version $\alpha DFT=DFT'$ instead we'll have that $DFT'(a)\bullet DFT'(b) = \alpha DFT'(ab)$, so you would have to calculate $DFT'^{-1}\left(\frac{1}{\alpha}DFT'(a)\bullet DFT'(b)\right)$.2019-01-23