Wraparound multiplicaton vs mullo
Torbjorn Granlund
tg at gmplib.org
Fri Oct 23 10:26:05 CEST 2009
nisse at lysator.liu.se (Niels Möller) writes:
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...
Could padding perhaps be made while recursing, not all at the beginning,
at top-level to the left and later as needed the right? Padding to the
right can simulate computing modulo B^m+1 when we actually compute
B^{m+k}+1, I think.
--
Torbjörn
More information about the gmp-devel
mailing list