写在前面的:
本文含有大量公式，不一定能成功渲染，请见谅。
Top Image来自这里
有空再补图

差分机是啥?(极简)

差分机简易版本大致如下:
给定一些寄存器,可以看作类似数组a[N] (下标从1开始),这里假设N = 8，有八个寄存器a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8]。
对于第i个寄存器,每次操作使得a[i]加上上次操作后a[i-1]的值。特别的，我们认为a[0] = 0 ，所以第一个寄存器a[1]的值永远不变。

下列表格中，第一列编号表示操作次数，操作0次即为初始状态。我们取a[1]=1 ,a[5] = 3,a[6] = 2 , a[7] = 1加以演示

a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8]
0. 1 0 0 0 3 2 1 0
1. 1 1 0 0 3 5 3 1
2. 1 2 1 0 3 8 8 4

附:一个简单的差分机网站 from SJTU (点我传送)

差分机有啥用?

差分机原理十分简单，而它最大的作用就是用来快速多项式求出值。

考虑一个简单的函数 $ f(x) = x^2 $。

定义差分函数 :
$ f0(x) = f(x) $ 且 $ f_n(x) = f{n-1}(x+1) - f_{n-1}(x)$

我们对其二次差分 $f_1(x) = f(x+1) - f(x) = 2x+1$，而 $f_2(x) = f_1(x+1) - f_1(x) = 2$。可以发现，其二次差分的结果变为了常数，如果再进行更多次的差分，其得到的$ f_n(x)$必定为0。

那这和我们的差分机有啥关系呢？

我们把$f_0(0),f_1(0),f_2(0)$的值作为a[8],a[7],a[6]的初始值，然后进行运算，然后我们会发现，第n次操作后，a[8],a[7],a[6]的值便变成了$f_0(n),f_1(n),f_2(n)$的值。

a[5] a[6] a[7] a[8]
0. 0 2 1 0
1. 0 2 3 1
2. 0 2 5 4
3. 0 2 7 9
4. 0 2 9 16
5. 0 2 11 25

事实上，任意的多项式都可以进行类似的差分操作。对一个最高n次的多项式，我们每次差分会让其最高次减一，因此在经过n次差分操作后，其n次差分函数只有0次,即为一个常数，所以其更高次的差分函数均为0函数。

因此，我们只需知道函数/数列 $f(n)$ 的所有次差分函数在0处的值，即可求出 $f(n)$ 的值。

一些计算相关的问题

一些小技巧与正确性证明

定义 $ a_k = f_k(0) $

性质0

$ fk(n) = \sum{i = 0}^{n}(a_{i+k}*{n\choose i}) $

proof: 显然，对于不同的 $k$，$ fk(n) $ 的形式应当一致，仅仅是求和中初始下标不同。所以我们只需对 $ k = 0 $的情况进行数学归纳即可。( 此时由定义，$f_0(n) = f(n)$ )
对于 $ n = 0 $，显然，$ f(n) = a_0$ 成立
假设对 $ n = m $ 成立，
此时，对于 $ n = m + 1 $，由定义有 $ f(m+1) = f(m) + f_1(m) $。
代入 $ f_k(n) = \sum{i = 0}^{n}(a_{i+k}*{n\choose i}) $ ，

—————其中 $ {n\choose -1} = {n\choose n+1} = 0$。—————
因为 $ {n+1\choose i} = {n\choose i} + {n\choose i-1} $
因此，$ f(m + 1) = \sum_{i = 0}^{m+1} (a_i*{m+1\choose i}) $ ，即假设对 n = m + 1也成立。
由数学归纳法，对 $\forall n \in Z^{+}{\cup}{0}$，假设都成立
因此，性质0成立，

性质1

$ ak = \sum{i = 0}^k ( f(i) \ast ( -1)^{k-i} \ast {k\choose i} ) $

proof: 类似的，假如将0替换为n，我们只需简单地把求和中的 $f(i)$ 替换为 $f(i+n)$ 即可
假设对 $k = m$ 已经成立，则对 $k = m + 1$
则

