Wraparound multiplicaton vs mullo
Niels Möller
nisse at lysator.liu.se
Thu Oct 22 22:28:31 CEST 2009
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
More information about the gmp-devel
mailing list