7
$\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
  • 2
    $\begingroup$ 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$
    – Myself
    Mar 16, 2011 at 19:06
  • $\begingroup$ @Myself: Calculation were ok, but as You have noticed I should have 4 positions instead of 2. When I took 4 positions ($a=[13,10,0,0]$ and so on) the result was correct. $\endgroup$
    – Tomek Tarczynski
    Mar 16, 2011 at 19:47
  • $\begingroup$ Excellent example...ya know, you can make your own answer out of this so it is sorta official. $\endgroup$
    – Mitch
    Mar 17, 2011 at 2:22
  • $\begingroup$ 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. $\endgroup$
    – Myself
    Mar 17, 2011 at 6:18

1 Answer 1

Reset to default
1
$\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
  • $\begingroup$ I still have one question. According to wiki "The only important thing is that the forward and inverse transforms have opposite-sign exponents, and that the product of their normalization factors be 1/N". So we can take $\frac{1}{\sqrt{n}}$ as normalization factor to both the transform and its inverse, but then after multiplying those two DFT we have $\frac{1}{n}f(a)*f(b)$, so the normalization factor after taking the inverse of this would be $\frac{1}{n\sqrt{n}}$. We would obtain different result if we have taken normalization factor $1$ and $\frac{1}{n}$. Where did that difference come from? $\endgroup$
    – Tomek Tarczynski
    Mar 17, 2011 at 8:56
  • $\begingroup$ 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)$. $\endgroup$
    – Myself
    Mar 17, 2011 at 12:41

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .