middle products

[David Harvey]

On Jun 18, 2009, at 3:48 AM, Paul Zimmermann wrote:

>        David,
>
>>> and already save more than 33% at 55 limbs. Larger timings in the  
>>> FFT
>>> range (say 100,000, 1M, 10M, 100M and 1G limbs) would be
>>> interesting too.
>>
>> 10^4 | 4.09e+07 | 2.53e+07 |  0.619  |
>> 10^5 | 9.68e+08 | 7.99e+08 |  0.825  |
>> 10^6 | 1.90e+10 | 2.70e+10 |  1.421  |
>>
>> That's the karatsuba asymptotics starting to dominate. At these sizes
>> surely it is better to use the FFT wraparound than to use my  
>> mpn_mulmid.
>
> don't you also have a Toom-Cook 3-way mulmid?

Yes, but

(a) I don't trust the code, and
(b) the size where it starts to beat karatsuba is about the same as  
where the FFT wraparound beats karatsuba, so I don't really see the  
point. Unless someone can figure out how to make it much more efficient.

david