【计算机系统导论】1.1 从算筹到打孔卡片

计算机的发展和工业化的整体思路是一致的,就是利用机器来取代简单可重复的操作,在降低错误率的同时提高速度,这也就不难解释为什么在通用计算机出现之前,计算器更多是以辅助的角色出现在各个行业——比方说纺织业中了。但是随着图灵机概念的提出,现代计算机在通用化方面迈出了最为重要的一步。图灵也因此被认为是计算机科学之父,而纵观计算机发展历史,可真是『天才引导的历程』,一路走来,星光熠熠。


更新历史

  • 2016.11.05: 完成初稿

计算无处不在,银行业需要计算利息,工程师需要计算桥梁受力,而小朋友们则数手指分饼干。从手写公式计算,到手按计算器计算,再到手敲键盘计算,原来,说到计算,最离不开的,是手。而在怎么把手玩出花样这个问题上,东西方交出了不同的答案。答案虽然不同,但目标是一致的,就是把计算变得更简单更准确。

1.1.1 从算筹到分析机

小时候我们数手指,长大一点手写公式计算,之后用手按计算器,再后来开始用手敲键盘,原来说到计算,最离不开的,是手。而在怎么把手玩出花样这个问题上,东西方交出了不同的答案。

数手指在非负个位数范围内的运算居于霸主地位,简单粗暴快捷,唯一的问题是没有办法存储结果。不要小看这个问题,只有在真正解决了存储结果这个问题之后,计算的方式才有了突破性的进展。

1.1.1 巴比伦数字

大约公元前 3100 年左右,巴比伦数字出现了,可以看作是『数手指』的集大成者。不过在此之前,请拿出双手,一起来数一次手指:

这种手指记数尤其适合清点货物,这也是为什么12进制是世界各地常见的计量单位之一。

  • 左右手的功能区分不同,左手用来计数,右手用来进位
  • 用左手大拇指依次敲击食指、中指、无名指和小拇指的三个关节,可以数到 12 (这也就是十二进制的来历)
  • 敲完小拇指如果需要继续数,那么右手屈起一根手指当做进位,左手可以继续计数

我们来测试一下,假如要数 33,那么左手拇指需要动几次?右手需要屈起几根手指?左手每个指关节各被敲击几次?

稍作尝试我们就能发现,与传统掰手指只能数到 10 不同,这种手指记数同样两只手可以数到 60,一下成了原来的 6 倍,在清点货物的时候非常方便,这也就是 12 进制在世界各地广泛使用的由来,毕竟贸易是最快的传播途径。

不过一旦超过 60,问题就来了,因为我们没有办法继续进位了:左手承担了最右边一位的功能,右手承担了右边第二位的功能,我们并没有第三只手了。有意思的是,这种位数的限制在计算机中也同样存在,比方说我们常听到的 32/64 位计算机,如果把它比作人的话,那么只有一只手,且这只手上有 32 根手指(但具体的计数方式是二进制,后面会详细说)。

奇怪的是,数手指的时候是以 12 进位,但是经过演化成为巴比伦数字具体写下来,却是以 10 进位的。于是十二进制和十进制一合体,因为最小公倍数的关系,就成了六十进制,也正是我们前面数手指能表示的最大数字。


(图 1.1 巴比伦数字)

因为这种不统一数制和符号的匮乏(实际上只有两种符号),巴比伦数字非常容易混淆,比方说上图的 60 和 1,稍不注意就会弄错。更重要的是,设计本身极大限制了表达(这在之后会有更深刻的表现),书写也不够方便(写 9 大约需要花 9 倍于写 1 的时间),相比于十进制所需要的九九乘法表,巴比伦数字需要的是六十六十乘法表,整整 1770 项(50x60/2)!因此,两河流域的数学基本只停留在计数阶段,并没有太大的发展。

1.1.2 算筹

让我们把视角移回东方,看看起源于约前 1600 年商朝的算筹。商朝特别流行占卜,于是用现成的小木棍做计算,就是最早的算筹。和巴比伦数字一样,算筹也只有横竖两个符号,但我们机智的老祖宗利用横竖混排避免了混淆,用更少的笔画做出了更优秀的设计,真正意义上做到了统一的十进制系统(无论是数手指还是书写均为十进制)

更重要的是,围绕这一计数系统,经过历朝历代的改进,不但有了小数(浮点数)和正负数的概念和表示,甚至能够利用消元法解一元高次方程(可以在习题中尝试,例子),是当时最先进的计数系统之一。

