2008/9/2 Daryle Walker wrote:
(I haven't looked at the library yet, so this may be not applicable.) Isn't there something called DFT that is something like FFT, but uses integers with modulo arithmetic? I think this can help processing polynomials and other lists that use integer coefficients without having to go into std::complex<double> arithmetic and risking rounding errors. Maybe that could be an optimization for integer-based polynomial lists.
Hi Daryle, I guess you're not thinking of Discrete Fourier Transform that is a form actually and also needs roots of unity. Well, in the library I used same FFT for every types of coefficients. Can you please expand this shortening or tell me where I could read more about it? Modulo arithmetic can also generate roots of unity. For example, if
On Sep 3, 2008, at 10:51 AM, Paweł Kieliszczyk wrote: the base is 31, then 2 is a fifth-root of unity (because 2**5 = 32 -> 1 under mod-31). The more precise term is "Number-theoretic transform," so look it up. -- Daryle Walker Mac, Internet, and Video Game Junkie darylew AT hotmail DOT com