Toom-8 testing (mpz level)

[bodrato at mail.dm.unipi.it]

Hi!

>> 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:
http://bodrato.it/papers/#Strassen

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

Regards,
Marco

-- 
http://bodrato.it/