Wraparound multiplicaton vs mullo

[David Harvey]

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