Wieb Bosma's optimal continued fraction algorithm

This algorithm computes the optimal continued fraction expansion of a real irrational number x. It is based on the algorithm in Optimal continued fractions by Wieb Bosma, Indag. Math. 49 (1987) 353-379.

t-1=x
a0=[x], the nearest integer to x
r-1=1, r0=a0
s-1=0, s0=1
t0=x-a0
ε1=sign(t0)
for k≥1:
    bk=⌊|tk-1|-1⌋
    vk=bksk-1+εksk-2
    uk=bkrk-1+εkrk-2
    αk=(vk+sk-1)/(2vk+sk-1)
    ak=⌊|tk-1|-1+1-αk⌋
    rk=akrk-1+εkrk-2
    sk=aksk-1+εksk-2
    tk=|tk-1|-1-ak
    εk+1=sign(tk).

Some properties for k ≥ 1:

  1. x = a0+ ε1/a1+ ε2/a2+ ···
  2. ak ≥ 2.
  3. ak = bk,      if εk+1 = 1;
    ak = bk+1, if εk+1 = -1.
  4. tk = εk+1/ak+1+ εk+2/ak+2+ ···

  5. the k-th complete convergent ξk = εk/tk-1.
  6. rk/sk = uk/vk ⇔ vk|vkx - uk| < (vk+sk-1)|(vk+sk-1)x - (uk+rk-1)|.
  7. sk > sk-1.
  8. ½ < αk < 1.
  9. αk - 1 < tk < αk.
  10. sk|skx - rk| < ½.
  11. -½ < tk < ½(√5 - 1).

Last modified 18th June 2009
Return to main page