下载掌阅APP，畅读海量书库
立即打开
欧几里得在《几何原本》第10卷中简要地叙述了什么叫做不可公比的量（incommensurable quantities）：
命题2 有两个不相等的量，若较小的量不能度量较大的量，则从后者中反复减去前者，直至余量比前者还小为止，然后轮番执行这个判断并相减的过程。如果小量始终无法度量大量，那么最初的那两个量就是不可公比的。
如果用3.5节所说的最大公度量（GCM）算法来做解说，那么欧几里得在这个命题里面要讲的意思实际上就是：若算法永远不能终止，则该算法的两个参数之间，不存在公度量。
然后，欧氏明确提出了一个算法，并且证明这个算法能够用来计算GCM。下面这张图有助于证明此算法：
由于这个证明是历史上第一个与算法是否能够停止有关的证明，因此，有必要把全过程抄录在这里（此处依据了Sir Thomas Heath的英译本）：
命题3 给定两个可公比的量，寻找其最大公度量。
证明
假设AB和CD是两个可公比的量，且AB小于CD，那么现在要寻找的就是AB与CD的最大公度量。
AB要么可以度量CD，要么不能度量CD。
若AB可以度量CD，则它亦能度量其自身，因此，AB就是AB与CD之间的公度量。
而且这个公度量，显然也是AB与CD之间的最大公度量。因为假如还有一个比它更大的公度量，那么那个公度量就比AB要大，因而无法度量AB。
接下来考虑AB不能度量CD的情况。
在这种情况下，如果将较小的量从较大的量中反复减去，直至余量比前者还小为止，然后轮番执行这个判断并相减的过程，那么就总能找到前者可以度量后者的时候， 这是因为，AB与CD并非不可公比的量，因此，按照第10卷第2号命题所说：如果把AB反复从CD中减去，直至余量EC小于AB为止（此时减去的那一部分称作ED，它可以为AB所度量），然后把EC反复从AB中减去，直至余量AF小于EC为止（此时减去的那一部分称作FB，它可以为EC所度量），那么轮番执行此过程，就总是能够找到前者可以度量后者的时候。不妨设AF可以用来度量CE。
由于AF可以度量CE，而CE又可以度量FB，因此，AF也可以度量FB。
而AF同样能够度量其自身，因此，它可以度量AF与FB之和，也就是整个线段AB。
由于AF可以度量AB，且AB可以度量DE，因此AF也能度量ED。
而AF同样能够度量CE，因此，AF可以度量CE与ED之和，也就是整个的线段CD。
于是，AF就是AB与CD之间的公度量。
现在要证明它不仅是公度量，而且还是最大的公度量。
假如它不是最大的公度量，那就意味着还有某个可以用来度量AB与CD的线段比AF要长。
把这个公度量设为G。
由于G可以度量AB，而AB又可以度量ED，因此，G也能够度量ED。
而G同样能够度量整个的线段CD，因此，G能够度量CD与ED的差值，也就是CE。
由于G可以度量CE，而CE又可以度量FB，因此，G也能够度量FB。
而G同样能够度量整个的线段AB，因此，G能够度量AB与FB的差值，也就是AF。可是按照刚才的假设，G要比AF大，因此，它不可能用来度量AF。所以说，不存在这样的G。
于是，在可以同时度量AB与CD的线段中，没有任何一条线段能够比AF还长，因此，AF就是AB与CD之间的最大公度量。
由此可见，给定两个可公比的量AB与CD，是可以找到其最大公度量的。
这种通过“辗转相减”来寻找GCM的办法，叫做欧几里得算法（Euclid’s algorithm或Euclidean algorithm）。它是第3章那个gcm函数的迭代版本。我们现在也用与C++代码类似的写法来描述这个算法的实现方式：
我们无需考虑线段长度是不是0的问题，因为在欧几里得的语境中，线段长度不可能为0。
习题4.1 如果其中一条线段的长度远远大于另一条线段，那么gcm0函数的效率就很低。请给出一种更为高效的实现方式，这种方式不能使用尺规作图所无法进行的运算。
习题4.2 证明：如果某线段可以同时度量另外两条线段，那么它也同样能够度量那两条线段的最大公度量。
为了提升line_segment_gcm算法的效率，我们首先对代码进行调整，以便在b＜a的时候尽可能多做一些减法：
在执行完多次减法运算之后，如果a与b相等，那么本来还可以通过一条测试语句来跳过其后的交换操作，但由于我们目前并没有做好优化代码的准备，因此先不考虑这个问题。我们现在要考虑的是，由于内层while循环是在计算a与b的余数（reminder），因此，可以将这部分代码单独提取成一个函数：
上面这个循环是不是一定会终止呢？这似乎不太容易看出来。如果在定义line_segment类型的时候，把从一个端点出发沿着某个方向无限延伸的射线（half line）也算进去，那么这个循环可能就无法终止了。因此，我们需要援引下面这条公理来对segment_remainder函数做出预设，以保证它总是能够终止：
阿基米德公理（Axiom of Archimedes） 对于任意两个量a与b来说，总有自然数n，使得a≤nb。
这实际上相当于在说：没有无穷的量。
现在重写GCM函数，令其调用segment_remainder：
我们目前只是重构了代码，并没有改善其性能。由于代码中的大多数工作都是在segment_remainder中执行的，因此需要设法提升该函数的速度。这里所用的办法与埃及乘法算法类似，也就是要通过对相关的量进行翻倍及减半来优化其运算过程。为此我们需要了解某数同另外一个数的二倍相除所得的余数，与该数同原数相除所得的余数之间究竟有着什么样的关系：
引理4.1（递归求余引理，Recursive Remainder Lemma） 如果r=segment_remainder（a，2b），那么：
比方说，假如我们要寻找n与10之间的余数，那就先看它和20之间的余数。如果余数小于等于10，那么这个余数就是它与10相除的余数，若余数在11～20之间，则从余数中减去10即可得到答案。
根据这个办法，我们可以把求余函数写得更快一些：
这种递归形式显得不太直观，因为它是一种向上递归（upward recursion）。大多数递归程序的递归参数都是逐渐变小的，也就是会从n降为n-1，而此处的参数却在逐渐变大，也就是会从n升为2n。尽管它的运作方式并不那么明显，但其结果依然是正确的。
现在来看一个例子。假设线段a的长度是45，线段b的长度是6，现在要寻找a与b相除的余数：
要注意的是，由于古希腊人并没有长度为0的线段这一概念，因此，他们所认为的余数是位于[1，n]这个范围之内的。
优化之后的函数依然使用了递归，因此会产生相关的开销。我们最终是想把递归变为迭代，但目前先不考虑这个问题。
令GCM函数调用优化之后的求余函数就可以得到下面这段代码，它可以用来解答习题4.1：
当然，如果a和b这两条线段本来就不存在公度量，那无论你把这个函数优化得多好，它都不可能适当地终止。