大數四則運算 in C/C++ - part3 ( 大數的除法 )

開發環境:Visual C++ 2010 sp1 with FFTW 
延續上一次part2的文章，這次要來講解除法怎麼運算，
首先，考慮一個直式的除法，如下，

       ________
123 |   78902

可以看到一開始要先用 789 來除以 123，
這樣就可以得到 789 = 123 * 6 + 51，
以下面直式所示，(run 1)
       ____6___
123 |    78902
           738
----------------------------
             510

接下來就是用 510 來除以 123，
這樣就可以得到 510 = 123 * 4 + 18，
以下面直式所示，(run 2)
       ____64__
123 |    78902
           738
----------------------------
             510
             492
----------------------------
               182

最後就是用 182 來除以 123，
這樣就可以得到 182 = 123 * 1 + 59，
以下面直式所示，(run 3)
       ____641_
123 |    78902
           738
----------------------------
             510
             492
----------------------------
               182
               123
----------------------------
                 59


所以總結以上的過程，除法的演算法就是以 除數的位數為比較位數，
再來拿與被除數一樣位數的數字，進行商的計算，
商的計算可以直接把除數乘以 1 . 2 . 3 . 4 ... BIG_CAP ( 統稱為 x )，
把 x 與 被除數相減，找到等於 0 或者是最小的正整數，
如果找到剛好等於 0 的，商就會是除數的倍數，
如果是最大的負數，商就會是除數的倍數 - 1 ，
再把 被除數 - x 的結果跟被除數下一個位元的數字結合，
重複上述的過程至最低的被除數位數。

以run1來說，被除數 = 789 ， x = 738 ，相減得 51 ，
那下一run就會是 被除數 = 510 ，x = 492，相減得 18 ，
下一run就會是 被除數 = 182 ，x = 123，相減得 59 ，

因為x有排序的關係，所以可以使用二元搜尋法來取代乘以1 . 2 . 3 . 4 ... BIG_CAP
由於我是參考EdisonX大大的文章，所以實作上在這邊不貼出來，請直接參考他的文章。
連結: 點我
To be continue...
下集預告: 神奇的FFT跟大數乘法的關係...