Releasing Toom-8.5 (mpn level)

[bodrato at mail.dm.unipi.it]

Thanks Niels,

>> Suggestions? Should I add toom44_itch() computed on the threshold point?
>
> Something like that, yes.

Ok, so, a very conservative definition can be:

#define mpn_toom6h_mul_n_itch(n)					\
( ((n) - MUL_TOOM6H_THRESHOLD)*2 + GMP_NUMB_BITS*6 +			\
   MAX(MUL_TOOM6H_THRESHOLD * 2,					\
       mpn_toom44_mul_itch(MUL_TOOM6H_THRESHOLD, MUL_TOOM6H_THRESHOLD)))

It is complex, but the compiler should shrink it to (n*2+CONST) and I hope
it keeps on being correct even if the memory usage by toom44 will be
reduced below (n*2).

> When you derive the itch function for toom66, you need to take into
> account that when recursing, you sooner or later get a multiplication
> below the toom66 threshold and recurse to toom44, and then the scratch

I say it is very conservative, because toom8h exists... and e.g. on my
laptop the ranges for the different balanced Toom are:
  Toom-2 [ 20.. 76]
  Toom-3 [ 77..182]
  Toom-4 [183..250]
  Toom-6 [251..379]
  Toom-8 [380..14000+]
and 251/6 = 41; 380/6+2=65 ... this means that on this machine, the
balanced Toom-6 shall _always_ use Toom-2 for recursion.

By the way, both Toom-3 and Toom-4 always use Toom-2 for recursion with
the ranges above...
... maybe this means that the upper threshold for Toom-8 is expected below
(76-1)*8 = 600  ;-)

Regards,
Marco

-- 
http://bodrato.it/