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

[Niels Möller]

Torbjorn Granlund <tg at gmplib.org> 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.

Regards,
/Niels

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