《数学与泛型编程：高效编程的奥秘》一3.5毕达哥拉斯学派的构想

3.5　毕达哥拉斯学派的构想

对于毕达哥拉斯学派的人来说&＃xff0c;数学并不像今天这样&＃xff0c;是对抽象符号所做的运算&＃xff0c;而是一种关于数字和空间的科学。在可以感知的现实世界中&＃xff0c;数字和空间正是两个最为基本的方面。毕氏学派除了关注正方形数、长方形数及三角形数等有形数&＃xff08;figurate number&＃xff09;之外&＃xff0c;他们还认为&＃xff0c;空间有着离散的结构&＃xff08;discrete structure&＃xff09;&＃xff0c;于是他们试图提供一套以数字为基础的理论&＃xff0c;使得几何学可以建立在该理论之上。这种想法实际上就相当于要创建一套基于正整数的统一数学理论。
为此&＃xff0c;他们提出一个概念&＃xff0c;说一条线段可以用另一条线段来“度量”&＃xff08;be measured&＃xff09;&＃xff1a;
定义3.1　当且仅当线段A可以通过有限个连续的线段V来表示时&＃xff0c;线段V才能用作线段A的量度。
这个量度必须选取得足够小&＃xff0c;使我们可以通过整数次的拼接来产生所需的线段&＃xff0c;没有“分数”&＃xff08;fractional&＃xff09;量度这一说法。测量不同的线段时&＃xff0c;当然可以分别使用不同的量度&＃xff0c;但如果想用同一种量度来测量两条线段&＃xff0c;那么该量度必须是二者的公度&＃xff1a;
定义3.2　当且仅当线段V可以同时成为线段A与线段B的量度时&＃xff0c;它才能用作二者的公度。
毕氏学派认为&＃xff0c;对于任何一个给定的情境来说&＃xff0c;都能找到适用于其中所有相关物件的公度&＃xff0c;因此&＃xff0c;空间就可以离散地进行表示了。

• • *
    由于公度可能有很多个&＃xff0c;因此&＃xff0c;他们提出最大公度量&＃xff08;greatest common measure&＃xff09;这一概念。

定义3.3　如果线段V是线段A和线段B的公度&＃xff0c;而且比两者的其他公度都要大&＃xff0c;那么V就是A和B的最大公度量。
毕氏学派还意识到了最大公度量&＃xff08;GCM&＃xff09;所具备的很多性质&＃xff0c;这些性质用现代的记法可以表示为&＃xff1a;
gcm&＃xff08;a, a&＃xff09; &＃61; a&＃xff08;3.7&＃xff09;
gcm&＃xff08;a, b&＃xff09; &＃61; gcm&＃xff08;a, a &＃43; b&＃xff09;&＃xff08;3.8&＃xff09;
b&＃xff1c;a gcm&＃xff08;a, b&＃xff09; &＃61; gcm&＃xff08;a-b, b&＃xff09;&＃xff08;3.9&＃xff09;
gcm&＃xff08;a, b&＃xff09; &＃61; gcm&＃xff08;b, a&＃xff09;&＃xff08;3.10&＃xff09;
根据这些性质&＃xff0c;他们提出了古希腊数学中最为重要&＃xff0c;或许也是整个数学中最为重要的算法&＃xff0c;那就是如何计算两条线段的最大公度量。古希腊人所使用的计算器具是可以对线段进行操作的直尺和圆规。如果用C&＃43;&＃43;代码来表示该算法&＃xff0c;并把line_segment视为一种类型&＃xff0c;那么我们可以将其写为&＃xff1a;

上面这段代码借助了三分律&＃xff08;trichotomy law&＃xff09;&＃xff0c;也就是说&＃xff0c;如果a与b这两个变量是同一种类型&＃xff0c;并且该类型的所有取值都是可以比较大小的&＃xff08;totally ordered&＃xff09;&＃xff0c;那么a与b的关系只可能是a &＃61; b、a&＃xff1c;b或a&＃xff1e;b这三种情况之一。
我们以gcm(196, 42)为例来演示该算法的计算过程&＃xff1a;
a b
196&＃xff1e;42, gcm&＃xff08;196, 42&＃xff09; &＃61; gcm&＃xff08;196-42, 42&＃xff09; &＃61; gcm&＃xff08;154, 42&＃xff09;
154&＃xff1e;42, gcm&＃xff08;154, 42&＃xff09; &＃61; gcm&＃xff08;154-42, 42&＃xff09; &＃61; gcm&＃xff08;112, 42&＃xff09;
112&＃xff1e;42, gcm&＃xff08;112, 42&＃xff09; &＃61; gcm&＃xff08;112-42, 42&＃xff09; &＃61; gcm&＃xff08;70, 42&＃xff09;
70&＃xff1e;42, gcm&＃xff08;70, 42&＃xff09; &＃61; gcm&＃xff08;70-42, 42&＃xff09; &＃61; gcm&＃xff08;28, 42&＃xff09;
28&＃xff1c;42, gcm&＃xff08;28, 42&＃xff09; &＃61; gcm&＃xff08;28, 42-28&＃xff09; &＃61; gcm&＃xff08;28, 14&＃xff09;
28&＃xff1e;14, gcm&＃xff08;28, 14&＃xff09; &＃61; gcm&＃xff08;28-14, 14&＃xff09; &＃61; gcm&＃xff08;14, 14&＃xff09;
14 &＃61; 14, gcm&＃xff08;14, 14&＃xff09; &＃61; 14
由此可见&＃xff0c;gcm(196, 42) &＃61; 14。
我们这里所说的gcm(196, 42)&＃xff0c;意思当然是指长度为196和长度为42的两条线段所具备的最大公度量&＃xff0c;然而本章在举例时为了简单起见&＃xff0c;会直接用代表线段长度的那个整数来表示该线段本身。
在接下来的几章中&＃xff0c;我们还要使用该算法的各种版本&＃xff0c;因此大家一定要理解这个算法&＃xff0c;并明白它的计算原理。你可以自己用手算上几轮&＃xff0c;以便获得更加确切的印象。