Wraparound multiplicaton vs mullo
David Harvey
dmharvey at cims.nyu.edu
Sat Oct 17 21:43:56 CEST 2009
On Oct 17, 2009, at 1:41 PM, Niels Möller wrote:
>> Lets see what this means in Schoolbook, Karatsuba and Toom ranges,
>> ignoring the O(n) term:
>>
>> Schoolbook Karatsuba Toom-3 Toom-4
>> exponent 2 1.59 1.46 1.40
>>
>> x^2 - 1 0.5 M(n) 0.66 M(n) 0.72 M(n) 0.76 M(n)
>> x^4 - 1 0.31 M(n) 0.56 M(n) 0.65 M(n) 0.71 M(n)
>
> I've tried the x^2 - 1 algorithm now, and benchmarked on an AMD
> x86_32. A first implementation is attached.
Cool!
How about recursing into the same routine for the multiplication
modulo 2^(n/2) - 1? Do you think that would make much difference for
larger n? I suppose you would need n divisible by 4, or would need to
add some bit shifts.
david
More information about the gmp-devel
mailing list