Difference Engine – 差分机

硅谷有一个计算机历史博物馆,很喜欢那里。
那有一个被实现的差分机,看到一个真实的实现在那的时候真的好激动。

diff

差分机,那么就来爽一把吧:

1.f(n)的差分:
\Delta f(n)=f(n+1)-f(n)

2. 从f(n) = n^2开始说起
则我们有:
\Delta f(n) = (n+1)^2 - n^2=2n+1;
\Delta (\Delta f(n)) = \Delta (2n+1)=2;
\Delta (\Delta (\Delta f(n))) = \Delta2 = 0;
为了方便表示,我们把\Delta (\Delta f(n)) 记作\Delta^{2}f(n),把\Delta(\Delta^{2}f(n))记作 \Delta^{3}f(n)
于是可以很容易的知道\Delta^{a+1}f(n)=0,a是f(n)的最高次项的次数

3. 利用差分来计算f(n) = n^3
我们可以列一张表:
f(0),\qquad f(1),\qquad f(2),\qquad f(3) \\
\Delta f(0),\quad \Delta f(1),\quad \Delta f(2)
\Delta^{2}f(0), \quad \Delta^{2}f(1)
\Delta^{3}f(0)
因为我们知道\Delta^{4}f(n)=0,所以最后一行全是常数。
当表中第一行写出来了,下面一行的数只需要根据差分的定义把它左右肩上的两数相减即可得到。
f(n) = n^3代入,上面的表就是:
0, 1, 8, 27
1, 7, 19
6, 12
6
因为我们知道对于任何n,\Delta^{3}f(n)=6, 所以我们又可以把这个表填成:
0, 1, 8, 27
1, 7, 19
6, 12
6, 6, 6, 6, 6, 6, 6, 6, 6,……
又因为根据差分的定义: \Delta^{i} f(n)=\Delta^{i-1}f(n+1)-\Delta^{i-1}f(n),而且我们已知了最后一行的所有值,于是把最后一行往上面一行叠加可得:
0, 1, 8, 27
1, 7, 19
6, 12, 18, 24, 30, 36, 42, 48, 54, ……
6, 6, 6, 6, 6, 6, 6, 6, 6, ……
倒数第二行又可以往上叠加,如此循环往复可得:
0, 1, 8, 27, 64,125, ……
1, 7, 19, 37, 61, 91, ……
6, 12, 18, 24, 30, 36, ……
6, 6, 6, 6, 6, 6, ……

4. 一般化
设f(n)是n的r次多项式,则我们只需要把f(n)的前r个数值算出,机械的列出f(n)的r阶差分三角,我们即可机械性得到对于任意n的f(n)值

5. 加法器的实现
机械上面,使用齿轮实现一个加法器还是很容易的,如下图:
gear

被加数在左边这个齿轮上,加数在右边的齿轮上。齿轮动起来之后左边齿轮的数值就被加上相应转动的齿轮数,如果有进位,会拨动左上角这个小零件表示有进位。

5. 小数的表示
12位的差分机,存储1是这么做的:
000000000001.
加上7
000000000007.
等于
000000000008.
这不会有什么问题。

如果是这样:
000000000001.
除以7
000000000007.
等于
000000000000.
这样就不对了

于是我们这么表示1:
0001.00000000
除以7
0007.00000000
等于
0000.14285714
这样精度就大大的被提高了

6. 负数的表示
与计算机内部一样,用的是补码,不过是10的补
负3:
我们先写一个3
003.000000000

999.999999999


996.999999999
加上
000.000000001

997.000000000
这个就是用补码来表示的-3,和二进制补码一样,首位非0则表示该数是负数

我们来计算7加上-3:
007.000000000

997.000000000

004.000000000
首位为0,表示这是个正数
负数这么表示的重要性在于,我们可以用已有的加法器来实现减法

7. 计算sin,e^x等非多项式函数
我们有泰勒级数呀~
\sin x = \sum_{n=0}^{\infty} \frac{(-1)^n}{(2n+1)!} x^{2n+1}<br /><br /><br /><br /><br /><br /><br /><br />
e^{x} = \sum^{\infty}_{n=0} \frac{x^n}{n!}
利用泰勒级数,我们就可以利用多项式来计算任意函数f(x)

8. 分析机
有了以上的理论基础,疯狂的巴贝奇设计了个惊天地泣鬼神的机器 – 分析机
分析机用了类似汇编一样的语言进行输入,而且是图灵完备的
也就是意味着,我们现代计算机所能实现的功能,分析机都可以实现
这东西在历史上从来没有被实现过。

9. 蒸汽朋克
不同于电磁,机械是可触摸的,更加的形而下一些。
当我第一次看到有人在Minecraft里面实现了一个CPU的那个震撼感觉:
21023932888

用红宝石电路实现了一个电脑!真实可见可触摸的运算电路!
真的很想看看这东西如果是一个真实世界的大楼那样的存在会是何等的壮观。

如果,分析机被实现出来了,会不会是这样的摩天大楼?
如果,科技树是这么点的,我们的世界会不会完全的不一样?
Intel会不会正在宣传他们最新的集成齿轮核心已经做到了10nm工艺?
显示器厂商会不会说他们最新的活字彩色金属屏幕的分辨率已经到了1024*768?
快速傅里叶变换在那个时空会不会成为一个只是很美丽却找不到应用的算法?
20世界最伟大的算法会不会是“快速初值生成算法”?
这种机械体系下,齿轮所在的位置就表示了数值,所以不存在现代内存断电之后数据就消失的问题,也就是说开机是0秒启动。

各种各种可以大开的脑洞~这是人类机械设计智慧的巅峰,只是现代的科技树这里的点似乎都加到机械表上去了…
这是一棵从来没有被点开的科技树,一切的可能性,都只存在手稿上和想象中。
何夕的《伤心者》虚构了一个悲剧的数学家。
巴贝奇是个历史上真实存在过伤心者。
他是不幸的,因为他从来没有能够实现他的设计。
然而他也是幸运的,因为他不是孤独的一个人。
Ada Lovelace看到巴贝奇那个1/7完成版差分机时候,她的眼睛中的亮光,一定是看到了无限可能的未来。

后来,我终于在计算机历史博物馆看到了差分机的实现,听着这迟到了一个半世纪的机器转起来发出咔咔咔咔咔咔咔的声音激动&感动的浑身发抖。