euclidean除法算法的其餘部分

Question

我使用JavaScript與我自己的BigInteger庫，我對mod函數的複雜性有問題。

// r = big1 - (big2 * (big1/big2)) 
function mod(big1, big2){ 
return subs(big1, multiply(big2, divide(big1,big2))); 
} 

Answer 1

// R = B1％B2

一種不同的方法是通過部分工作模量（說出您要數目限制爲每個數9個位數和說B2 < 100）：

1. 從b1的最左邊的數字開始，使用前9位數字構造一個數字並將其命名爲N.
2. 計算N mod b2，得到範圍在00到99之間的結果（請記住該示例是b2 < 100）。
3. 通過將以上結果（步驟2）與b1的接下來的7個數字連接來構建新的9位數字N.如果在b1中剩餘的位數少於7位，但至少有一位，則從上面的結果（步驟2）中構建一個新的N，它的位數少於9位，然後是b1的其餘數字
4. 重複步驟2 -3，直到b1的所有數字都被處理過

最終結果是b1％b2。如果b2非常大，則這將不起作用，但是如果b1非常大，則可以將其視爲算法目的的字符串。

編碼它應該很容易與迭代，因爲你可以事先知道迭代次數，甚至不需要遞歸。