本系列文章预计会有10个章节，这套文献会系统讲述计算机科学本身，这里是第一季第06篇接上篇，今天是讲发明家巴贝奇相关故事的第二篇，这一节谈谈差分机的原理。 19世纪，在工业革命的促进下，西方科技和经济蓬勃发展，越来越多的场景需要对复杂多项式进行计算，比如求y=x²+x³函数，当x=5时，求y值等等，可能还有一些三角函数的计算、指数和对数的复杂计算。我们知道当时帕斯卡和莱布尼茨发明的“计算机”已经可以解决了四则运算，那么这种复杂运算当时是怎么做的呢？当时人们流行这种做法: 针对一些常用的多项式，预先计算出一系列的y值，打印出一张x值与y值的对应表，这就可以直接查表求值，而不是计算求值。没错，就是表，直接可以查阅的表。当时，在微积分出现之前，完成这些函数的计算几乎不可能。18世纪之后，欧洲数学家使用微积分，才找到了很多计算上述函数的近似方法。不过这些方法的计算量极大，需要很长的时间，而且当时除了数学家，一般人是完成不了那些计算的。为了便于工程师在工程中和设计时完成各种计算，所以数学家才设计了数学用表。这就像我们中学对数表或者九九乘法表一样，直接查就得了！显然，如果用手工来算这些多项式的值，工作量比较大，而且多项式的形式不计其数，太过繁琐。还有一个严重问题，就是那个时代的数学用表错误百出，给生产和科学研究带来了很多麻烦。而这个问题很难避免，因为手算很难保证完全不出错。如果很多数学家分别独立计算，还可以比对结果发现错误。但是巴贝奇发现，那些不同版本的数学用表都是抄来抄去的，而犯的错也都是一样的。因此，巴贝奇就想设计一种机械，能够完成微积分的计算，然后用它来计算各种函数值，得到一份可靠的数学用表。当时他只有22岁。在随后的 10 年里，巴贝奇造出来一台有 6位精度(巴贝奇最初的目标是达到8位精度 )的小型差分计算机。随后巴贝奇用它算出了好几种函数表，用于解决航海、机械和天文方面的计算问题。值得指出的是，巴贝奇的这次成功受益于工业革命的成就——当时机械加工的精度比瓦特时代已经高出了很多，这让巴贝奇能够加工出各种尺寸独特的齿轮。但是，当时并没有 20 世纪的精密加工技术，制造小批量特制齿轮和机械部件的成本高、难度大，这给巴贝奇后来的工作带来了诸多不便。是什么让巴贝奇产生制造“差分机”的想法呢？以及为什么要起名为“差分机”呢？我们掰一掰。笔者以前确实也只是知道巴贝奇和他的差分机，但是作为专栏的创作者还是必须要理清楚深层的知识，我们继续往下看。是这样的，差分机这个名字，源自其所使用的算法，是帕斯卡在1654年提出的差分思想：n次多项式的n次数值差分为同一常数。等下我们举几个例子大家就懂了。当时基于01（计算的烦恼 ）所以构思如果能有一台机器可以输入各种多项式，不管是x+x²+x³还是2x+x²，抑或是其他形式，它都可以自动求出当x=1,2,3,4,.··的值。或者x=0.001.0.002、0.003,0.004,..·，0.999，时求出对应的y值，那么就可以一劳永逸了。而真正为之action这位老哥就是巴贝奇。他的第一个目标就是设计一台“可编程（当时还没有编程的概念）”的机械制表机。还有一个细节是，1786年的一本书中记载了穆勒（这个人的具体背景我还没查到，有知道的读者可以补充下）的一个构想。穆勒根据下面所示的规律来计算多项式的值，比如y-2x+x²，当x=1时y=3;x=2时y =8;x=3时y =15:x=4时y=24，由此可以发现如下图的规律。只要先算出该多项式结果中的每一阶的差值，就可以根据上一个结果，按照一定规律加上这些差值，得出下一个结果的值，这样就不需要把每一个x的值都代入计算一遍了。可以看到，二次多项式有两阶差，三次多项式则有三阶差，这样，不管这个多项式多么复杂，只要幂次一定，其运算量都差不多。这样就可以极大简化机器的复杂度。根据书中记载，穆勒构想了这样一台能根据上一个结果和差值自动求解多项式数值表的机器，称之为“差分机”。但是穆勒没有获得资助。1822年6月14日巴贝奇上书皇家天文学会 以“采用机器计算天文及数学表手记”为题目，成功获得了资助，因为当时对数学表的需求的确很大，政府认为这能解燃眉之急，节省成本。1823年政府资助了1700英镑用于启动项目。但是实际工程中却发现，由于当时的机械制造工艺无法良好地满足其两万五千个左右的部件的规格要求，耗费的成本远超过预想，最终政府投入了十倍的资金，但是巴贝奇依然没能造出这台机器，只造出了一部分，如下图所示。在原本的设计中，该机器被称为“差分引擎一号” (Difference Engine No.1) ，可以计算到第六阶差，支持 16 位数的运算。该机器由工匠 JosephClement 负责打造，预计完工后将有25 000个零件，重15吨。可惜，一方面是零件太过精密，制造困难，另一方面巴贝奇不停地边制造边修改设计，与Clement产生极大矛盾并最终导致其辞职。从1822年到1832 年的十年间，巴贝奇只拿出了上面所示的这部分来示范。最后大部分零件被熔掉回收，英国政府在1842年做最后清算时发现，整个计划一共让政府赔掉了 17500英镑一一约等同于 22 台蒸汽火车头（这个损失在当时还是巨大的）。然而，巴贝奇并没有丧气，在制造差分机的过程中，其思想得到了升华，意识到整个机器可以进化为更高级的形态。所以在1834年，他转为设计另一种更通用更强大的计算机 —— 分析机。在分析机的设计构算单元包含四则运算模块，同时还可以存储四组不同的运算方程式，相当于四个独立的程序。这些方程式程序采用穿孔卡片(Punched Card)（关于提花机穿孔卡片我们后期谈英国诗人拜伦之女奥古斯塔·埃达·金（Augusta Ada King）再谈）加载到机器里，支持判断跳转、循环等程序逻辑，运算结果可以选择输出到打印系统、打卡系统、绘图系统等。这分明与现代计算机的架构别无二致了。只是，这一次又成为了纸上谈兵。巴贝奇留给后人的只有如小图的这台机器的一小部分。在x取0～6时，F(x)及∆F(x)的值如下表所示：不难发现，对于一次多项式，每个相邻的x所对应的F(x)之差都是一个常数，这个常数正是x的系数。那么二次多项式呢？在x取0～6时，F(x)及其一次、二次差分的值如下表所示：对于二次多项式，每个相邻的x所对应的一次差分之差（即二次差分）是一个常数。一次多项式和二次多项式的规律如此，三次、四次，乃至任意多次的多项式都遵循这样的差分规律——n次多项式的n次差分为常数。差分规律是一项伟大的发现，有了差分，在计算多项式时就可以用加法代替乘法，我们只需要准备好x=0时F(x)及各次差分的值，后面任意x所对应的F(x)值均可通过加法得出。只要有了各列的数值，后期只需要相加即可。从原理上讲，其实就是将复杂的计算拆解成有规律的计算，然后让机器去计算即可。好，今天就先这样，下一篇我们来总结一下这位巴贝奇老哥。
|
