第二季 · 第 31 章

两千年前的除法

《算法的故事》第二季 · 当算法走进真实世界——欧几里得与算法的起点公元前300年前后，亚历山大城。在没有计算机、没有编程语言，甚至没有现代代数符号的年代，一套只需要反复做减法的计算方法，已经能够解决一个重要的数学问题。两千多年后，当人类开始制造电子计算机，这套方法几乎不需要改变，就可以重新运行在硅芯片上。它叫作欧几里得算法。而它真正令人惊叹的地方，并不是能够求出一个数字，而是人们已经能够严格证明：为什么这样的计算一定能够得到正确答案。

序幕：两根无法直接比较的木尺

想象这样一个场景。地中海东岸，阳光穿过一间古代作坊的门廊。桌面上放着两根木尺，一根长252个单位，另一根长105个单位。一名工匠正在为某座建筑制作装饰构件。他需要找到一个合适的长度，使这个长度能够整齐地量尽两根木尺，不留下任何零碎部分。当然，他可以选择长度为1的单位尺。可是那太短了。工匠想找到的是能够同时量尽两根木尺的最长单位尺。他先拿起长105的尺，沿着长252的木尺连续比量。量了两次，还剩42。他又尝试用剩下的42去量105。能够量两次，还剩21。最后，用21去量42，刚好两次，一点不剩。问题解决了。他需要的最长单位尺是21。

一次测量，三次寻找示意图：252 = 105 + 105 + 42；105 = 42 + 42 + 21；42 = 21 + 21。

这似乎只是一个普通的测量问题。但是仔细想一想，它隐藏着三个了不起的事实。第一，工匠不需要逐一尝试从1到105的所有长度。第二，每完成一次测量，接下来需要处理的问题都会变得更小。第三，当最后一个余数消失时，答案就出现了。这三个事实，构成了一套古老算法的基本骨架。不过，这个故事还有一个更重要的问题。为什么这样做一定是对的？如果有人不相信21就是最长的共同单位，他该怎样证明？如果换成两个极大的数字，这个方法还会有效吗？如果两根尺子的长度不是整数，结果又会怎样？这些问题将把我们带到一个真正存在过的古代数学世界。史实说明：上述工匠、作坊及252与105的木尺均为教学性场景重构，并非有文献记载的历史事件。真正的史实依据，是《几何原本》第七卷关于最大公度数的命题。

第一幕：亚历山大城，一座知识汇聚的城市

《几何原本》存世的早期纸草文献残片之一，约公元75—125年，内容属于第二卷命题5，并非本章算法所在的第七卷，更不是欧几里得本人手稿。^{[Mathematical Association of America][个人数学网站]}公元前331年，亚历山大大帝在埃及北部建立了一座城市。这座城市以他的名字命名：亚历山大城。此后的几十年里，随着希腊化世界的形成，亚历山大城逐渐成为地中海地区重要的政治、商业与学术中心。来自不同地区的商人、学者和工匠在这里汇聚。人们研究天文，研究医学，研究地理，也研究数学。古希腊数学已经积累了数百年的探索成果。泰勒斯、毕达哥拉斯学派、希波克拉底、欧多克索斯等名字，代表着不同阶段的数学传统。人们知道了许多关于图形和数字的性质，但这些知识并不天然构成一个统一、严密的体系。有些结论依靠图形直觉。有些结论拥有相当复杂的证明。还有许多问题需要将不同研究者的成果联系起来，才能形成完整的知识结构。就在这样的历史背景下，一位名叫欧几里得（Euclid）的数学家，完成了一项影响深远的工作。他整理并系统化了当时的数学知识，形成了十三卷本的《几何原本》（Elements）。我们今天习惯称他为“几何学之父”，但实际上，关于他的个人生活，可靠的资料非常少。我们不知道他确切出生于哪一年，也无法准确复原他的求学经历。后来的数学家普罗克洛斯（Proclus）记载，欧几里得活跃于托勒密一世统治时期，整理了欧多克索斯、泰阿泰德等前人的研究成果。这意味着，他并不是凭空创造整套古希腊数学。他的伟大贡献之一，是把已有的知识组织成能够逐步推演的逻辑体系。^{[Euclid][MacTutor History of Mathematics][MacTutor History of Mathematics]}这件事的重要性，比表面看起来还要大。假设你拥有一千个数学结论。如果这些结论只是散落在不同手稿里，它们不过是一千个彼此分离的知识点。但如果能够明确指出哪些结论建立在哪些定义之上，哪些定理能够推出其他定理，这些知识就变成了一个可以不断向外生长的逻辑系统。《几何原本》正是这样一部著作。它从定义、公设和基本命题出发，逐步构造越来越复杂的数学结论。其中不仅有点、线、面和立体，也有整数、比例、素数，以及数与数之间的关系。我们要寻找的算法，就藏在第七卷里。

