Toom testing, and unbalanced recursive calls in toom22.
Torbjorn Granlund
tg at gmplib.org
Tue Oct 20 15:09:36 CEST 2009
nisse at lysator.liu.se (Niels Möller) writes:
When I proposed to simply use mul_basecase, that was on the theory
than the difference between basecase and the best algorithm would
likely be very small over the range of practical interest. (And then I
don't care if basecase is highly sub-optimal for untypical sizes used
by the toom22 testcases).
I see. Perhaps that is indeed true.
A related question is, should we call toom22 for known-suboptimal
operands?
No...it is nice that you begin to understand the GMP philosophy. :-)
But when choosing algorithm, we will probably need to do some
simplifying compromises. For many areas, the difference of the best and
2nd best algorithms will be close to zero. If we can identify those,
and thereby make the shapes easier to manage, then we should do that.
We need to figure out where the border between toom22 and
toom32 is (and hopefully, also rule out use of e.g., toom42 for the
recursive call),
Yes.
My measurement program (the graph-generating one) completely botched the
point at oo. The program built a complete table of sizes and best
algorithm + speed (plus 2nd best, plus current mul.c speed), which could
have been used for the multiplication for the oo point. Alas, that
would have required modification of each toom function, to make them
look in my table.
--
Torbjörn
More information about the gmp-devel
mailing list