The Four Meanings of "Accurate to 3 Places"

[Albert Chan]

(12-30-2017 08:10 PM)ttw Wrote:  This recursion is basically x=1/[1/x] where [] means floor is called the Gauss Map. It drifts rather quickly because the error in continued fraction approximation (p/q) is of order 1/q^2 (actually much better). The accuracy of the continued fraction part quickly exceeds the floating point precision of the calculator. The algorithm's greatest strength (good accuracy) tends to make it tricky.

Hi, ttw:

On machine that can produce good modulus, x = 1/fraction(x) error can be removed.

Code:

def genCF(n, d=1):
    "generate continued fraction of n/d (n can be float)"
    while d:
        yield int(n/d)
        n, d = d, n%d

>>> list(genCF(2**0.5))
[1, 2, 2, 2, 2, 2,
2, 2, 2, 2, 2,
2, 2, 2, 2, 2,
2, 2, 2, 2, 2,
1, 1, 1, 2, 7,
1, 2, 33, 2, 7,
5, 2, 1, 1, 16, 2]

Above look bad (exact coefs of sqrt(2) = [1, 2, 2 ...]), but not really.
genCF actually generated correct coefficients.

Python cannot produce 2**0.5 exactly, but as: 12738103345051546 / 2**53 ~ 1.4142135623730951

>>> list(genCF(12738103345051546, 2**53) ### all done in integers
... # exact coefficents as above

You can also confirm this IEEE fraction in Mathematica. It will generate same coefs.

Why the accuracy ?
Because modulus operation is exact, using this algorithm.