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]
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. bk ≥ 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 1st April 2008
Return to main page