Re: [boost] Review Request: Polynomial

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