Releasing Toom-8.5 (mpn level)

[Niels Möller]

bodrato at mail.dm.unipi.it writes:

> I say it is very conservative, because toom8h exists... and e.g. on my
> laptop the ranges for the different balanced Toom are:

Bounding the log term (i.e. recursion depth) by GMP_NUMB_BITS is very
conservative. For all but the smallest toom-functons, it might make
sense to get a more precise bound, involving a term like

  floor (log_2 (floor(n-1) / (THRESHOLD-1))).

log_2 can be computed using count_leading_zeros, or for constants one
can use some large conditional expression.

> 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.

I'd guess this situation is not uncommon.

/Niels