如果想要了解古人在数学上的进展,还是要把基本的算筹弄明白的,祖冲之就是利用算筹把圆周率推算到小数点后七位的(3.1415926),又比如下图的杨辉三角,就是 1303 年元代数学家朱世杰在《四元玉鉴》卷首绘制《古法七乘方图》


(图 1.3 杨辉三角形 朱世杰《四元玉鉴》)

关于计数系统再多说几句,不同的文明基本都有自己的文字,而不同的设计和表达形式极大影响了不同计数系统的表达能力。


(图 1.4 各种计数系统。注:需要重新绘制)

结合数学的发展历史来看,有以下几个关键设计,可以说从一开始就决定了数学发展的程度:

  • 是否有表示 0 的符号,这决定了是否能够通过统一的表达形式来进行进位
  • 书写和计数时的进制是否一致,如果不是,为了配合进制转换会出现很多不规则的词
  • 基本组成元素的数量,比方说罗马数字只有 I V 和 X,需要通过加加减减来表达某个数字,这种自带计算成本的技术方式会极大阻碍数学发展
  • 书写是否简洁,每个数字的书写时间是否接近

1.1.3 算盘与安提基特拉机械

算盘其实并不是中国人最早发明的,因为算筹的强大和简洁,直到宋元时期(公元十世纪)算盘才开始广泛流行。而算盘最早测雏形大约在前 2700 到 2300 年左右的苏美尔文明时代就已出现,而后随着巴比伦数字传到古希腊,最终在古罗马时代慢慢形成了青铜算法,拉丁语名为 abacus


