Simplification of "reciprocal word 3by2" (aka invert_pi1)

Paul Zimmermann Paul.Zimmermann at inria.fr
Sat Jun 20 05:53:03 UTC 2020


       Dear Pawel,

> Thanks for checking this out Paul.
> 
> Are you able to generate any counter-example for beta=2^64?

yes: d1=9223372036855824384 d0=9223374235880128513.

Please can you confirm? This should be the smallest solution (by d1*2^64+d0).

How did I? I wrote a SageMath program that for each d1 computes the ranges
of d0 values that correspond to the same final value of v after line 9.
Then I kept ranges of d0 that give p < t1 at line 12, and for which
(beta+v-1)*(d1*(v-1)+d0) >= beta^3, which is the condition for the second
adjustment at line 15. It then remains to check the smallest d0 of each range.

Paul


More information about the gmp-discuss mailing list