1、机械计算起源

        最近在想平衡三进制的除法，想看看那么大牛是怎么做的，资料很少，但还是有的，有但是看不懂，也不知靠不靠谱，后面跟着实践了能行，下面就看看Balanced Ternary Arithmetic，这个高德纳(Donald Knuth)写出有关平衡三进制的文章，而这思路又起源于巴贝奇的机械结构。

        巴贝奇最牛的地方在于，他将人的数学计算，转变成了机械可以运算的的题，在1834年的夏天到1836年期间，他给它的新引擎注入了令人赞叹的功能，他设计了第一个自动装置，可用于直接乘法与除法，它的除法过程也很特别，很震撼，他指出：“机器的算术运算，没有什么比这更困难的了”，在查尔斯·巴贝奇的分析机出现后，也演变出了手摇或电动机械计算器，接下来看看Integer Long Division的文章，它们是如何实现除法的。

---

2、十进制机械除法

        最简单的除法就是减法，10/3就是10-3-3-3=1，所以就是商3余1，也就是累计可以减多少次，剩下多少就是余数，下面是以1234/38为例：

这种是不移位重复减法，注意了上面p是变成了负数的，然后又变了回来，为什么这样做，是因为机械齿轮的设计，很难分辨数的大小，就算是能分辨，设计也很复杂，还不如一直减，直到负数停止，然后再回退上一步的结果，也就是结束后再加回去，它的运算过程：

1. 清除寄存器【r】的结果
2. 重复从【p】中减去【q】,每次都将1加到结果寄存器【r】中，直到【p】变成负数
3. 撤消之前的减法，将【p】加上【q】，结果寄存器【r】减1，得到上一步的结果，除法完成：最终商在【r】中，余数在【p】中。

---

        上面的方法，虽然简单暴力，但是效率很差，举一个极端的例子：100000000000/1，如果重复的相加那么手摇计算机，就变成的健身器材了，这并不是我们想要的，所以就有了第二版，有移位的减法，如下所示：

        上述除法思路，用的还是巴贝奇的想法，根据结果采取适当的措施，即： 用试探性减法，直到结果为负数，而得到负号，就表示数字多了一个，通过加法恢复正确的数字，然后将商乘以10，重复进行减法运算；通过计算，每个阶段在符号位变化前执行的减法次数，可依次生成除法结果的各位；也就是1234/38，不断的在38后面加0，到2个位移<<，加2个0时，得3800，1234变成负数，然后撤消之前的减法，得到1个位移<，（即r左移1位变成00，q右移1位变成380），然后减1次就加-380，加到第4次时又变负数，撤消之前的减法，得到0个位移<，4变成3，商乘于10变成30，(即r左称1位变30，q右称1位得38)，然后减1次就加-38，再次减负数，这时除法结束，最后一次撤消之前的减法(与原q相同,无移位)，得到最后的商32和余数18，它的运算过程：

1. 清除寄存器【r】的结果
2. 通过将【q】向左移并用移位机制（s）跟踪，将【q】的最高位与【p】的最高位对齐
3. 反复从【p】中减去【q】，每次都在结果寄存器【r】中加1，直到【p】变成负数
4. 通过【p】加回【q】，并将【r】减1，撤消之前的减法。看【q】是否要移位；若是，则将【r】左称1位，将【q】右移1位，回到步骤3继续开始。
5. 否则，【q】不再移位，则除法完成，最终商在【r】中，余数在【p】中。

---

3、平衡三进制除法

       最终讲这一部分了，这个是高德纳写的，符号他直接采用了-1、0、1，这个排版起来，不太好看懂，下面我还是用+\0\-来说明，如下图所示：

        这个平衡三进制除法很特别，首先，将被除数分成两个向量 p 和 s，其中 p 的位数最多与除数 (q) 相同，s 是剩余位数的向量；比如，这+-++-（十进制65） /+--（十进制5），也就是p为+-+，s为+-，而除数q为+--，然后就是除数q乘于(+或-)与被除数p相减（实际上相减1次或2次），直到p位于一个半封闭区间内(上图可知)，每一步的结果(+或-)，都要加到r上去，当 p 减少到位于 q 所限定的区间内时，结果乘以 3（通过附加0）并将 s 的下一位数字转移到 p。当 s 用尽时，结果 r 和被除数 p 构成最终的商和余数。

---

        说实话是不是，看不懂了，没事刚开始我也看不懂，写多两题就懂了，先要清楚它的半封闭区间，它的区间是由除数构成的，也就是p是正数时，0<=p<5这区间，当p是负数时，0>=p>(-5)这区间，如下图右下角的区间示意图；它的运算过程，就是将【p】减去【q】，然后判断【p】是否在这两个半封闭区间内，不是则继续减，实际只要减去1次或2次就可以了，符合后将 s 的下一位数字转移到 p中，结果乘于3（通过附加0），这也非常简单的，下面就用+-++-（十进制65） /+--（十进制5）例子，计算如下：

        共算了三步，每一步，都只相减了1次，也就是+-(十进制2)，当p与q符号相同时上+，反之上-，它们相减等于加上它的相反数，而余数2是在这两个半封闭区间内，所以就可以转移s，当s都移完了，就可以得商+++(十进制13)和余数0。

---

此方法是通用的，下面继续算10/-2，如下图所示：

在上图中，符号不同则上了-，然后第一轮相减得1，符合半封闭区间，进行下一轮，r的-变-0，然后+变++，与-+相减1次得2，但半封闭区间不包含2，所以要再相减1次得0，符合半封闭区间，s用完，结果即（-0）+（-+），得到-++(十进制-5)和余数0，结果正确。   

---

下面，再来一题：+0++0+(十进制280)/+0-(十进制8)

这个最有用的就是提醒你，什么时候是上0，而不是只上+或-，也就是当s的位数移过来时，并没有相减时，也符合半封闭区间，所以就上0了，虽然上0了但移位还是要的，这里有4个步骤，所以结果是++0-（27+9+0-1=35）和余数0，结果正确。

---

最后，来2道简单的，4/2及9/2，如下图：

这文章Balanced Ternary Arithmetic中还有很多有趣方法，比如快速除于3的方法等，细细品读，你会获得不一样的收获，比如头顶掉落的一撮毛。。。