algorithm - 十进制大数除法算法

编辑：我将bignum类重新调整为使用std::bitset并且我刚刚实现了long division fine。我只是不知道有什么类可以存储位。（就像std::bitset）
我正在创建一个bignum类，其中std::string使用十进制字符作为内部表示我试着用一个简单的算法实现除法：
while N ≥ D do N := N - Dendreturn N
当然也很慢。我试着实现长除法，但这对于十进制字符来说太难了。
提前谢谢。

最佳答案

你可以试着找出表单的最高值，而不是经常减去d
D^2n和sub this然后用剩余值重复该步骤，直到剩余值小于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