Toom testing part II: Infinity point in toom44.

[Niels Möller]

I noticed that mpn_toom44_mul breaks when input sizes are an = bn =
13, and MUL_TOOM44_THESHOLD >= 4*MUL_KARATSUBA_THRESHOLD.

In this case, MAYBE_mul_basecase is false, so that the macro
TOOM44_MUL_N_REC never calls basecase. However, the infinity point
product is computed using

    TOOM44_MUL_N_REC (vinf, a3, b3, s, tp);	/* vinf, s+t limbs */

where s = 1. The multplication is passed on to mpn_toom22_mul, which
crashes with single limb inputs.

This problem disappears for larger inputs 13, but it can reoccur for
larger sizes if also MAYBE_mul_toom22 is false.

For a general balanced invocation of mpn_toom44_mul, an = bn = n, also
the multiplication at the infinity point is balanced, and of size n -
3 ceil(n/3) >= (n-9)/4.

So for correctness, I think the definitions of the MAYBE macros should
be changed to

#define MAYBE_mul_basecase						\
  (MUL_TOOM44_THRESHOLD < 9 + 4 * MUL_KARATSUBA_THRESHOLD)
#define MAYBE_mul_toom22						\
  (MUL_TOOM44_THRESHOLD < 9 + 4 * MUL_TOOM33_THRESHOLD)
#define MAYBE_mul_toom44						\
  (MUL_FFT_THRESHOLD >= 9 + 4 * MUL_TOOM44_THRESHOLD)
#endif

or perhaps with logic like this only for the multiplication at the
infinity point, and the original logic for the other points.

Also, it seems that an underlying assumption here is that toom44_mul
need not return correct results for input sizes below
MUL_TOOM44_THRESHOLD (since it might then call toom22 or toom33 with
too small inputs). Is that intended?

I think toom33 has the same issues, even though I haven't been able to
trig that.

I'd prefer toom33 and toom44 to work and give the correct results for
all input sizes that can be chopped up in the intended way (possibly
with some additional condition limiting how unbalanced the inputs may
be, e.g., like s + t >= n + 17), even if they need not be optimized
for operation outside of the ranges where they're used by the higher
level multiplication functions. Torbjörn might not agree, I guess.

The interface details obviously has implications for how these
functions are tested.

Regards,
/Niels