What's a reasonable size ratio for toom32?

[Niels Möller]

Niels Möller <nisse at lysator.liu.se> writes:

> I'm having some difficulty with the intuition,
> perhaps it would help to draw the diagrams of ratio for unbalanced sub
> product as a function of the input ratio, for both toom22 and toom32

I've done a bit of the math. If input ratio is 1/2 <= r <= 1, then for
Toom22, the "output" ratio, i.e., the ratio for the unbalanced multiply
is

  r' = 2r - 1

For Toom32, the output ratio is

  r' = min(3r - 1, 2/r - 2)
 
If we want to avoid getting down to 1/2, we can chose the algorithm with
highest r'. Then the cross over is at 
 
  r = (sqrt(17) - 1) / 4 \approx 0.781 \approx 32/41

corresponding to 

  r' = (sqrt(17) - 3) / 2 \approx 0.562

So that would be a better cutoff ratio than 4/5, and be sufficient to
maintain the invariant r > 0.56. Which may make a difference, because
the r' \ approx 0.562 isn't that bad a fit for toom32, the next recursion
level gets r'' = (3 sqrt(17) - 11) / 2 \approx 0.685, which is close to
ideal for Toom32. (While for ratios very close to 1/2, we have r = 1/2 +
\epsilon ==> r' = 1/2 + 3 \epsilon, so we can stay with a pretty bad
ratio for several iterations.

For completeness, using the twice repeated Toom22 method when r is close
to 1/2 gives r' = (1-r) / r = 1/r - 1, but not obvious what's a reasonable
threshold if we want to add that method to the mix.

And I don't see a way to avoid getting down to r \approx 0.562 for some
inputs, we would need to use something different from Toom22 or Toom32
when ratio is close to 0.78, and I don't know what that could be, Toom43
has likely way too much overhead to be a good choice.

Regards,
/Niels

-- 
Niels Möller. PGP key CB4962D070D77D7FCB8BA36271D8F1FF368C6677.
Internet email is subject to wholesale government surveillance.