Wraparound multiplicaton vs mullo
bodrato at mail.dm.unipi.it
bodrato at mail.dm.unipi.it
Wed Oct 21 06:29:08 CEST 2009
Ciao,
> Maybe I should write down how the x^4-1 algorithm works. Structure is
> First "evaluate" as follows,
>
> |s0| | 1 1 1 1| |a0| # f(1)
> |s1| | 1 -1 1 -1| |a1| # f(-1)
> |s2| = | 1 0 -1 0| * |a2| # Re f(i)
> |s3| | 0 1 0 -1| |a3| # Im f(i)
> |s4| | 1 1 -1 -1| # Re f(i) + Im f(i)
Then you perform five multiplication... I think it would be better to
implement a recursive function: compute the product Mod x^4-1 by computing
it Mod x^2-1 and Mod x^2+1, then using CRT.
You need:
- two multiplication for the x^2-1 side, this is the recursive side;
- three for the x^2+1 side, if you use Karatsuba...
But you can decide the best algorithm for the x^2+1 side, or let mul_n
choose the best for you... maybe you can exploit the FFT for larger sizes!
Moreover you don't need to write different functions for x^4-1, x^8-1...
> Almost all the linear operations are butterfly operations, i.e., they
The recursive version also uses only butterflies. I did found it
implemented in some Java library, it was named Nussbaumer's Convolution,
but I've never read the original paper...
Regards,
Marco
--
http://bodrato.it/
More information about the gmp-devel
mailing list