一项已经存在两千多年的命题

第七卷命题1讨论两个互素数的判定；命题2则提出：对于两个不互素的数，找出它们的最大公度数。用今天的话来说，就是求两个整数的最大公约数。命题的证明使用了一个关键过程：不断从较大的数中减去较小的数，直到得到能够整除前一个数的余量。这里必须说明一个容易被现代教材掩盖的历史细节。《几何原本》中描述的是连续减去较小数的过程，而不是直接写出我们今天熟悉的 % 取余运算符。现代的辗转相除法，是这一过程更简洁的计算表达。另外，《几何原本》第七卷还沿用了古希腊数学对“单位”和“数”的区分。若最终得到单位1，对应的是两数互素的情形。因此，不能把现代程序的每一处定义直接套回古代文本。这些区别不影响我们今天使用算法，却能帮助我们理解它最初的数学背景。^{[Propositions][Clay Mathematics Institute]}让我们现在离开宏大的历史背景，回到两个简单的数字。252。105。看看一项两千多年前的数学思想，究竟是怎样工作的。

第二幕：每减去一次，答案就更近一步

最直接的求解方式，当然是列举。252有哪些约数？105又有哪些约数？把两份名单进行比较，找出共同出现的那些数字，再选择其中最大的一个。这显然能够完成任务。但是，如果数字变得极大呢？如果两个数拥有数百位，我们还要把可能的约数逐个列出来吗？换一种思路。不要先问：“它们共同拥有多少个约数？”而是问：“如果较小的数不能整除较大的数，那么剩下的部分，会不会保留我们想要寻找的信息？”这就是算法的转折点。

第一次缩小问题

现在有两个数：

252,\quad105

我们从252中减去105：

252-105=147

于是，原来的问题变成：

\gcd(147,105)

这里的

\gcd

是英文 greatest common divisor 的缩写，即最大公约数。为什么能够这样替换？假设某个整数

d

能够同时整除252和105。既然252可以写成若干个

d

相加，105也可以写成若干个

d

相加，那么252减去105之后，剩下的147也一定能够被

d

整除。反过来也一样。如果

d

能够同时整除147和105，那么它自然能够整除两者的和252。因此：

\gcd(252,105)=\gcd(147,105)

我们没有计算出答案。但我们成功地把一个较大的问题，变成了一个较小的问题。更重要的是，这种变换不会改变答案。

第二次缩小问题

147仍然大于105。继续减去105：

147-105=42

于是：

\gcd(147,105)=\gcd(105,42)

接着，105减去42：

105-42=63

63仍然大于42，再减一次：

63-42=21

现在剩下42和21。42减去21，得到21。两个数字终于相等了。

\gcd(21,21)=21

整个计算可以写成一条不断缩小的链：

\begin{aligned} (252,105)&\rightarrow(147,105)\\ &\rightarrow(105,42)\\ &\rightarrow(63,42)\\ &\rightarrow(42,21)\\ &\rightarrow(21,21) \end{aligned}

所以：

\boxed{\gcd(252,105)=21}

结果并不复杂。真正值得注意的是，我们并没有寻找所有约数。也没有在众多候选中比较。我们只是不断缩小问题，却在每次缩小的过程中完整保留了答案。这是一种极其重要的数学思想。一个困难的问题，可能不需要直接解决。只要找到一种保持答案不变的变换，把它变成越来越简单的问题，答案就可能自己显现。

两千年后的名字：不变量

今天的计算机科学家会把这种思维称作维护一个“不变量”（Invariant）。在欧几里得算法中，这个不变量就是：

每次变换前后，两个数的最大公约数始终相同。

