当你在计算某个数的近似值时🔍，或者在求解某个方程的根时🧮，连分数算法 就像一把神奇的放大镜🔎，能帮你逐步逼近那个隐藏在数字背后的真相。

欢迎来到《密码学核心算法实战》的连分数专题！这里没有纸上谈兵的理论空谈（真的不画大饼😉），只有一把把能直接撬动数据安全的精密齿轮⚙️。

连分数算法的操作 🌟

这个算法可以直接将一个有理数或者无理数直接表示成一个连分数形式，当然因为这个算法的原理十分简单，所以就不单独拿出来讲了，直接进入正题！🤗

输入：一个实数 $x$。
令 $i = 0$，$x_0 = x$

  1. 令 $a_i$ 为 $x_i$ 的整数部分
  2. $b_i = x_i - a_i$，如果 $b_i = 0$，则算法结束
  3. 如果 $bi \neq 0$，则令 $x{i+1} = \frac{1}{b_i}$，$i = i + 1$，回到步骤 1

输出：连分数的部分商 $a_0, a_1, a_2, \ldots$，即 $x = [a_0, a_1, a_2, \ldots]$。

反过来，$x = [a_0, a_1, a_2, \ldots]$ 也可以通过递推关系来计算出 $x$ 的近似值。

设 $x_n = [a_0, a_1, \ldots, a_n]$，则有递推关系：

其中 $p_n$ 和 $q_n$ 分别是 $x_n$ 的分子和分母。
最终，$x_n = \frac{p_n}{q_n}$ 就是 $x$ 的一个近似值。

连分数算法的实现 😎

下面是一个 Python 实现的连分数算法：

def continued_fraction(x, max_iterations=100):
    a = []
    for _ in range(max_iterations):
        ai = int(x)
        a.append(ai)
        x -= ai
        if x == 0:
            break
        x = 1 / x
    return a

def continued_fraction_convergents(coeffs):
    """
    用递推公式计算连分数 [a0,a1,...an] 的所有渐进分数
    参数：
        coeffs: 连分数部分商列表 [a0,a1,a2,...]
    返回：
        list: 每个元素是 (n, p_n, q_n, x_n)，包含每一步的递推结果
    """
    if not coeffs:
        raise ValueError("连分数系数列表不能为空！")
    p_prev_prev = 0  # p_{-2}
    p_prev = 1       # p_{-1}
    q_prev_prev = 1  # q_{-2}
    q_prev = 0       # q_{-1}
    convergents = []  # 存储每一步的渐进分数
    for n, a_n in enumerate(coeffs):
        # 递推计算 p_n 和 q_n
        p_n = a_n * p_prev + p_prev_prev
        q_n = a_n * q_prev + q_prev_prev
        # 计算当前渐进分数 x_n = p_n/q_n
        x_n = p_n / q_n
        # 保存结果（n从0开始）
        convergents.append((n, p_n, q_n, x_n))
        # 更新前两项，为下一次递推做准备
        p_prev_prev, p_prev = p_prev, p_n
        q_prev_prev, q_prev = q_prev, q_n
    return convergents

SageMath 偷懒 🤓👆

有同学说：“博主，博主，你的算法确实很厉害，但是还是太吃操作了，有没有更加简单无脑的用法？”👻
有的，兄弟有的，这样的算法在 SageMath 中早就已经被封装好了🤫，我们直接调用就行了：

from sage.all import continued_fraction
# 这个 continued_fraction 函数既可以计算连分数的部分商，也可以计算连分数的渐进分数，具体用法如下：
# 计算连分数部分商
coeffs = continued_fraction(x)
# 计算连分数的渐进分数
convergents = continued_fraction(coeffs)

怎么样，是不是非常简单？🤣👉🤡

上一章：密码学算法 - Hensel-Lifting算法 👈
下一章：密码学算法 - Wiener算法 👈
回到开始：关于我 👈

相关链接：
密码学数学基础 - 连分数 👈