字符串中大数的除法
字符串中大数的除法
提问于 2011-10-29 12:34:42
我在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但问题是，这种方法对于非常大的数字来说非常慢。还有什么其他可能的方法可以让它变得更快？
回答 4
Stack Overflow用户
发布于 2011-10-29 13:58:08
获得快速bignum计算的一种方法是使用较高的基值。
作为一个例子，考虑一下和
12301922342343 +
39234932348823
--------------
51536854691166当手工计算时，你从最右边的数字开始计算，如果结果超过9，你要记住一个“进位”。从右到左依次是3+3=6，4+2=6，3+8=1+carry 1，2+8+1=1+carry 1等等。
然而，您可以做的是以多位数块的形式进行计算。例如
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形式的基数可以方便地一次打印出一个小数形式的结果。
Stack Overflow用户
发布于 2011-10-29 13:37:27
我过去曾尝试过编写bignums程序，我的解决方案是将分子的最高有效位除以分母的最高有效位，并根据刻度差异进行调整。这是答案的第一个数字。将这个乘以分母，然后从分子中减去它。然后以this作为新的分子重复此操作。这就像小学里的长除法一样。
10000 / 3
=10/3 * 1000 + ?
=3*1000 + ?
=3000 + (10000-3000*3)/3
=3000 + (1000 / 3) //repeat recursively from beginning Stack Overflow用户
发布于 2011-10-29 18:20:06
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/7937031
复制相关文章
相似问题
腾讯云开发者