只要这一点能够成立，我们就可以放心地把原来的数字丢弃。因为它们所包含的、与问题有关的关键信息，并没有丢失。许多精妙的算法，其实都依靠这种思想。二分查找不断缩小搜索范围，但必须保证目标仍在保留的区间之内。某些排序算法不断调整数据位置，但必须保证已经整理好的部分继续保持有序。图算法不断扩大已知区域，也需要维护某些正确性条件。这些算法虽然解决不同的问题，却拥有一个共同的设计原则：我们可以不断改变问题的状态，但不能破坏证明答案正确所依赖的性质。而在两千多年前的《几何原本》中，这样的逻辑已经以数学证明的形式出现。

第三幕：一次除法，代替许多次减法

现在，我们已经知道连续减法能够求出最大公约数。可是，这个算法存在一个明显的弱点。想象两个数字：

1\,000\,001,\quad1

如果每次只减去1，那么需要进行一百万次减法，才能让两个数相等。虽然结果仍然正确，但过程实在太漫长。有没有办法让计算更快？答案隐藏在一个普通的除法算式里。

1\,000\,001=1\times1\,000\,001+0

实际上，我们不需要做一百万次减法。只需要一次除法，就知道1能够整除1,000,001。重新观察252和105。在连续减法的过程中，我们先减去了两次105：

252-105-105=42

这完全可以写成：

252=2\times105+42

这就是带余除法。接下来：

105=2\times42+21

最后：

42=2\times21+0

当余数成为0，计算结束。最后一个非零余数，就是最大公约数。

欧几里得算法 · 现代取余形式

252=2\times105+\boxed{42}

105=2\times42+\boxed{21}

42=2\times21+\boxed{0}

最后一个非零余数

21

这就是今天最常见的辗转相除法。它与《几何原本》中的连续减法思想相通，但表达方式更加紧凑。一次带余除法，相当于把连续减去同一个数的步骤合并起来。在现代计算机中，这一操作通常写作 %。例如：

252 % 105  # 42
105 % 42   # 21
42 % 21    # 0

于是，我们可以把整个算法概括成一个数学关系：

\boxed{\gcd(a,b)=\gcd(b,a\bmod b)}

其中

b\neq0

，而

a\bmod b

表示余数。只要余数不是0，就继续重复这件事。这个关系看起来平凡，却产生了一个惊人的结果：原来无论数字多么巨大，我们都可以用同一条简单规则去求解。它不需要知道数字代表什么。这些数可以是木尺的长度，也可以是工厂生产周期、齿轮齿数，或者计算机密码系统中使用的大整数。只要输入符合条件，规则就能够运行。算法因此获得了一种超越具体问题的普遍性。

第四幕：为什么它一定能够停下来？

现在，假设你是一名古希腊数学家。某个人来到你面前，告诉你：“我发现了一种计算最大公约数的方法。我已经试验了一百组数字，每次都成功。”你应该相信他吗？从经验上看，这似乎很有说服力。可是一百组数字成功，并不能证明第一百零一组也一定成功。即使试验一百万组，也不能穷尽所有正整数。数学家需要的不是“试过很多次”。而是“能够证明对所有符合条件的输入都成立”。这正是数学证明与经验检验之间的重要区别。

证明一：答案为什么不会改变

假设：

a=qb+r,\qquad 0\le r<b

其中

a,b

是正整数，

q

是整数，

r

是余数。我们的目标是证明：

\gcd(a,b)=\gcd(b,r)

先假设一个整数

d

同时整除

a

和

b

。因为：

r=a-qb

所以

d

也一定整除

r

。这意味着，

a,b

的任何公约数，同时也是

b,r

的公约数。再从另一个方向考虑。假设

d

同时整除

b

和

r

。由于：

a=qb+r

所以

d

也一定整除

a

。这意味着，

b,r

的任何公约数，也是

a,b

的公约数。两组数字拥有完全相同的正公约数。既然它们的公约数集合相同，最大的公约数自然也相同。证明完成。注意，我们没有使用任何具体数字。这段证明同时适用于252和105，也适用于其他任意两个正整数。

证明二：为什么算法不会无限运行

正确性只是算法的一部分。即使每次变换都没有破坏答案，如果程序永远不停，也无法交付结果。因此，我们还必须证明算法会终止。观察取余过程：

