Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$

share|improve this question
2  
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). –  Myself Mar 16 '11 at 19:06
    
@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. –  Tomek Tarczynski Mar 16 '11 at 19:47
    
Excellent example...ya know, you can make your own answer out of this so it is sorta official. –  Mitch Mar 17 '11 at 2:22
    
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. –  Myself Mar 17 '11 at 6:18
    
@Myself: I was glad to accept your answer. –  Tomek Tarczynski Mar 17 '11 at 8:16

1 Answer 1

up vote 1 down vote accepted

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

share|improve this answer
    
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? –  Tomek Tarczynski Mar 17 '11 at 8:56
    
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)$. –  Myself Mar 17 '11 at 12:41

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.