Toom-8 testing (mpz level)

[Niels Möller]

Torbjorn Granlund <tg at gmplib.org> writes:

> I am curious about your preference of # of evaluation points that are
> divisible by 4?  Does that have something to do with interpolation
> symmetries...?

It makes sense to me to start with the four "special" points 0,
\infty, +1, -1 (one pair with additive symmetry and one pair with
multiplicative symmetry). And then add points four at a time as +p,
-p, +1/p, -1/p for small integers p > 1, which then has both additive
and multiplicative symmetry).

I imagine p = 2 and p = 4 give easier evaluation (but maybe not
easier interpolation) than p = 3.

On my list of toom stuff I'd like to work on in my copious spare
time, I have:

* Improvements of allocation and code size.

* I'd like to investigate 6-point toom using the points 0, \infty, ±2, ±1/2
  rather than 0, \infty, ±1, ±2 as is used today, to see if symmetries
  can be exploited in a better way.

* Somewhat related, there's an allocation improvement that Marco
  (iirc?) did to matrix22_mul, that I'd also like to integrate).

* Invariance interface, I did some experiments with invariance and
  Karatsuba some years ago (that code could precompute the evaluation
  for an invariant input, including the evaluation for all recursive
  Karatsuba calls). IIRC, that saved some 5-10%. I'd like to dig up
  that code and extend it to handle toom as well. I guess that for a
  start, it will be easiest and most important to focus on the
  balanced case.

Regards,
/Niels