a=qb+r,\qquad 0\le r<b

每执行一次取余，新的第二个数就会变成余数

r

。而余数总是严格小于原来的除数

b

。这意味着，在算法继续运行的每一步中，作为除数的那个非负整数都会严格减小。例如：

105\rightarrow42\rightarrow21\rightarrow0

一个非负整数序列，不可能永远严格下降。它不能一直变小，却始终保持非负整数。所以，经过有限次取余运算，余数一定会变成0。这不是基于实验的猜测，而是由整数本身的性质保证的。我们于是得到了两项结论：正确性由公约数不变性保证。终止性由非负整数严格递减保证。这两项性质组合起来，构成了一份完整的算法正确性证明。现代计算机科学中，程序验证、循环不变量和终止性分析仍然采用类似的思维。两千多年前的数学证明，由此与今天的程序设计产生了直接的思想联系。

第五幕：如果木尺的长度根本无法被共同测量呢？

故事到这里，似乎已经圆满。但古希腊数学还有一个更加深刻的问题。想象一个边长为1的正方形。根据勾股定理，它的对角线长度是：

\sqrt{1^2+1^2}=\sqrt2

现在，我们有两条线段。一条长1。另一条长

\sqrt2

。能不能像刚才那样，找到一段长度，让它的整数倍恰好等于这两条线段的长度？换句话说，是否存在某个正长度

u

，以及两个正整数

m,n

，满足：

1=mu,\qquad \sqrt2=nu

如果存在，那么：

\sqrt2=\frac nm

这意味着

\sqrt2

可以写成两个整数之比。但我们知道：

\sqrt2

是一个无理数。这样的整数

m,n

不可能存在。因此，正方形的边长与对角线不存在一个能够同时整数量尽它们的正长度。这种情况在古希腊数学中被称为“不可公度”。这一发现对古代数学思想具有重要意义。因为它表明，并不是所有几何长度都能够用整数之比来表达。

当算法永远得不到零

如果我们把两条不可公度的长度代入连续减去较小长度的过程，会发生什么？每完成一次相减，我们都会得到新的、更小的长度。但余量永远不可能恰好变成零。因为一旦能够在有限次测量之后恰好结束，就意味着我们找到了一个能够整数量尽这两条线段的共同单位。这和它们不可公度的性质矛盾。因此，对于两条不可公度的线段，这样的精确相减过程不会在有限步内终止。《几何原本》第十卷命题2恰好讨论了这种关系：如果对两条不等的量反复进行相减，始终得不到能够量尽前一量的余量，那么这两条量不可公度。^{[Book X][web.calstatela.edu]}这与整数算法形成了一个鲜明对比。对于正整数，每次余数减小，最终一定能够到达0。但对于某些几何长度，余量可以无限减小，却始终不等于0。差别在哪里？就在输入对象的数学性质上。正整数是离散的。在0和1之间，不存在其他正整数。但在0和1之间，却存在无穷多个正实数。所以“每次严格减小”这个条件，单独并不足以保证实数序列在有限步内结束。我们还需要整数的离散性。这也是一个非常值得记住的算法设计教训：一个算法能够正确终止，不仅取决于执行步骤，还取决于它允许处理什么类型的输入。如果你将整数算法直接搬到浮点数环境，却不考虑精度误差、容差和终止条件，原本可靠的程序也可能出现意料之外的行为。历史在这里，与今天的软件工程问题再次相遇。

第六幕：两千年之后，数学家开始计算算法本身

到了十九世纪，欧几里得算法早已是数学中的经典方法。但一个新的问题逐渐变得重要。人们不仅想知道一个算法能不能算出答案，还想知道：究竟需要计算多少次，才能得到答案？1844年，法国数学家加布里埃尔·拉梅（Gabriel Lamé）发表了对欧几里得算法计算步骤的著名分析。他证明，辗转相除法所需的除法次数，与输入数字的十进制位数之间存在明确的上界关系。一个常见的表述是：对于两个正整数，算法所需的除法次数不会超过较小数十进制位数的五倍。不过，拉梅并不是第一个研究这个问题的人。数学史研究指出，Reynaud、Léger、Finck 等学者在他之前已经取得过相关结果。拉梅的研究是这一历史发展过程中极具影响力的一环。^{[ScienceDirect][Wolfram MathWorld]}

