Iterative Toom-Cook-2.5 (Toom32) method for unbalanced multiplication
bodrato at mail.dm.unipi.it
bodrato at mail.dm.unipi.it
Mon Jan 4 12:36:07 CET 2010
Ciao,
> void
> mul_invariant (mp_ptr rp, mp_srcptr up, mp_size_t un, mp_srcptr pe,
> mp_srcptr vp, mp_size_t vn);
>
> Multiplies u times v, using the previously precomputed data pe
> corresponding to u. v can be of arbitrary size, but the precomputed data
> is used only as long as the size of v fits the algorithm choices
> corresponding to the precomputation.
The whole infrastructure seems interesting, but some more flexibility is
needed, I think.
When you precompute the evaluation on {up,un}, you must fix a splitting n.
Once the number n is fixed, you are not forced to use a single algorithm,
you can use many.
I try to explain with a small example. You code says:
case MUL_EVAL_TOOM23:
{
n = MUL_EVAL_N (pe);
if (vn <= 2*n || vn > 3*n)
goto mul_eval_general;
Why?
If vn <= 2*n, you can use toom22; you have all the evaluated values you need.
On the other side, if vn > 3*n but vn < 4*n, one can use toom42, simply
adding the evaluation in (2) to the precomputed ones. If vn>4*n, iteration
probably is the answer.
We do not need to remember the algorithm we pre-evaluated for, but only
the number of slices we divided the number into, and the values we have.
If we can have a dynamical list of values and update it on the fly, it's
better.
E.g. if you take a number {up,un} and pre-evaluate it with n=un/3, for the
values +/-1, +/-2, then you can use this number in any toom32, toom33 or
toom34 product; if you need a toom36 product, you can add evaluations in
+/-(1/2), after this update you will have a wider range of acceptable
shapes, but you do not lose the smaller ones...
Happy new year to everyone who reads!
Marco
PS: I know, toom63 currently uses +/-4, not +/-(1/2)...It can be changed:)
--
http://bodrato.it/papers/
More information about the gmp-devel
mailing list