历史上最著名的3个数学算法，关于算法的观念，直到今天还在演进

准确定义算法这个词并不容易还有一些意思相近的同义词，也就是其他一些名词，会给出几乎一样的东西，比如 "规则" "技巧 " "过程 " "方法 "还可以举一些例子，比如长乘法，这是小学生学习的两个正整数相乘的一种垂直乘法可是，尽管非正式的解释和适当的例子给人一种算法是什么的良好感觉，但隐藏在算法一词中的思想经历了一个漫长的演变过程，直到20世纪才获得一个令人满意的形式定义，而算法的概念仍在不断演变

算盘和算术家

回到乘法的例子，有一点很明显:两个数怎么相乘这些数的表示方法很大程度上影响了乘法的具体练习要理解这一点，试着把两个罗马数字CXLVII和XXIX相乘，但先不要翻译成等价的十进制数147和29这个事情很难理解，后面还要花很多时间去计算，这也可以解释为什么罗马帝国关于乘法的资料极其零散

c表示100x代表10L代表50，但是把X放在L的左边意味着从L中减去X，所以是40，V意味着5，I意味着1，两个I放在V的右边，意味着把它们加到V上，所以是7以上解释加起来，就是罗马数学的147

我们今天使用的记数系统也可以携带如果携带，可以使用一种或多种碱

长期以来，我们可以使用一种计算工具算盘进行计算这些计算工具可以表示一定基数下进位制中的数字例如，如果基数为10，则标记可以代表1个单位或10，或100等等，这取决于它被放置在哪一行或哪一列通过根据精确的规则移动这些标记，可以执行四种算术运算中国的算盘是算盘的一种

12世纪，阿拉伯数学著作被翻译成拉丁文后，十进制在欧洲开始流行这种进位制特别适合于算术运算，并导致许多新计算方法这些方法一般称为算法，不同于算盘上用记号笔计算

有限性

我们看到算法一词指的是中世纪基于整数十进制表示的计算程序但到了17世纪，在达朗贝尔主编的百科全书中，算法一词被赋予了更广泛的含义，不仅指算术，还包括代数方法和其他计算程序，如积分算法正弦算法等等

算法是一组有限的规则，用于对有限数量的数据进行操作，并在有限数量的步骤后产生结果。

注意这里已经强调了有限性，写算法的有限性和执行算法的有限性。

上面的陈述不是经典意义上的数学定义我们将会看到进一步形式化它是很重要的但我们暂时对这个定义感到满意，再来看看数学中算法的一些经典例子

三个历史例子

算法有一个我们还没有提到的特点:迭代，即简单程序的重复执行为了看出迭代的重要性，我们再来看一下长乘法的例子，长乘法是一种适用于任意大小正整数的方法数字越大，程序越长但最重要的是方法相同如果你能把两个三位数相乘，你也会把两个137位数相乘，而不需要学习任何新的原理原因是长乘法包含了大量精心构造的，小得多的任务，比如两个一位数的表相乘我们将看到迭代在我们将要讨论的算法中起着重要的作用

欧几里德算法:迭代

欧几里德算法是最好的，也是最常用的例子来说明算法的本质这种算法可以追溯到公元前3世纪欧几里得用它来计算两个正整数的最大公约数

当我们第一次遇到两个正整数A和B的最大公约数时，定义为正整数，是A和B的因子..但是，出于许多目的，最好将其定义为具有以下两个属性的唯一整数d。这两个属性是:

第一，d是a和b的因子，

其次，如果c是a和b的另一个因子，那么d可以被c整除。

欧几里得《几何原本》第七卷的前两个命题给出了一种求d的方法，其中第一个命题如下:给定两个不相等的数，从较大的数中减去较小的数如果剩余的数字直到剩余的数字是一个单位才能测量，那么原数就是互质的换句话说，如果你辗转反侧得到数字1，那么gcd就是1这时候就说原来两个数互质

翻滚减法

现在让我们概括地描述欧几里得算法，它是基于以下两个观察:

若a=b，则a和b的gcd为b。

d是a和b的公约数当且仅当它也是a—b和b的公约数。

现在我们来设定需要A和B的gcd，设A ≥ B..如果a=b，观察告诉我们gcd是B，否则观察告诉我们，如果找到a—b和B的gcd，得到的答案是一样的现在设a_1为a—b和B中较大的一个，b_1为较小的一个，然后求两个数的gcd但是，现在两个数中较大的一个，即a_1，小于原来两个数中较大的一个，即A，这样，我们可以重复上面的过程:如果a_1=b_1，则a_1和b_1的gcd，即A和B的gcd为B _ 1，不然我们可以把a_1改成a_1—b_1，然后组织a_1—b_1，b_1，总之

为了让这个项目继续下去，还需要进行另一项观察。这是以下关于正整数的基本事实，有时称为良序原则:

严格降序正整数序列a _ 0 gta1 gta2 gt...必须是有限序列。

因为上面的迭代过程只是产生了一个严格的下降序列，这个迭代最终肯定会停止，也就是说在某一点一定有a_k=b_k，这个公共值就是A和b的gcd。

欧几里德算法流程图欧几里德除法

一般欧几里德算法的说法与此略有不同可以应用一种更复杂的叫做欧几里德除法的程序，这种程序可以大大减少算法的步骤数，这种算法也叫轮流除法

数q叫做商，r叫做余数。上述两点和现在应替换为

若r=0，则a和b的gcd为b。

a和b的gcd与b和r的gcd相同。

这一次，将第一步中的替换为如果r≠0，做第二步，用代替r1是b除以r得到的余数，所以r _ 1ltr，并模仿过去

