Toom-8 testing (mpz level)
bodrato at mail.dm.unipi.it
bodrato at mail.dm.unipi.it
Wed Oct 7 15:37:41 CEST 2009
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/
More information about the gmp-devel
mailing list