Boost logo

Boost :

Subject: Re: [boost] Review Request: Polynomial
From: Daryle Walker (darylew_at_[hidden])
Date: 2008-10-30 12:27:28

On Sep 3, 2008, at 10:51 AM, Paweł Kieliszczyk wrote:

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

Boost list run by bdawes at, gregod at, cpdaniel at, john at