Niels Möller <ni...@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. _______________________________________________ gmp-devel mailing list gmp-devel@gmplib.org https://gmplib.org/mailman/listinfo/gmp-devel
