c++ - 字符串中大数的除法

Question

我用 C++ 编写了一个程序，使用字符串来除大数。那就是一个字符串，用于存储数字的每个数字。我用连续减法得到余数和商。

For ex:
16/5 
Subtract 16-5=11
11-5=6
6-5=1
1 is less than 5 so stop
quotient = 3 and remainder = 1

但问题是这种方法对于非常大的数字来说非常慢。还有什么其他可能的方法可以让它变得更快？

Answer 1

获得快速 bignum 计算的一种方法是使用高值作为基数。

举个例子考虑总和

12301922342343 +
39234932348823
--------------
51536854691166

当手动进行此计算时，您从最右边的数字开始对它们求和，如果结果超过 9，请记住“进位”。从右到左 3+3=6、4+2=6、3+8 =1+进位1，2+8+1=1+进位1，以此类推。

然而，您可以做的是以多个数字 block 进行计算......例如

012 301 922 342 343 +
039 234 932 348 823
-------------------
051 536 854 691 166

这与以前的计算相同，但现在我使用基数 1000 而不是基数 9(数字从 000 到 999)，我可以使用相同的方法。最右边的数字是343+823=166进位001，342+384+001=691，922+932=854进位001等等。

为了能够轻松地进行乘法运算(除法算法也需要)，32 位整数的基数的合理选择是 9999，因为 9999*9999 仍然小于 2**32，因此可以直接计算而无需溢出。

使用 10**n 形式的基数可以很容易地一次打印出一位十进制数的结果。