同理0，我们可以将后两个组合数合并。
因此，假设对 $ k = m + 1 $ 也成立。
由数学归纳法，对 $\forall n \in Z^{+}{\cup}{0}$，假设都成立
因此，性质1成立。

性质0,1の运用

将性质0结合计算器/计算机，可以很快地由原函数 $ f(n) $ 求出差分机中对应寄存器的初始值。即使你可能并不知道 $ f(n) $ 的解析式，你仍然可以接这个差分机来大致预测其之后的走向。

而有时计算题里面如果给定了每个寄存器的值，你也可以通过性质1快速求出一定精度下的 $ f(n) $ 的解析式。

说白了就是为了应付题目，挣分数的事，不寒掺。

差分机二号

附注:更准确的原理请点击跳转

目前的差分器看似已经十分高效了的，但其原型是用纯机械实现的。
我们考虑一次差分机操作，即将寄存器的值加到下一个寄存器，可以用C++代码表示:

1
2
3
4
5
6
7
int re[9]; //re[i]为第i个寄存器的值
//一次差分机操作
void iteration() {
    for(int i = 8; i >= 2  ; --i) {
        re[i] = re[i] + re[i-1];
    }
}

然而，机械结构的加法并不是这么简单。其具体实现是靠齿轮的啮合，齿轮转过的齿数为齿轮的值。

设相邻的 齿轮a 和 齿轮b 的齿数分别为 x 和 y，因为ab啮合，所以a 和 b 转过的总齿数相同。

通过把 齿轮a 转动到0，即可实现齿轮b的值变为 x+y ，进而实现加法。

注意到在这个过程中，齿轮a的值丢失，所以睿智的巴贝奇先生又在两个寄存器间添加了中间齿轮，在齿轮转动的过程中和 齿轮b 保持同样的旋转，这样在 齿轮b 变为 x+y 后，该中间齿轮也会转过 x 齿。在完成加法后，我们只需让中间齿轮和已经被清0的齿轮a啮合，把中间齿轮转回 0 ，即可实现一次加法操作。

可以看出，在每次的加法操作中，需要同时占用相邻的两个齿轮(寄存器)，因此一次差分机操作其实需要7步操作，每步操作使相邻的两个寄存器进行加法，这样效率比较低。

因此，我们可以考虑并行计算，注意到加法只会占用相邻的两个寄存器，我们可以在第一步让寄存器 2n-1 加到 2n 同时操作，第二步让寄存器 2n 加到 2n+1 同时操作，这样就可以只用两步就完成了加法。

相比第一种做法，并行计算提升了寄存器的平均占用率(原先操作每步骤占用率为 2/8，而后面的操作占用率第一步为8/8 第二步为6/8)，加法操作的总数不变，但一步可以同时进行更多次加法，这样的效率提升是十分显著的，尤其对于机械结构。

具体实现可以看如下的表格:
我们先预处理成如下的阶梯阵

a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8]
0. 0 0 1 0 1 0 2 0
1. 1 1 1 1 2 2
2. 2 2 3 4
3. 4 7

第一步后:

a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8]
0. 0 0 1 0 1 0 2 0
1. 0 1 1 1 1 2 2
2. 2 2 2 3 4
3. 4 5 7
4. 12

第二步后:

a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8]
0. 0 0 1 0 1 0 2 0
1. 0 0 1 1 1 1 2 2
2. 1 2 2 2 3 4
3. 4 4 5 7
4. 9 12

可以看出，该计算方式的确可以加速机械结构的运算过程。

End

差分机简易版入门级介绍到此结束。可以看出，差分机的确是一个非常巧妙的机器，其诞生于19世纪早期，不仅巧妙借助齿轮实现了加法的计算，而且还利用了差分函数的性质来快速求出多项式函数的值。甚至对于某些非多项式函数，借助公式我们也能大致模拟其之后的走向。其在加法过程中还运用到了并行计算的思想，而这在计算机的雏形以及思想尚不存在的时代无疑是十分超前的。