从 gcd 到 ChatGPT

Algorithm 从哪里来？

这个词来自 9 世纪数学家 al-Khwārizmī 名字的拉丁化形式。他用阿拉伯语写作；名字与花剌子模地区有关，不能据此把“阿拉伯语作者”直接等同于“阿拉伯人”。

他的印度计数法著作以拉丁文版本流传，常见题名为 Algoritmi de numero Indorum。它不是原作的阿拉伯文书名。[2]

今天先问这五件事

输入是什么？输出是什么？
每一步是否明确？
是否能在有限步内结束？
每一步是否能实际执行？

本讲先讨论求解有限输入、需要终止的计算任务。“规则明确”不等于“每次走同一条路径”：随机算法也可以有明确规则。[3]

训练 · 学出参数

1. 数据批次
2. 前向计算
3. 计算损失
4. 更新参数

以自回归语言模型预训练为例：根据前文预测后续 token，衡量预测的误差，再用优化算法调整参数。[5]

指令微调、偏好学习等后训练还有其他数据和目标；“下一个 token 预测”不能概括全部训练。[6]

推理 · 生成文本

1. 已有 token
2. 下一个 token 的分布
3. 选择 token
4. 加入上下文

然后继续下一轮，直到模型结束输出或触发长度上限等停止条件。选择可以包含采样；token 也不一定是一个完整的词。

这是自回归文本生成的简化模型；通常不会在每轮生成时更新模型权重。工具调用与多模态产品还包含额外过程。

例如：26 和 6

26 的正因数：1、2、13、26
6 的正因数：1、2、3、6
共同的正因数：1、2

答案为什么存在？

1 总是公约数，所以候选集合非空。所有正公约数都不超过 min(a, b)，所以候选集合有限。非空的有限集合一定有最大值。

算法内部会出现 0，约定 gcd(a, 0) = a（a > 0）。本讲不处理 gcd(0, 0)。

数学表达

自然语言：用 b 替换 a，用余数替换 b。反复执行，直到 b 变为 0，返回 a。

伪代码

GCD(a, b):
    while b ≠ 0:
        (a, b) ← (b, a mod b)
    return a

括号表示同时赋值：右边的两个值都用更新前的 a、b 计算。即便输入 a < b，这个取余版本也能工作。

当 b > 0 时，下一轮的第二个数是余数 r。

因此，每轮的第二个数都严格变小，又不会小于 0。它必然在有限步后到达 0。

结束时有 (a, 0)，答案就是 a。再结合“每轮 gcd 不变”，算法正确性才完整。

先把两个数排成 a ≥ b。只要 b > 0，就用 a − b 替换较大的数，再排一次。

相同的“公约数不变”证明仍然成立。每次减法后 a + b 严格变小，因此也会结束。

相等时也要继续：例如 (2, 2) → (2, 0)。这补齐了笔记中严格大于、小于分支遗漏的边界。

GCD_SUB(a, b):
    (a, b) ← (max(a,b), min(a,b))
    while b ≠ 0:
        a ← a − b
        if a < b:
            swap(a, b)
    return a

取余把“反复减去 b，直到余数小于 b”合并成一次算术操作。

取余法：2 次取余。
减法：7 次减法。
两种算法都正确，但操作次数不同。

换成 (9999, 1)，差别会更明显：1 次取余，对比 9999 次减法。

“一步”的代价，也要定义

取余和减法不一定花相同时间。大整数的一次运算，成本还与数字的位数有关。

要分析复杂度，先说明：输入规模怎么量？基本操作是什么？比较最坏情况、平均情况，还是某个具体输入？