[tom at womack.net: More exploration of the Kertesz problem]

[Paul Zimmermann]

For those of you who are not on the number theory list, this is advertisement
for GMP.

Paul Zimmermann

------- Start of forwarded message -------
Approved-By:  "Victor S. Miller" <victor at IDACCR.ORG>
Date:         Tue, 24 Apr 2007 17:56:01 -0400
Reply-To:     Tom Womack <tom at womack.net>
Sender:       Number Theory List <NMBRTHRY at LISTSERV.NODAK.EDU>
From:         Tom Womack <tom at womack.net>
Subject: More exploration of the Kertesz problem
To:           NMBRTHRY at LISTSERV.NODAK.EDU
List-Owner: <mailto:NMBRTHRY-request at LISTSERV.NODAK.EDU>

This turns out to be a very good test of whether the manufacturer of
your multi-precision arithmetic package bothered to optimise bignum
division and GCD in the case where the result is large ... in
particular, running 2131/2713 did not complete after several hours using
Pari-GP 2.3.1, and took about 13.5 seconds to complete 29 steps and
reach the 69154989-digit final denominator when I recoded using
gmp-4.2.1.

For denominators less than 10^4, nothing takes more than the 29 steps of
2131/2713, or has a final denominator of more than the 364594641 digits
of 373/6893.

The gmp code is http://www.chiark.greenend.org.uk/~twomack/guyprob.cpp
(you'll want to compile with gmp>=4.2.0 to get the sub-quadratic
division), and the incremental milestones from a run up to denom=10000
are at http://www.chiark.greenend.org.uk/~twomack/guyprob.out .

Tom
------- End of forwarded message -------