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

[bodrato at mail.dm.unipi.it]

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/