Wraparound multiplicaton vs mullo

bodrato at mail.dm.unipi.it bodrato at mail.dm.unipi.it
Wed Oct 21 19:12:41 CEST 2009

>> 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!
> I'm not so sure this is useful. In FFT range, it would be better to
> use FFT for the top-level x^n-1, I think.

I think it is. For any strategy I heard of, multiplication is superlinear,
i.e. M(n) > M(n/2) + M'(n/2).
I mean, if you use FFT for a full product...

It should be tested.



More information about the gmp-devel mailing list