Branches History Index

◀ ▲ ▶Branches / Theoretical-computer-science / Semi-numerical-algorithms / Algorithm: Continued Fraction (Python)

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

Algorithm: Continued Fraction (Python)

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)))

  1. will output
  2. will output

Table of Contents

Proofs: 1

Mentioned in:

Definitions: 1

Thank you to the contributors under CC BY-SA 4.0!

Github:
bookofproofs

References

Bibliography

  1. Hermann, D.: "Algorithmen Arbeitsbuch", Addison-Wesley Publishing Company, 1992
  2. Schnorr, C.P.: "Lecture Notes Diskrete Mathematik", Goethe University Frankfurt, 2001

Footnotes

  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. ↩