Skip to content

Instantly share code, notes, and snippets.

@nadavrot

nadavrot/continued_fractions.py

Last active November 24, 2022 00:20
Show Gist options
  • Save nadavrot/d63234e14e92327e54fce224ea662589 to your computer and use it in GitHub Desktop.
Save nadavrot/d63234e14e92327e54fce224ea662589 to your computer and use it in GitHub Desktop.
Download ZIP
Approximate irrational numbers with a fraction
Raw
continued_fractions.py
https://en.wikipedia.org/wiki/Continued_fraction
from math import trunc, pi, sqrt
def approximate(alpha, iters):
r = [alpha]
a = []
for i in range(iters):
a.append(trunc(r[-1]))
r.append(1/(r[-1] - a[-1]))
P = [a[0], a[0]*a[1] + 1]
Q = [1, a[1]]
for i in range(2, iters):
P.append(P[-1] * a[i] + P[-2])
Q.append(Q[-1] * a[i] + Q[-2])
return P[-1], Q[-1]
P, Q = approximate(sqrt(2), 5)
print("%d/%d = %f" % (P, Q, float(P)/Q))
P, Q = approximate(pi, 5)
print("%d/%d = %f" % (P, Q, float(P)/Q))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment