十进制大数除法算法

Question

编辑：我将我的 bignum class 重新设置为使用 std::bitset 并且我刚刚实现了长除法。我只是不知道任何 class 来存储位。（喜欢std::bitset）

我正在用 std::string 制作一个 bignum class 以使用十进制字符作为内部表示。我尝试用一个简单的算法实现除法：

while N ≥ D do N := N - D end return N

当然它很慢。我尝试实现长除法，但是用小数字符做这太难了。

提前致谢。

Answer 1

与其经常减去 D，不如尝试找出表格的最大值 D^2n 和子这个。然后用剩余值重复该步骤，直到剩余值小于 D.

伪代码

0 result=0
1 powerOfD = D
2 while (powerOfD*powerOfD<N)
3   powerOfD=powerOfD*powerOfD
4 result = result+powerOfD/D, N=N-powerOfD;
5 if(N>D) 
6   goto 1
7 return result

示例 31/3（N=31，D=3）

0 result=0
1 powerD = 3;
2 3*3 < 31   TRUE
3   powerOfD= 3*3;
2 9*9 < 31   FALSE
4 result=0+9/3; N=31 - 9
5 22> 3   TRUE
6   goto 1
1 powerD = 3
2 3*3 < 22  TRUE
3   powerOfD= 3*3;
2 9*9 < 31   FALSE
4 result=3+9/3; N=22 - 9
5 13> 3   TRUE
6   goto 1
1 powerD = 3
2 3*3 < 13  TRUE
3   powerOfD= 3*3;
2 9*9 < 31   FALSE
4 result=6+9/3; N=13 - 9
5 4> 3   TRUE
6   goto 1
1 powerD = 3
2 3*3 < 4 ALSE
4 result=9+3/3; N=4-3
5 1> 3   FALSE
7 return 10

十进制大数除法算法

Division algorithm with decimal bignum

algorithm