13

I need to multiply two polynomials each having small integral coefficients. I need a fast FFT routine in C/C++ which can convolve them. I have seen several libraries but they seem to be too large spread over multiple files. What is important is I need code which is not too long and can be very easily used and compiled in a single .c/.cpp file.

  1. FFT should be optimized for real inputs at least if not small integers.
  2. Radix 4 implementation if available would be fine too.
  3. Compiling it should take no special compilation flags as compilation of program has to be done in external environment which I can't control.

One that very well matches my needs is here. But I need something twice as fast.

Paul R
  • 208,748
  • 37
  • 389
  • 560
Nikhil Garg
  • 3,944
  • 9
  • 30
  • 37
  • 2
    What's your question? I need a million dollars. Also, I like cheese. A LOT. – Mateen Ulhaq Mar 10 '11 at 04:33
  • 1
    @muntoo - Real polynomial convolution is an important problem in itself and hence I think its natural to ask this question. I don't need full power of FFT but just a specific small subset and the fact that there IS an OS implementation almost suiting my needs, means that it is not unrealistic either. – Nikhil Garg Mar 10 '11 at 04:47
  • 2
    How large are the polynomials? FFT has better complexity than direct convolution, but also a significantly higher constant, for small problems direct convolution would be faster. – Ben Voigt Mar 10 '11 at 05:04
  • 2
    Pretty large. Degree is around 10^6. I am sure an O(N^2) algorithm won't run in any reasonable time. – Nikhil Garg Mar 10 '11 at 06:28

3 Answers3

20

For a straightforward and easy to use FFT implementation try KissFFT. If you need absolute maximum performance though, and don't mind a little complexity, then it has to be FFTW.

Paul R
  • 208,748
  • 37
  • 389
  • 560
4

I've collected some of my top search results that fit or mostly fit the question (C/C++ FFT), and I've generally organized them from simple to complex:

Feel free to add to or update the list.

Andrew
  • 5,839
  • 1
  • 51
  • 72
3

I've adapted the smbFft function from this example on DspDimension to my needs in the past.

Left For Archive
  • 2,626
  • 1
  • 18
  • 19