Toom testing, and unbalanced recursive calls in toom22.
tg at gmplib.org
Mon Oct 19 18:32:48 CEST 2009
nisse at lysator.liu.se (Niels Möller) writes:
Some possible solutions:
1. Have TOOM22_MUL_MN_REC always use basecase for too unbalanced
products (and trust that in practice toom22 will not be called for
sizes where this is a poor choice). Also, for size 2n x n+1, the
most unbalanced case mpn_toom22_mul can handle, that function is
probably not the best choice.
2. Have TOOM22_MUL_MN_REC choose between toom22, toom32 and basecase,
using some conditions.
3. Let TOOM22_MUL_MN_REC use the general mpn_mul function for
unbalanced multiplication. This has implications on the use of
scratch space (as long as mpn_mul doesn't use an itch/scratch
interface, scratch allocated for toom22 will be wasted. And if
mpn_mul is eventually itchified, this gives a rather unpleasant
I think all the other toom functions call mpn_mul for the unbalanced
recursive product, but that overhead is more noticeable for toom22, I
What's reasonable to do?
I don't think toom22 should call mul.c for the point-at-oo evaluation.
The overhead is simply too large for these small operands.
I also don't think (1) is good.
(2) is my favourite.
But except when tuning (as told by TUNE_PROGRAM_BUILD) we can often
exclude various alternatives. For example, if
MUL_TOOM33_THRESHOLD / MUL_TOOM22_THRESHOLD < 2
we know that toom22 will always call mpn_mul_basecase.
But we may also keep the code like it is, and simply forbid the operands
that lead to too unbalanced recursive calls. That's my approach in the
measurement program generating the graphs at gmplib.org/devel/.
This isn't too hard to find out in closed form, I suppose. I was lazy
in the measurement program, and wrote a recursive predicate. It should
be a simple function of MUL_TOOM22_THRESHOLD and (un-vn).
More information about the gmp-devel