toom54

[Niels Möller]

Torbjorn Granlund <tg at gmplib.org> writes:

> Not so sure.  But we can decide to make it that.  It currently is
> fastest for large operands, in a *narrow* space between 43 and 53, and
> its subproducts will want 33.

If so, we have an apparent cycle in the graph,

          toom33
         ^      \
        /        \
       V          V
   toom32  <--->  toom22

For the range where toom32 is (or should be) used, its calls to toom33
shouldn't generate any calls to higher tooms(?). And when toom22 calls
toom32, it also shouldn't call toom33. Hence, tha above subgraph is for
calls to toom32, while for a call to toom22, we only have

   toom32  <--->  toom22

Any moving up, in the general case, I imagine toom33 might at least call
toom43? It's going to be a fairly complicated graph.

I'm also thinking about how to do the itch functions for these
functions, taking all recursive calls into account. I still think we
want closed formulas for the lowest tooms, while that's most likely
*not* practical for the higher ones.

> But first MUL_TOOM43_TO_TOOM54_THRESHOLD needs to be measured and set
> to some default.

I've started to look at tuning. I don't yet understand how the
TOOMX_TO_TOOMY tuning works.

I started by adding MPN_TOOM54_MUL_MINSIZE, and then I noticed that the
corresponding values for toom43 and toom53 are commented with "???" in
gmp-impl.h. Is it correct to use the same value as MIN_AN in the
corresponding testfiles? If so, I think this is the right patch:

diff -r 605ce4a6238b gmp-impl.h
--- a/gmp-impl.h     Tue Feb 14 21:41:21 2012 +0100
+++ b/gmp-impl.h     Wed Feb 15 10:04:32 2012 +0100
@@ -1247,8 +1247,9 @@ typedef struct {
 
 #define MPN_TOOM32_MUL_MINSIZE   10
 #define MPN_TOOM42_MUL_MINSIZE   10
-#define MPN_TOOM43_MUL_MINSIZE   49 /* ??? */
-#define MPN_TOOM53_MUL_MINSIZE   49 /* ??? */
+#define MPN_TOOM43_MUL_MINSIZE   25
+#define MPN_TOOM53_MUL_MINSIZE   17
+#define MPN_TOOM54_MUL_MINSIZE   31
 #define MPN_TOOM63_MUL_MINSIZE   49
 
 #define MPN_TOOM42_MULMID_MINSIZE    4

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.