前言
由於計算機編程語言數據類型存儲的限制，無法使用內置的數據類型來進行任意位數字的計算，其中任意位整數四則運算中的除法最難處理。
因此，大整數除法成了很多高校數據結構課程中的課程設計作業。今天為大家帶來一個Java實現的基於二分法和乘法運算反向求解大整數除法的奇葩算法。
二分法
二分法是一些數學運算和眾多數據結構算法的基礎，在介紹算法基本思路之前先簡單回顧下二分法的概念。在數學中，二分法是指函數區間兩端點通過逐步逼近函數零點求得近似值。在數據結構算法中一般還被稱為二分查找，其是指在有序列表中通過折半的方式來搜索指定元素。
二分法示意圖
算法思路
1. 數據存儲與基本流程
計算機程序需要考慮的兩大方面就是算法和數據存儲，其中數據存儲形式會影響到算法的設計，因此根據需求合理設計數據存儲結構非常重要。在本次程序設計中，我們選擇雙向鏈表來存儲大整數數據。
上圖示例中展示了雙向鏈表存儲數據的優勢，這種數據結構既可以滿足大整數輸出顯示的需求，又可以方便進行計算。在Java實現中我們使用LinkedList來存儲大整數數據。
有了大整數存儲數據結構之後，需要設計算法流程，基本流程如下所示：
2. 初始化商
有了數據結構和基本流程就可以開始實現大整數除法算法了。在進行運算之前，為了節省時間成本，我們可以合理的初始化商。以十進制大整數除法運算為例，假設計算 A / B 的結果R，則R的最大位數如下所示：
R.digit = A.digit - B.digit + 1
在確定R的最大位數之後，設置大整數R各存儲節點為節點最大值。以四位數節點為例，其初始化值為9999。這裡為了演示方便，我們設置節點為一位數節點，即最大值為9。則初始化商結果如下：
3. 迭代求值
迭代求值的過程是從初始化商的高位節點開始用二分法的方式設置臨時商，然後通過將臨時商與除數相乘得出的結果同被除數進行比較從而判斷是否終止迭代或在下一次迭代中採取二分法增還是二分法減來調整商。
處理順序是從臨時商的高位到臨時商的低位，從而保證迭代求值的速度。因為高位數值的變動相比於低位數值的變動會有更大波動，從而能夠快速收斂。
在迭代求值過程中有一點非常重要，那就是判斷何時應該停止迭代。停止迭代求值的條件之一就是二分法進逼求值過程中右值和左值的絕對差已經小於等於1，即二分法當前值的波動已經停止。另一個重要條件分為兩種可能，一是上一次迭代的臨時商大於結果，另一種情況是二分法當前值在兩次迭代中不發生改變。
當以上兩條件同時滿足並且無低位節點需要處理時則迭代終止。當最後一次試商比較結果為當前商大於真實結果時，則最終結果需要減一。
節點粒度為1，即節點最大值為9的程序執行結果如下圖所示：
節點粒度為4，即節點最大值為9999的計算示例結果：
優化
通過對結果進行初始化，能夠保證初始化結果的位數與實際結果位數近似，減少不必要的迭代。雖然通過二分法能夠很大程度上節省時間，但在時間複雜度上仍然有很大的提升空間。
比如前面提到試商比較可以合併為一步來提高時間效率，在乘法運算過程中從高位節點開始進行運算，能夠在乘法運算完成前提前返回比較結果，從而節省時間。
這種乘法運算過程好比一條拉鍊，也可以叫它拉鍊式乘法。高位運算如下圖所示：
低位運算如下圖所示：
以上運算示意圖只是一個簡單的演示，實際的拉鍊式乘法運算要比圖中展示的複雜的多。同樣的，從高位向低位運算的目的是為了在運算過程中快速的比較結果以提高時間效率。
在乘法運算過程中，臨時乘積同被除數的比較只能判斷臨時乘積是否大於被除數。當臨時乘積大於被除數時，也就意味著當前臨時商大於實際結果。
待改進
當被除數與除數位數接近時，節點粒度即位數較大時，該算法運行效率會高於Java的BigInteger。但是當位數相差較大時，運行效率會比BigInteger差很多，而已知的耗時較大的部分仍然是試商比較。
另外，在選擇節點粒度時，為了避免節點數值溢出，設置節點最大值為9999。這雖然使得在任何情況下都不會發生溢出，但仍然浪費一些數據存儲的空間。該算法還存在著一些不足，運行效率不如BigInteger那樣穩定，還有待改進。
結語
今天介紹了奇葩的大整數除法，在算法中也使用和熟悉了常見的數據結構。在算法的設計過程中，也能看到與官方算法存在的差距。雖然我們自己設計的算法不會應用於生產項目中，但在此過程中也能夠收穫編碼的快樂。
可在Github中搜索bluesky-algorithm下載源代碼，也可以點擊下方瞭解更多在線查看。大家對於此算法有什麼改進意見可以在評論區留言，期待你們的反饋。《奇葩算法》系列下一期再見。
閱讀更多 程序猿藍天 的文章
