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的方法等，細細品讀，你會獲得不一樣的收獲，比如頭頂掉落的一撮毛。。。