最难计算的数字，竟然藏在斐波那契数列里

来看两个数字：

89,\quad55

它们是斐波那契数列中相邻的两项。执行欧几里得算法：

\begin{aligned} 89&=1\times55+34\\ 55&=1\times34+21\\ 34&=1\times21+13\\ 21&=1\times13+8\\ 13&=1\times8+5\\ 8&=1\times5+3\\ 5&=1\times3+2\\ 3&=1\times2+1\\ 2&=2\times1+0 \end{aligned}

竟然需要九次除法。为什么这两个看起来并不大的数字，会让算法执行这么多步骤？仔细观察。每一步的商几乎都是1。这意味着，每次除法都只能相对缓慢地缩小数字。而且，得到的余数本身又构成一条倒过来的斐波那契数列。这并不是巧合。对于给定的除法步数，连续的斐波那契数可以构造出规模特别小却需要如此多步的输入。斐波那契数列因此与欧几里得算法的最坏情况分析紧密联系起来。但是，还有一个更令人惊讶的结论。即便碰到这样的困难输入，辗转相除法的取余次数仍然只随数字的位数增长。在把单次整数取余视为固定时间操作的简化模型里，我们通常将它的时间复杂度写成：

\boxed{O(\log\min(a,b))}

对于任意精度的大整数，还必须单独计算每次除法的位运算成本，因此不能直接把这个式子当作完整的比特复杂度。从古希腊到十九世纪，人类对算法的认识发生了一次重要变化。最初，人们关心一个问题是否能够通过有限步骤解决。后来，人们开始追问：在所有可能输入中，它最多需要付出多少计算代价？这就是算法复杂度理论的一条重要思想线索。

第七幕：一个古老算法的现代生命

如果欧几里得算法只能求最大公约数，那么它是否值得被人类研究两千多年？答案当然不止于此。

从分数约简到工程设计

我们熟悉的分数：

\frac{252}{105}

由于最大公约数是21，因此可以约简为：

\frac{252\div21}{105\div21}=\frac{12}{5}

再回到最初的木尺问题。一块长252、宽105的矩形板材，如果要用边长相同的正方形完整铺满，并且要求正方形边长尽可能大，那么边长就是21。长边可以排列12块。短边可以排列5块。总数是：

12\times5=60

最大公约数不仅给出了一个数字，还解决了一个真实的空间划分问题。

从模运算到现代密码学

再向前走一步。现代密码学中，经常需要解决这样的问题：给定整数

a

和模数

m

，寻找一个整数

x

，使得：

ax\equiv1\pmod m

这里的

x

称为

a

关于模

m

的乘法逆元。例如：

7\times15=105

而：

105\bmod26=1

因此15是7在模26意义下的乘法逆元。当数字非常大时，怎样高效求出这个逆元？答案之一，就是欧几里得算法的扩展形式——扩展欧几里得算法。它不仅求出最大公约数，还能求出整数

x,y

，使：

ax+by=\gcd(a,b)

这一能力是 RSA 等公钥密码算法数学实现中的重要工具。于是，一条古希腊数学中用于求共同度量的思想，最终进入了现代密码学。当然，这并不意味着欧几里得本人预见了计算机或密码学。而是后来的数学家和工程师，不断发现古老数学结构能够解决新的问题。算法的生命力，往往正来自这种跨越时代的重新应用。

第八幕：让古老的算法在计算机中复活

现在，我们终于可以把这套算法写成程序。用 Python 来实现，只需要几行代码。


def gcd(a: int, b: int) -> int:
    a, b = abs(a), abs(b)

    if a == 0 and b == 0:
        raise ValueError("两个数不能同时为零")

    while b != 0:
        a, b = b, a % b

    return a


print(gcd(252, 105))   # 21
print(gcd(89, 55))     # 1
print(gcd(1071, 462)) # 21

其中最关键的只有这一行：

a, b = b, a % b

它将原来的两个数，替换成较小的数和余数。注意，它没有特别针对252和105编写任何规则。对于任意符合条件的整数，这套程序都能得到结果。这里还利用绝对值运算支持负整数，并规定两个输入不能同时为零。我们试着从一名现代程序员的视角，重新描述这个算法。输入是两个整数。每次执行明确的运算。整个过程保持最大公约数不变。算法在第二个数变成零时停止。输出是第一个数。这已经具备了现代算法的典型特征：明确的输入、有限的计算规则、可证明的正确性，以及能够到达的终止状态。

