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'm exploring the use of FFTs for multiplication, but even with simple examples it seems to go wrong. For example, here I'm trying to multiply $1$ by $2x$ (code is in matlab, but I think you can probably understand it even if you don't know the language):

# x and y are two polynomials, x(n) = 1; y(n) = 2n
x = [0 0 0 1];
y = [0 0 2 0];
# Evaluate both polynomials at roots of unity
xval = fft(x);
yval = fft(y);
# zval(n) = x(n)*y(n)
zval = xval .* yval;
# interpolate to get back prodvec(n) = x(n)*y(n)
prodvec = ifft(zval) / length(zval);

This gives an output of [0 0 0 .5] instead of [0 0 2 0]. Any idea what I'm doing wrong? It seems obvious enough that I should be doing $Wx$ to find the values of $x(n)$, and then $W^{-1}z$ will give me back the polynomial I want. But it's not working.

share|improve this question

1 Answer 1

up vote 2 down vote accepted

There are two things you're doing wrong:

  1. Vectors in matlab are read left-to-right, so you should have $x,y$ reversed.
  2. The FFT and inverse FFT operations are inverses, so there's no need to divide by the normalization factor.

Try this instead:

x = [1 0 0 0];
y = [0 2 0 0];
ifft(fft(x).*fft(y))
share|improve this answer
    
I wanted to write the same thing, but then thought that that can't be the entire problem, since in that case the result should have been [0 .5 0 0] and not [0 0 0 .5], no? –  joriki Feb 21 '11 at 19:10
    
Also, if the OP wants to multiply polynomials having too high degree, e.g. $x^3 + x^2 + 1$ (represented by $[1, 0, 1, 1]$) and $x^3 + x + 1$ (represented by $[1, 1, 0, 1]$), make sure to use the enough points in his Fourier transform, e.g. in this case fft(x, 8) instead of just fft(x). –  Calle Feb 21 '11 at 19:12
    
@joriki, have you tried the code? The reason you get $.5$ and not $2$ is because you divide by the length, which you shouldn't do, since it's built into ifft. –  Calle Feb 21 '11 at 19:14
    
@Calle: That's a misunderstanding. I agreed about the $.5$ and $2$, and also about the reversing of the vectors. What I got wrong was that I thought $x^5$ would be folded to $x^1$ if the array is too short, but in fact it gets folded to $x^3$, which explains the OP's result. –  joriki Feb 21 '11 at 19:18

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.