Toom testing, and unbalanced recursive calls in toom22.
Paul.Zimmermann at loria.fr
Mon Oct 19 16:15:52 CEST 2009
> From: nisse at lysator.liu.se (Niels =?iso-8859-1?Q?M=F6ller?=)
> Date: Mon, 19 Oct 2009 15:56:43 +0200
> I'm working on improved testcode for the toom functions, and I've
> discovered the following problem with toom22:
> Say mpn_toom22_mul is called with inputs of size an = 178, bn = 89.
I guess you mean an = 178, bn = 118 from the numbers below.
> Then this will be split in pieces as follows,
> a = a0 + a1 * B^89
> b = b0 + b1 * B^89
> where a0, a1 and b0 are of 89 limbs each, and b1 is shorter, only 29
> Then there's the unbalanced recursive call to compute a1 * b1. Since
> the size of b1 is larger than the Karatsuba threshold (20 on the test
> machine), it recurses to toom22_mul; this is the logic of the
> TOOM22_MUL_MN_REC macro. But toom22_mul can't handle a 89 x 29
> product, and things fall apart.
> Some possible solutions:
> 1. Have TOOM22_MUL_MN_REC always use basecase for too unbalaned
> 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 multiplicaton. 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
> circular dependency.
another solution is to (pseudo-)multiply b by B^30, then b0 and b1 have both
59 significant limbs. See Section 1.3.5 of . This will keep the unbalanced
ratio between a and b for a0*b0 and a1*b1.
 Modern Computer Arithmetic, Richard Brent and Paul Zimmermann, version 0.3,
June 2009, http://www.loria.fr/~zimmerma/mca/mca-0.3.pdf.
More information about the gmp-devel