Allocation for toom33

[Torbjorn Granlund]

nisse at lysator.liu.se (Niels Möller) writes:

  Torbjorn Granlund <tg at gmplib.org> writes:
  
  > I checked the measured data to see if toom33 is anytime considered the
  > best function and s + t >= n + 5 does not hold.  Here are the points for
  > a core i7:
  >
  > [...]
  
  One other observation: They all have large s and small t. Is there any
  input sizes where it's optimal to choose a toom varaiant that results
  in a small s?
  
The reason s is large and t is small for toomMN with M=N is that we
don't allow s < t (since we don't allow an < bn for the original operand
sizes).

  Does it ever happen that s <= an - M? If it does, how small can it be?
  Can it ever happen that s < t?
  
I have a very simple program that I recommend that you use, and let it
operate on my measured data.

The program is shell.gmplib.org:~tege/kmes-anal.c.
Data for Core i7 is in shell.gmplib.org:~tege/kmes-15000.i7.

I'll make these publicly available if there is interest.  (Or at least
the beginning of the 2 Gibyte kmes-15000.i7.)

There is a simple loop at the end of the program, with example analyses
for toom33 and toom32.

For toom32 I get these points with small s:

 an  bn    s  t   n
 26  22:   4  11  11
 27  24:   3  12  12
 29  26:   3  13  13
100  95:   4  47  48
100  96:   4  48  48

I get slightly more points with small t:

117  43:  39   4  39
129  46:  43   3  43
130  46:  42   2  44
130  47:  42   3  44
130  48:  42   4  44
131  46:  43   2  44
131  47:  43   3  44
132  46:  44   2  44
132  48:  44   4  44
140  51:  46   4  47
142  52:  46   4  48
143  51:  47   3  48
143  52:  47   4  48
144  52:  48   4  48
166  59:  54   3  56
166  60:  54   4  56
167  58:  55   2  56
167  59:  55   3  56
167  60:  55   4  56
168  59:  56   3  56
168  60:  56   4  56
178  63:  58   3  60
179  63:  59   3  60
179  64:  59   4  60
180  63:  60   3  60
203  72:  67   4  68

Two caveats:

(1) The inf point is still poorly measured... :-) The small s/t
    experiements should have valid measurements since it is
    unquestionable mul_basecase's turf.  But the function over which the
    small s/t function is winning might run too slowly because it ran
    into a mpn_mul stupidity.

(2) Each an,bn point was measured just once.  The measurement program was
    written mainly for generating data for graphs, and I assume the eye
    is a good noise filter.  (It is possible to compile the measurement
    program to make any number of measurements, and then take the median.)

For these reasons, we should draw conclusions cautiously.

-- 
Torbjörn