FFT Algorithm Variation

Hello to all, as you all know FFT algorithm has many variation in terms from its pruposes.

My requirement of FFT is integer multiplication and polynomial evaluation.

I looking for good reference about the topic.

If you have any, please post it here.

Thanks.

You need an FFT to do integer multiplication?

What sort of evaluation of polynomials do you need to do?

Horner Scheme is the one i looking for.

I am no mathematician, but isn't Horner's method a fairly basic/ancient approximation scheme for finding polynomial roots? I think for some problems a DFT or FFT would be an alternate to Horner's algorithm. I could be wrong, but I don't think there is such a thing as Horner's scheme of evaluating polynomials with an FFT. At least there isn't one listed in my dusty old copy of the Handbook of Applied Mathematics or Numerical Recipes in C.


Have you tried a google search yet? Perhaps we just have to figure out what terms you need to search on. What exactly are you trying to accomplish?

Horner's scheme is for evaluating polynomials. For example, for 4x^4 + x^3 - x^2 + x + 1, Horner's scheme amounts to rewriting it as 1 + x(1 + x(-1 + x(1 + x(4)))). I don't know what it has to do with the FFT, unless you want so many digits that it's worthwhile to do the individual multiplications using the FFT.

Basically, i just need simple integer multiplication with FFT.

Interesting. I never had the occasion to encounter this technique. I googled for fft+multiplication and the following link was at the top.

http://numbers.computation.free.fr/...rithms/fft.html

After an initial read I really don't see what's simple about this.

It's a pretty standard technique. I'm pretty sure GMP uses the FFT to multiply very large numbers. However, the numbers do have to be very large (thousands of digits, I think) in order for the FFT to win over, say, Karatsuba multiplication.

How about cooley turkey FFT ?