A simple continued fraction is a complex rational expression that looks like this:
1
x = a0 + ————————————————————
1
a1 + ———————————————
1
a2 + ——————————
a3 . . .
The quantities ai are called partial quotients. The rational number obtained by
including n terms of the continued fraction is called the nth convergent. Every
irrational number can be represented as an infinite continued fraction. As n increases,
the nth convergent becomes an increasingly precise rational
approximation to an irrational number.
The partial quotients, ai, for a simple continued fraction can be determined using the recursion:
Where,r0 = x rn = 1/(rn-1 - an-1)
The convergents are defined as cn = pn/qn. The initial terms pi, qi are set to:an = floor(rn)
This allows us to compute subsequent terms from the recursion using:p-2 = 0, q-2 = 1 p-1 = 1, q-1 = 0
Then we get for n = 0,pn = an·pn-1 + pn-2 qn = an·qn-1 + qn-2
A procedure written in the Zeno programming language to compute a sequence of partial quotients and convergents.p0 = a0 q0 = 1
procedure fraction(x : real)
var a, p, p1, p2, q, q1, q2 : int
var r : real
% initialize
r := x
p2 := 0
q2 := 1
p1 := 1
q1 := 0
while true
% compute partial quotient and convergent
a := floor(r)
p := a*p1 + p2
q := a*q1 + q2
put (p/q):20:14, " = ", p, "/", q
% finished when desired precision reached
exit when abs(p/q - x) < 0.0000000001
% advance
r := 1/(r - a)
p2 := p1
q2 := q1
p1 := p
q1 := q
end while
end procedure
Sample output for π = 3.1415926535897932384626433832795
3.00000000000000 = 3/1
3.14285714285714 = 22/7
3.14150943396226 = 333/106
3.14159292035398 = 355/113
3.14159265301190 = 103993/33102
3.14159265392142 = 104348/33215
3.14159265346744 = 208341/66317
3.14159265361894 = 312689/99532