Toom-8 testing (mpz level)
Niels Möller
nisse at lysator.liu.se
Wed Oct 7 14:23:32 CEST 2009
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
More information about the gmp-devel
mailing list