Welcome guest
You're not logged in.
302 users online, thereof 0 logged in

Algorithm: Continued Fraction (Python)

Continued Fraction (Python)

Known time/storage complexity and/or correctness

The continued fraction of a real number $x\in\mathbb R$ can be computed by the following algorithm.1

1 Because floating point arithmetic IEEE-754 “double precision”, python doubles contain 53 bits of precision. Therefore, the algorithm not always computes the write values of the continued fraction. The algorithm also limits the computation to 20 values of the continued fraction, since some continued fractions are not finite.

Short Name

$\operatorname{contFrac}$

Input Parameters

real number $x\in\mathbb R$

Output Parameters

continued fraction $[x_0;x_1,x_2,\ldots]$

Python Code

import math

def contFrac(x, k):
    cf = []
    q = math.floor(x)
    cf.append(q)
    x = x - q
    i = 0
    while x != 0 and i < k:
        q = math.floor(1 / x)
        cf.append(q)
        x = 1 / x - q
        i = i + 1
    return cf

# Usage
print(contFrac(math.sqrt(2)))

# will output 
# [1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]

| | | | created: 2019-06-23 17:31:32 | modified: 2019-06-23 19:06:33 | by: bookofproofs | references: [1357], [8186]

1.Proof: (related to "Continued Fraction (Python)")


This work was contributed under CC BY-SA 3.0 by:

This work is a derivative of:

(none)

Bibliography (further reading)

[1357] Hermann, D.: “Algorithmen Arbeitsbuch”, Addison-Wesley Publishing Company, 1992

[8186] Schnorr, C.P.: “Lecture Notes Diskrete Mathematik”, Goethe University Frankfurt, 2001

FeedsAcknowledgmentsTerms of UsePrivacy PolicyImprint
© 2018 Powered by BooOfProofs, All rights reserved.