互动实验室：亲手运行欧几里得算法

输入两个正整数

第一个数

第二个数

最大公约数

21

除法次数

3

计算过程

步骤	带余除法	余数
1	252 = 2 × 105 + 42	42
2	105 = 2 × 42 + 21	21
3	42 = 2 × 21 + 0	0

最后一个非零余数就是最大公约数。你可以更改输入，观察计算步骤如何变化。

给读者的三个挑战

第一个挑战： 输入两个相邻的正整数，例如100和101。观察计算次数，并尝试证明它们的最大公约数为什么一定是1。第二个挑战： 输入连续的斐波那契数，例如144和89、233和144。观察计算步骤的增加规律，尝试解释为什么它们能让算法运行得相对缓慢。第三个挑战： 不使用 %，只用减法、比较和交换，重新实现欧几里得算法。然后对比输入1,000,001和1时，两种程序的执行次数有多大差别。完成这些实验之后，可以尝试回答一个更深的问题：如果我们已经知道某种变换不会改变答案，而且能证明问题每次都会变得更小，那么我们是否就找到了一种设计算法的通用思路？这个问题，将在后面的许多章节中不断出现。

尾声：一场跨越两千三百年的对话

让我们重新回到公元前300年前后的亚历山大城。在那里，数学家还没有现代编程语言，也没有晶体管和存储器。他们用文字、图形和逻辑推理描述数学结构。我们无法知道欧几里得编写第七卷时的具体情景。也不知道他是否曾经面对两根木尺，或者用过252和105这样的例子。但我们确实知道，他所整理的《几何原本》中保存了一套严格的数学方法。这一方法告诉后人：当两个数难以直接处理时，可以尝试将它们转化为更小的数。只要转化不会改变目标答案，而且计算过程最终必然终止，就能够建立一套可靠的求解程序。很多世纪以后，数学家继续研究它的运行次数。计算机诞生以后，工程师把它写成程序。现代密码学发展以后，人们又使用它的扩展形式处理模逆元等问题。如今，当你在计算机中写下：

while b:
    a, b = b, a % b

你写下的不仅是几行代码。你实际上是在使用一种跨越了两千多年、仍然具有现实价值的数学思想。它的步骤可以非常简单。它的证明可以非常严密。而它的应用，可以远远超出最初研究它的人所处的时代。这也许是算法最迷人的地方。真正伟大的算法，不只是解决了某个时代的问题。它还能让后来的时代，用它解决发明者从未想象过的问题。

历史档案：本章事实与叙事的边界

本章依据《几何原本》第七卷命题1、2和第十卷命题2的文本，以及现代数学史研究编写。主要参照克雷数学研究所提供的《几何原本》文献资源、圣安德鲁斯大学 MacTutor 数学史档案，以及 Jeffrey Shallit 对欧几里得算法复杂度分析历史的研究。^{[Clay Mathematics Institute][web.calstatela.edu][ScienceDirect][Clay Mathematics Institute]}文中的亚历山大城时代背景、欧几里得活动年代和著作内容有史料支持；开篇的工匠故事、数字示例及心理场景则属于教学重构。欧几里得算法的具体发明者及最初发明时间无法从现存史料中完全确定，因此本章将欧几里得视为这一算法的重要古代文献传承者，而不是未经证实地宣称他是唯一的发明者。

下一章 · 第32章

《把时间切成频率：傅里叶变换的速度革命》

经过两千多年的演进，数学家的问题将发生一场新的变化。一种古老算法能够通过巧妙的步骤，把原本漫长的计算缩短。但到了二十世纪，科学家面对的将不再只是两个整数，而是成千上万、甚至数百万个连续变化的信号数据。怎样从纷乱的波形中找出隐藏的频率？怎样让庞大的计算量突然缩小到原来的很小一部分？下一章，我们将从傅里叶的数学思想出发，走进高斯的早期计算方法，再来到1965年 Cooley 与 Tukey 发表快速傅里叶变换算法的年代，讲述另一次深刻的计算速度革命。

——《算法的故事》第二季 · 第31章完