Wraparound multiplicaton vs mullo

[bodrato at mail.dm.unipi.it]

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/