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

[Niels Möller]

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.

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 think a general addmul would be worth investigating (it can be more or
less general, with the size of the part to be added in being an
independent parameter, or tied to the size of one of the factors). For
mul_basecase, it's (in the easiest case) just a matter of replacing the
first mul_1 by an addmul_1. There's going to be some more bookkeeping to
do it for toom and fft, but my gut feeling is that it shouldn't be that
big a deal.

Regards,
/Niels

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.