Iterative Toom-Cook-2.5 (Toom32) method for unbalanced multiplication

[Torbjorn Granlund]

nisse at lysator.liu.se (Niels Möller) writes:

  Torbjorn Granlund <tg at gmplib.org> writes:
  
  > This could be avoided by making the
  > interpolation code understand the situation; it could add instead of
  > writ the low n product limbs.  Do you do that?
  
  I suspect that's tricky. The lowest part of the product comes from the
  multiplication at the zero point, basically mul_n (or some perfectly
  balanced toom). And at least for the interpolation functions I've read
  or written, that's computed into the low end of the product area.
  
Writing it there is pessimal.  We want that part either added (best) or
put someplace else, in a separate result variable.

  So one would really need something like addmul_n (this issue turns up in
  several places. In the toom functions, where it would be useful at least
  for the multiplications at the infinity point (if it can be added in one
  can do that product, saving some storage and combining one addition with
  the multiplication), as well as when iterating a multiplication
  primitive such as toom32 or basecase.
  
I suppose we could consider this for *small* m,n.  That's where it can
save some time.  For large operands, I suspect we'll end up with massive
code duplication.  (Alternatively, we could implement mul_n as MPN_ZERO
+ addmul_n..., or what you seem to suggest: a generalisation where we
add a size parameter for which part to add, shich part to just store.)

-- 
Torbjörn