(图 1.5 古罗马算盘

和巴比伦数字一样,奇怪的事情又发生了,西方人似乎一直都很喜欢用奇怪的制式配合灵活的工具,比方说不太直观需要左减右加的罗马数字让罗马算盘缠上了裹脚布,熟练使用这种计数系统就需要大量的记忆。

在铅笔出现之前,算盘最大的优势在于便携,商人和税务官甚至可以站着路边进行计算。虽然随着时代的发展算盘一直在演变,但其基本组成却从未变化。算盘的意义在于把原来的心算过程用固定的口诀表示了出来,只需要按照固定的规律,就可以得到想要的结果。算筹和算盘不但在功能和效率上远超手指计数,更利用不同的方式存储计算的中间结果,这就是一次彻底的革命,实际上相当于寄存器。

而当我们把视角转向西方,约在公元前150到100年之间,古希腊人为了计算天体在天空中的位置设计了一个青铜机器(属于模拟计算机),通常称为安提基特拉机械。在沉睡了近两千年后被打捞出来,一位对此进行深入研究的教授不禁赞叹:『该机器是如此的非凡,而且是仅此一件。这个设计是美丽的,其天文周期极为精确。这个机械的设计会让所有人惊讶得下巴脱落。无论是谁设计的都是非常仔细……在历史性和稀少性的价值上,我必须承认这个机械比蒙娜丽莎还有价值』。

可惜的是,这样高超的工艺随着古希腊文明的暗淡而消逝,类似的如此复杂工艺技术直到 14 世纪时欧洲制造了天文钟后才重新出现,但安提基特拉机械的重现于世界证明了,超越时代的人类的智慧终将闪耀。

1.1.4 骨头与计算尺

随着阿拉伯数字的传入,罗马数字和罗马算盘逐渐被取代,借助更加完善和统一的计数系统,西方的计算能力终于快速发展了起来。查询式计算工具就是其中的突出代表,只要应用特定的计算规则,就可以得到想要的结果,一个有趣的例子是苏格兰数学家纳皮尔在 1614 年发明的“纳皮尔的骨头”(Napier’s bones)。

纳皮尔的骨头主要用于计算乘除法,实际上是把乘法转换为加法,把除法转换为减法,也可以用于开平方根。


(图 1.6 纳皮尔的骨头

纳皮尔在发现利用加减计算乘除的方法之后更进一步,提出了对数的概念。而纳皮尔的骨头其实就是为了协助计算对数表而发明的,之后在 1633 年,英国牧师奥特雷德利用对数基础,发明出一种圆形计算工具比例环,通过对齐尺子上的刻度查询计算结果(这就是中文“对数”一词的由来),并最终演变成最基本的手动计算器——计算尺。其深远影响一直延续到了 20 世纪。直到 20 世纪 70 年代出现电子科学计算器,没有一套计算尺,都不好意思说自己是工程师。

计算尺满足了从军事到航海各个领域的近似计算需求(在这些领域快速得到结果比百分百准确的值更加重要),后来甚至成为了一种商品,我们耳熟能详的伽利略甚至还制造并卖出过 100 多副计算尺。


(图 1.7 计算尺

有意思的是,中国历史上最早使用计算尺的是康熙皇帝,他使用的是一把象牙制的甘特式计算尺,当时称为假数尺。康熙时代的假数尺有四种类型:假数尺、正弦假数尺、切线假数尺、割线假数尺。我们可以在故宫博物院看到多把康熙御制的铜质和象牙假数尺。

1.1.5 帕斯卡与莱布尼兹

对于某些场景来说,计算尺的简单灵活比准确性更加重要,但是对于诸如银行业来说,计算的准确性更加重要。随计算尺而蓬勃发展的产业就有精密制造业,而对于准确时间的渴望最终催生了机械表的诞生,而齿轮转动天然具有的进位功能给了帕斯卡灵感。1642年,法国数学家、物理学家和化学家帕斯卡为了帮助负责税务计算工作的父亲,设计了一台“帕斯卡计算器”。虽然因为造价高昂只卖出了大约 15 套,但却是计算历史又一次革命。

前面提到算筹和算盘本质上是寄存器,用来保存计算结果,而具体的计算过程需要人手工完成,但帕斯卡计算器利用齿轮和内部结构自动完成了简单的加减法运算,即使一个人不会加法,但只要学会了帕斯卡计算器的使用,同样可以得到正确结果。更重要的是,整个的计算逻辑除了输入外不需要人干预,避免了因为不仔细而导致的错误。于是计算器真正成为了拥有计算能力的机器,而不只是辅助计算用的工具。

(图 1.8 帕斯卡计算器

帕斯卡计算器的用法也非常简单,上面的一列是显示数字的小窗口,下面对应着指针和拨轮,输入的时候只需要像拨盘电话一样输入数字即可即时显示结果(具体可见习题中的演示)。因为齿轮是可以双向转动的,所以只要以不同的方向转动,就可以完成加法和减法。因为乘除法能够转换为加减法,所以如果不怕操作麻烦,是可以通过重复加来完成乘法的。这里又一次体现了设计与限制,如果有一个数字大于六位,如上图所示的帕斯卡计算器就无能为力了。

与帕斯卡同时代的德国数学家莱布尼兹也对机械化的计算工具颇有研究,1673 年,莱布尼兹制作出了第一个真正的四则运算器,称为『步进计算器』。它由两部分组成,第一部分与帕斯卡计算器类似,用于计算加减法;第二部分采用了专门设计的乘法器和除法器,通过控制齿轮转动的角度,产生了相当复杂的计算能力,这种设计被称为『莱布尼兹轮』,使得一个齿轮可以表示从 0 到 9 十位数字。莱布尼兹轮几乎是接下来 275 年各种计算器的基础,这简直是一个不可能打破的记录!试想,现在还有什么东西是一次发明能『统治』差不多三个世纪的呢?


(图 1.9 步进计算器

帕斯卡做计算器是为了辅助税务计算,但是莱布尼兹做计算器是为了什么呢?答案是为了算人口。因为这类机械计算工具造价高昂,基本只有政府才有能力和意愿在背后支持。而作为人类历史上第一个拥有四则运算能力的计算器,虽然因为价格昂贵而没有能够推广开来,但是机械计算器的领域已经彻底被打开,在等待合适的时间爆发出惊人的力量。

1.1.6 差分机与分析机

帕斯卡和莱布尼兹发明的计算器虽然在原理的先进性上大大超越了算盘和计算尺,但是放到实际使用中,繁琐的操作反而大大降低了工作效率。虽然计算过程过程已经不需要人参与,但是仅输入数据这一项,就需要花费太多的时间,并且在后续计算结果出来之后,仍然需要人工去收集统计,在这样的使用场景下,还不如直接用算盘来得方便。

终于,在帕斯卡计算器出现大约 200 年之后,大航海时代的开启,原来依赖于查表所能提供的精度已经难以满足工程师、航海家和商人的需求。这时,英国人巴贝奇站了出来,决心把脑海中的想法实现出来,这就是现代计算机的雏形。在英国政府的支持下,巴贝奇在 1822 年开始了差分机的设计和制造,希望将从计算到印刷的过程全部自动化,这样就可以避免人为误差。差分机使用有限差分方法来机器计算多项式函数的值。有限差分方法是个简单但功能强大的技巧,它用重复加减的过程来避免需要的乘法和除法。不过由于当时制造工艺水平较低,这个 10 英尺高,10 英尺宽,5 英尺长,重 2 吨,以蒸汽机驱动的庞然大物在 10 年间只完成了七分之一,看不到未来的英国政府不得不停止了对该项目的支持(毕竟按照这个趋势,要 70 年才能完成)。

(图 1.10 差分机一号已完成的七分之一)

即使只有七分之一,即使一万多个还没用到的零件最终被熔解,差分机依然拥有重要的历史意义。最高可以读写 16 位数的差分机,可以看作是人类踏进计算机科学最重大的起步。

虽然失去了政府的支持,但是在设计和制造差分机的十年让巴贝奇有了设计更强大机器的能力,更加精密的分析机因此面世,它能用多项式展开的方法计算对数和三角函数,具体的计算过程则是用打孔卡片输入,完成类似汇编语言的程序指令。设计和尝试建造这个充满传奇色彩的机器成了他整个下半生的梦想。这个分析机的设计理念比差分机更超前,向未来穿越了大概一个世纪。

说到打孔卡片,最初来源于纺织行业,用来控制织布机。打孔卡片上的每一个可打孔位置对应一个钩子,而该处打孔与否决定对应的钩子是抬起还是放下,从而控制钩子上的悬挂的线走在布的上边还是下边,这样就可以自动织出图案了。正因如此,巴贝奇选择打孔卡片作为输入就不无道理了。

(图 1.11 分析机部分组件的实验模型,巴贝奇自制,现藏伦敦科学博物馆)

它的“内存”是由齿轮组成的,齿轮位置记录数字。它们大约可以存储1000个40位的十进制数(约16.7 KB)。

机器有一个算术单元,就是现在说的CPU,用来进行四则运算、比较和求平方根操作。运算的基本原理与帕斯卡的转轮相似,但他改进了进位装置,使得40位数加40位数的运算可完成于一次转轮之中。它做一次20位乘40位的运算只需两分钟。虽然这个速度与现代电子计算机根本不可比,但当时已经是很惊人的了。

分析机还有自己使用的编程语言,它类似于现代的汇编语言。这个语言支持循环和条件分支,按现在的名词来讲它是图灵完备的。

分析机用三种不同类型的打孔卡片进行输入。(还记得前面专门提到打孔卡片吧!)第一种用于算术运算,第二种用于记录数字常数,而第三种用于加载和存储操作,和在存储单元到算术单元之间来传递数字。这三个类型的卡是相互独立的。

这不就是不用电的计算机吗?一个多世纪过去后,现代电脑的结构几乎就是巴贝奇分析机的翻版,只不过是主要部件换成了集成电路而已。

非常可惜的是,巴贝奇可能过于理想主义,忽略了大项目的风险,因为资金的不足和技术的限制,这部超越时代的机器并没能制作出来,但是计算机的火种已经燃烧起来,并在一百年之后成为了足以影响人类社会发展的举足轻重的力量。

1.1.7 打孔卡片

前面提到的各种计算机制,唯一离不开的是手,我们需要用手来完成输入的动作,无论是算筹的摆放、算盘的拨动、计算尺的滑动还是莱布尼兹轮的转动,都需要手。而作为早期办公自动化的产物,打孔卡片的出现,标志着人类从『做运算』到『处理数据』这一转变的序幕正式拉开。在卡片上打出的孔可以表示任何信息,更重要的是,孔一旦打下,信息也就保存了下来。

真正使得打孔卡片流行起来背后的原因其实和莱布尼兹轮的出现背景一样——算人口。美国每十年会进行一次人口普查,1790 年的时候不到四百万人,人工统计还说得过去。一个世纪之后人口增长到了六千三百万,这就是一个浩大的工程了。统计局的人估计了一下,1890 年的统计如果还用原来的方式,到 1900 年都没办法统计完,这可怎么办?

于是政府决定举办一场竞赛,看谁能想到快速完成人口统计的方法,这一次赫尔曼·何乐礼摘得桂冠。他的方法是把数据记录在打孔卡片上,六千多万张打孔卡片就如下图所示般手动『喂』给制表机完成统计。一位操作员平均每天可以用这种方法处理七千多张卡片,足足比人工统计快了十倍。正因如此,何乐礼被广泛认为是现代机械数据处理之父。随着他发明的制表机,自动数据处理的时代开启。

何乐礼顺势在 1895 年成立了制表机器公司,向全世界的人口统计局推售自己的产品。可能制表机器公司听起来有些陌生,如果我说它在 1924 年改名为 IBM,相信没有多少对计算机感兴趣的同学没有听过了吧。

从十九世纪三十年代到七十年代,打孔卡片统治了数据处理领域,而 IBM 则统治了打孔卡片本身。我很不能理解为什么我们的课本只教大家从历史中得出一堆大道理,完全可以理论结合实际嘛。

从 THINK 到不断创新,IBM 之所以能够独领风骚数十年,正是把研究(Research)和开发(Develop)完美结合的典范,或者说,R + D = $,就是这么简单。

1.1.8 本节总结

从算筹到打孔卡片,同样是利用位置进行记录,却用了近四千年才完成了从手动到机械的转变(这一点几乎所有教材都没有提及它们之间的关联)。算筹代表的是最原始的计数方式,而打孔卡片则是近代的方式,为开启数字时代之门做出了举足轻重的贡献。

在漫长的历史中,人们用各种各样的方法尝试着让计算更加简单可靠,最终发现只有摆脱『人』这个变量,才能得到效率的极大提升(也许不该用『摆脱』,应该用『解放』)。而从手动到机械的转变则像是即将燎原的星星之火,随着从模拟到数字这阵东风,让整个理工科沸腾了起来。

番外 第一位程序员——艾达的故事

对计算机感兴趣的同学,恐怕都知道艾达(Ada Lovelace)是举世公认的第一位程序员。但为什么偏偏是艾达迈出了这一步,而且还是在十九世纪初的欧洲(那时很多女性都没有接受教育的权利)?

这就要从艾达的身世说起了。艾达的父母均非无名小辈,父亲是著名诗人乔治·戈登·拜伦,母亲安妮·伊莎贝拉·米尔班奇是人称『平行四边形公主』的业余数学家。而艾达从小就对数学有着极高的兴趣,除了家庭教师的悉心指导,后来更是直接受奥古斯都·德·摩根的教导(奥古斯都·德·摩根是现代计算机数学基础布尔代数的创始人之一)。

有意思的是,艾达的家庭教师之一玛丽·索麦维正好和巴贝奇是朋友,所以艾达在 17 岁的时候看到了当时正在建造的差分机,从此便与计算机结缘。九年之后,正当巴贝奇失去政府资助,大家也觉得他的工作毫无价值的时候,一位伯爵夫人上门拜访,这位伯爵夫人就是艾达(当时艾达已经与比她大十岁的教廷教师威廉·金结婚,后者于 1838 年继承了贵族头衔)。

艾达之后便热心参与到了差分机与分析机的相关工作,把巴贝奇对于分析机的设想从法语翻译成英文,并添加了许多注释,最终成稿是原文的三倍。即使做出了如此大的贡献,她也仅仅是在署名的时候使用 A.A.L 这个缩写。在文稿的附录中,艾达详细说明了使用分析机计算伯努利数的方法,这是第一个计算机程序,自然,艾达也就成为了第一位程序员。

(图 1.12 艾达编写的计算伯努利数的程序)

不仅如此,艾达对于计算机的认识也是极具前瞻性的,提出了编程语言、通用计算以及人工智能的早期概念,这些连巴贝奇自己都没有想过!可惜的是,因为长期的艰苦研究,艾达与 1852 年 11 月 27 日逝世,年仅 37 岁,最后葬于拜伦家族的墓地中。但她的精神一直流传了下来,艾达的座右铭是:

工作是我的报酬。

艾达对于计算机科学的意义可谓重大,有叫 ADA 的编程语言,有以其生日 1815 年为编号的军方项目,有把她的全息图标签放到产品中的,还有以艾达为名的计算机奖项。这不,谷歌在艾达诞辰 197 周年时(即 2012 年 12 月 10 日)还专门制作了 doodle,以庆祝和鼓励在技术中做出贡献的女性。


(图 1.13 谷歌于 2012 年 12 月 10 日的首页截图)

捧个钱场?