Toom-8 testing (mpz level)

bodrato at bodrato at
Wed Oct 7 15:37:41 CEST 2009


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

Torbjorn is a clever guy :-)
You know I tried a program generating code, but it was buggy. Then I
decided to use the few free time for some sparse results...

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

Exactly, the symmetry is very attractive. The "half less" versions will be
obtained avoiding the evaluation in \infty. I mean, with the Toom-6.5 I
want to obtain toom76, 66, 85, 75, 94, 84, A3, 93, B2, A2.

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

... it depends... evaluation in {1,2,3} can be easier than {1,2,4} for a
degree 2 polynomial ;-)

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

Yes, you remember correctly, it was me :-) It was a "side effect" of my
work on Strassen's matrix-matrix multiplication:

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

A balanced case with one invariant operand can be used for the very
unbalanced. By keeping the smaller operand invariant and multiplying by
slices of the longest one...



More information about the gmp-devel mailing list