Fast Multiplication

[Marco Bodrato]

Ciao,

Il Sab, 21 Novembre 2015 10:48 am, Torbjörn Granlund ha scritto:
> paul zimmermann <Paul.Zimmermann at inria.fr> writes:
>   I tried with gmp-6.1.0: the smallest value for which "make check" does
>   pass is MUL_TOOM22_THRESHOLD=6.
>
> I wouldn't trust setting the values outside of what we do in
> mpn/minithres/gmp-mparam.h.  There MUL_TOOM22_THRESHOLD is 8.
>
> The smallest value for equal size operands and for differently sized
> operands might not be the same.

Right, toom22 supports equally sized operands of size 4, but there are
problems with unbalanced multiplications.

We may support 5 as a value for the threshold, with a change like:
diff -r 09ec1265bd9f mpn/generic/toom42_mul.c
--- a/mpn/generic/toom42_mul.c  Fri Nov 20 08:16:27 2015 +0100
+++ b/mpn/generic/toom42_mul.c  Sat Nov 21 16:50:10 2015 +0100
@@ -86,4 +86,8 @@
 #define b1  (bp + n)

+  if (UNLIKELY (an == 9) && bn >= 5) {
+    mpn_toom32_mul (pp, ap, an, bp, bn, scratch);
+    return;
+  }
   n = an >= 2 * bn ? (an + 3) >> 2 : (bn + 1) >> 1;

but it's not worth doing... because an odd size hardly is a good threshold
for Karatsuba and supporting also 4 would add to much "noise" to the code.

I changed the MPN_TOOM22_MUL_MINSIZE in gmp-impl.h, to avoid the risk that
tune/tuneup can suggest such a small value.

Regards,
m

-- 
http://bodrato.it/