next up previous
Next: Towards an iterative algorithm for Up: Advanced Computer Algebra: From Newton Previous: Primitive n-th roots of unity

Efficient implementation

The theoretical complexity of Algorithm 1 is good but does not lead to a practical implementation of a fast multiplication of polynomials. According to [GCL92] it is not better than the classical algorithm for n $ \leq$ 300. The reasons are We are going to get rid off these two difficulties leading to a practical algorithm better than the classical one for n $ \geq$ 32 (in ALDOR).



Subsections
next up previous
Next: Towards an iterative algorithm for Up: Advanced Computer Algebra: From Newton Previous: Primitive n-th roots of unity
Marc Moreno Maza
2004-04-27