Continuous fractions in CAS

[Albert Chan]

(09-23-2020 11:22 AM)pinkman Wrote:  dfc(sqrt(2)) returns [1,2,2,2,2,2,2,2,2,2,2,2,2,2,2] (good!) and dfc(sqrt(2),5) returns... [1,2,[2]]

sqrt(n) has repeating CF coefs is because radical can be flipped to the bottom:

√n = p + (√(n) - p) = p + q / (√(n) + p) = p + 1 / ((√(n) + p)/q)

where p = floor(√n), q = n - p²

If q = 0, n is perfect square, and we are done.
If q = 1, FP((√(n) + p)/q) = FP(√n), thus will repeat itself. (here, FP(x) meant x - floor(x))

Example:

XCas> dfc(sqrt(7),1)       → [2, (sqrt(7)+2)/3]
XCas> dfc(sqrt(7),4)       → [2,1,1,1, sqrt(7)+2]          // q=1, next one will repeat
XCas> dfc(sqrt(7),5)       → [2,1,1,1,4, (sqrt(7)+2)/3] ≡ [2, [1,1,1,4]]

Code:

def CFsqrt(n, repeat=False):    # Generate CF coefs of sqrt(n)
    p = sqrtn = int(n**0.5)
    yield sqrtn                 # 1st continued fraction coef
    q = n - p * p
    if not q: return            # perfect square, nothing to do!
    while q != 1 or repeat:     # q==1 signal recurring about to start
        coef = (sqrtn + p) // q # continued fraction coef
        yield coef
        p = coef * q - p        # update next p and q
        q = (n - p*p) // q
    yield (sqrtn + p) // q      # last repeating coef

>>> list(CFsqrt(7))         # \(\sqrt{7} = [2; \overline{1, 1, 1, 4}]\)
[2, 1, 1, 1, 4]
>>> list(CFsqrt(77))       # \(\sqrt{77} = [8; \overline{1, 3, 2, 3, 1, 16}]\)
[8, 1, 3, 2, 3, 1, 16]