Wraparound multiplicaton vs mullo

[Niels Möller]

Torbjorn Granlund <tg at gmplib.org> writes:

> I suppose some maths on your table has the answer, but I ask anyway:
> Does size 2^t m - k ever run slower than size 2^t m?  Than it could help
> to pad out one's operands (for the presumed main usages of this new
> trick Newton, ab-cd with cancellation, etc).

After a quick look, it seems padding is worthwhile up to a limit.
E.g.,

  n = 72 = 2^3 * 9 is faster than n = 80 = 2^4 * 5,
  n = 104 = 2^3 * 13 is faster than n = 112 = 2^4 * 7

so in this ranges, one should not pad to more than multiples of 8. On
the other hand,

  n = 488 = 2^3 * 61 is slower than n = 496 = 2^4 * 31

and n = 496 is faster than n = 512.

It makes some sense to me that for a size where one can recurse k
times before reaching the base case (threshold is 16 on this machine),
one should pad to a multiple of 2^k, but I haven't tried to verify
that scientifically...

Regards,
/Niels