连分数算法

连分数算法
术语名称	连分数算法
英语名称	continued fraction algorithm

连分数算法指把一个实数转化为连分数的算法。

算法

对给定实数 [math]\displaystyle{ a }[/math] ，有

1. 令 [math]\displaystyle{ i \leftarrow 0 }[/math] ，
2. 令第 [math]\displaystyle{ i }[/math] 个部分商 [math]\displaystyle{ a_i = \lfloor a \rfloor }[/math] ，
3. 计算 [math]\displaystyle{ a - a_i }[/math] ，如果为 0 终止循环
4. 令第 [math]\displaystyle{ i+1 }[/math] 个完全商 [math]\displaystyle{ b_{i+1} = \frac{1}{a - a_i} }[/math]
5. 令 [math]\displaystyle{ a\leftarrow b_{i+1}, i \leftarrow i + 1 }[/math] ，回到第 2 步。

连分数
基本定义	连分数（简单、普通、广义；有限、无限）	连分数算法
部分结构	渐近分数	完全商
分类	有限连分数	循环连分数、无限不循环连分数
最佳有理逼近
用连分数逼近	渐近分数	半渐近分数
用中间分数逼近	Farey 数列	Stern–Brocot 树