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

Niels Möller nisse at
Tue Dec 22 22:20:54 CET 2009

Torbjorn Granlund <tg at> writes:

> I suppose we could consider this for *small* m,n.  That's where it can
> save some time.

A start would be to do it for basecase, and make sure that the interface
is good enough that one can get rid of the annoying copies in the un >>
MUL_BASECASE_MAX_UN > vn case in mpn_mul.

> For large operands

I'm not sure about savings here. During the work with small-prime fft,
it seemed like the final O(n) reconstruction work was quite important.
If one can do an extra addition on the fly at small extra cost there,
one saves one pass over the data, for a * b + c operation. So I wouldn't
be surprised if that can give a modest speedup to a * b + c
operations in the low end of the fft range.

> (Alternatively, we could implement mul_n as MPN_ZERO
> + addmul_n...,

Or mul_1 + addmul, to do a little useful work while filling the area.
But that's still not very good as a general solution.


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

More information about the gmp-devel mailing list