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

[Niels Möller]

bodrato at mail.dm.unipi.it writes:

> 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'm not sure what the typical uses of the invariance functions will be,
but I imagine fixed sizes will be an important special case. My
intention has been to do all of the algorithm choice logic up front, in
the precomputation function. Two use cases I'm aware of are

* iterated 3x2 and the like, where the size of the non-invariant number
  will be the same for all but the last multiply, and

* matrix22_mul which does two multiplications involving each number,
  both with the same sizes (and which doesn't fit the interface in my
  code since one would want to view both factors as "invariant"). This
  is pretty small amount of invariance, but at least when I tried it
  with my small-prime fft code, it gave a modest saving in the fft range
  (threshold to Strassen multiplication was around 1000 limbs on
  x86_64).

>       case MUL_EVAL_TOOM23:
>         {
>           n = MUL_EVAL_N (pe);
>           if (vn <= 2*n || vn > 3*n)
>             goto mul_eval_general;

> 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.

If we try to be smart here, I imagine there may be sizes where we could
use the evaluated points (and corresponding splitting n), but where it
would be better to use a different split? I can't come up with an
example right now, though.

> If we can have a dynamical list of values and update it on the fly, it's
> better.

In earlier discussions on invariance, the plan has been to not do
anything automatically like that (at least not for the lowest level
invariance interface). The user has to specify up front (preferably in a
high level way) what invariance information should be used.

So rather than caching evaluated values, I'd prefer a generalization
where one can say "I'm going to multiply this particular number with
some numbers of size in the range n_min, ... n_max", and then precompute
everything that's useful somewhere within that range. An invariance
function like that can also decide to use several different splits of
the given number, to cover the range in a better way.

Regards,
/Niels

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