不难看出，这两种方法在求gcd方面是等价的，但在算法方面却有很大的不同比如设a=103 438，b=37如果用翻来覆去的减法，会反复从103438中减去37，直到剩下的差小于37这个差和103438除以37的余数一样，如果用第二种方法，一次就可以得到这样，使用第二种方法的原因是，用反复减法求除法余数的效率非常低提高效率在实践中非常重要第二种方法给出了多项式时间算法，而第一种方法需要指数长的时间

范围

欧几里德算法可以扩展到很多其他背景，只要有加减乘除的概念例如，它有一个变体可以用于高斯整数环它是由复数以a+bi的形式构成的环，其中a和b是整数，也可以用在实系数的多项式环中但是有一个要求，就是能够用余数除法定义类比有了这个，算法和正整数情况下的算法基本相同比如下面这个命题:如果A和B是两个任意多项式，B不是零多项式，那么一定有两个多项式Q和R..所以要么R=0，要么R的个数小于b的个数

正如欧几里德在《几何原本》中提到的，当A和B不一定是整数时，这个程序也可以对一对数实现容易验证，当且仅当比率a/b是有理数时，这个程序才会停止这个观点引出了连分数的概念在17世纪之前，没有专门研究过，但其思想根源可以追溯到阿基米德

阿基米德计算π的方法:近似和有限

圆的周长与直径之比是一个常数，从18世纪开始被记录为π现在我们来看看公元前3世纪阿基米德是如何得出这个比例22/7的经典近似值的如果我们在一个圆上做一个内接正多边形和一个外切正多边形，然后计算这些多边形的周长，就会得到X的上下界，因为圆的周长一定大于任何内接多边形的周长，但小于任何外切多边形的周长阿基米德从正六边形开始，然后将多边形的边数一次增加一倍，得到越来越精确的上下界他实现了96边形并得到了它

π的近似

但是，逼近π的算法和阿基米德计算两个正整数的gcd的算法有明显的区别像Euclid这样的算法通常被称为离散算法，与用于计算非整数值的数值算法相对

牛顿—拉夫逊法:递归公式

1670年左右，牛顿提出了求方程根的方法，并针对方程x 3—2x—5 = 0解释了他的方法他的解释从观察到x的根大约等于2开始

因为x接近2，p很小，他省略了P 3和6p^2来估计p，这就给他P 10p—1=0的等式，也就是p=1/10这当然不是一个精确的解，但它给了牛顿一个新的更好的近似根:x=2.1然后牛顿重复这个过程，使X = 2.1+Q，代入原方程后，他给出了一个关于Q的方程，近似求解这个方程，提炼出他的近似解，于是Q的估计为—0.0054，于是X的下一次近似为2.0946

可是，我们怎么能确定这个过程会收敛到X呢让我们更仔细地检查这个方法

正切和收敛

牛顿的方法可以用函数f的形象来作几何解释，虽然牛顿本人并没有这样做f=0的每个根x对应于函数y=f的曲线和x轴的交点如果我们从根X的一个近似值A出发，如上设置p=x— a，就可以用a+p代替X得到一个新的函数g，也就是说原点被有效地移到了然后把p的所有高次幂都省略掉，只留下常数项和线性项，这样就得到了函数g的最佳线性逼近——几何上讲，这就是g在点)的正切

这样，得到的p的近似值就是函数y在点的切线与x轴的交点在横坐标上加一个A，就是把原点返回到原来的，这样A+P就给出了f的根的一个新的近似，这就是为什么牛顿的方法叫切线法

牛顿法

从上图可以看出，如果曲线y=f的切线与X轴相交于点A，F在点(A，f(a))的切线与X轴相交(即上图中横坐标为a+p的点，即根的近似值)，则第二次近似(即A+P+Q)肯定比第一次近似高A+。

回到牛顿的例子，我们可以看到牛顿选择a=2并不是上面所说的情况但是从下一个近似值2.1开始，下面所有的近似值都是一样的几何上，如果点)在X轴上方，y=f(x)的曲线在凸部与X轴相交，或者点)在X轴下方，y=f(x)的曲线在凹部与X轴相交，就会出现这种有利的情况

初始近似值的选择显然是非常重要的，它提出了微妙的和意想不到的问题如果我们考虑复多项式的复根，这就更清楚了牛顿的方法很容易适应这种更广泛的背景设Z是一个复多项式的复根，z0是初始逼近，那么牛顿法会给出一个z0，Z1，z2…的序列，这个序列可能收敛也可能不收敛于Z，我们把根Z的吸引区域定义为这样的初始逼近z0的集合，这样得到的序列就真正收敛于Z，把这个区域记为A(z)如何确定A(z)

第一个提出这个问题的人是1879年的格洛丽亚他注意到，这个问题对于二次多项式来说很容易，但是当次数为3或3以上时就很难了比如多项式z 2—1的根1的吸引面积是复平面上以纵轴为界的两个半平面，但是z 3—1的三个根1，w，w 2对应的吸引面积是极其复杂的集合这些集合由Julia在1918年描述，现在被称为分形集

递推公式

牛顿方法的每一步都会产生一个新的方程但拉夫森指出，这实际上是不必要的对于特殊的例子，他给出了一个可以用于每一步的公式但他的基本观察结果是可以普遍应用的，推导出了一个可以在每种情况下使用的通用公式，这个公式可以很容易地通过切线解释得到

它与x轴相交的横坐标是a—f/f’我们现在说的牛顿—拉夫逊法就是指这个公式我们从一个初始近似值a_0=a开始，然后用这个递归公式得到它

这样就得到一个近似序列，在复数情况下，即z_0，z_1，z_2，...

举个例子，考虑函数f = x ^ 2—c，此时牛顿法给出了c的平方根的一系列近似，递推公式现在是

将上述通式中的f替换为x 2—c。这个近似的平方根解是在公元1世纪被亚历山大的海伦发现的..

。