Iterative Toom-Cook-2.5 (Toom32) method for unbalanced multiplication
tg at gmplib.org
Tue Dec 22 20:07:48 CET 2009
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.)
More information about the gmp-devel