Hi, I'd like to request a review of my polynomial library which I wrote during Google Summer of Code project this year. The zip file is in Boost Vault (called polynomial.zip). It includes the library, tests and documentation. The same files (not compressed) are also available in sandbox: http://svn.boost.org/svn/boost/sandbox/SOC/2008/polynomial/ Thanks -- Pawel Kieliszczyk
Hi Paweł, I have added your library to the review queue. Could you please send me a short description of the library? Thanks, ron On Aug 29, 2008, at 11:04 AM, Paweł Kieliszczyk wrote:
Hi, I'd like to request a review of my polynomial library which I wrote during Google Summer of Code project this year.
The zip file is in Boost Vault (called polynomial.zip). It includes the library, tests and documentation. The same files (not compressed) are also available in sandbox: http://svn.boost.org/svn/boost/sandbox/SOC/2008/polynomial/
Thanks
-- Pawel Kieliszczyk _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/ listinfo.cgi/boost
Hi, 2008/8/30 Ronald Garcia <garcia@cs.indiana.edu>
Hi Paweł,
I have added your library to the review queue. Could you please send me a short description of the library?
Thanks, ron
Thanks. The library was written to enable fast and faithful polynomial manupulation. It provides: - main arithmetic operators (+, -, * using FFT, /, %), - gcd, - different methods of evaluation (Horner Scheme, Compensated Horner Algorithm, by preconditioning), - derivatives and integrals, - interpolation, - conversions between various polynomial forms (special functions for creating Chebyshev, Hermite, Laguerre and Legendre form). -- Pawel Kieliszczyk
On Aug 31, 2008, at 6:12 AM, Paweł Kieliszczyk wrote: [SNIP]
The library was written to enable fast and faithful polynomial manupulation. It provides: - main arithmetic operators (+, -, * using FFT, /, %), [TRUNCATE]
(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. -- Daryle Walker Mac, Internet, and Video Game Junkie darylew AT hotmail DOT com
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? -- Pawel Kieliszczyk
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
participants (3)
-
Daryle Walker -
Paweł Kieliszczyk -
Ronald Garcia