Wraparound multiplicaton vs mullo

[Torbjorn Granlund]

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