我编写了一个程序来使用 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
但问题是这种方法对于非常大的数字非常慢。还有什么其他可能的方法可以使它快速？
问问题
4715 次
4 回答
3
获得快速 bignum 计算的一种方法是使用高值作为基数。
例如，考虑总和
12301922342343 +
39234932348823
--------------
51536854691166
手动进行此计算时，您从最右边的数字开始并将它们相加，如果结果超过 9，请记住“进位”。从右到左 3+3=6, 4+2=6, 3+8=1+进位 1、2+8+1=1+进位 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 形式的基数可以很容易地一次打印出十进制的结果。
于 2011-10-29T05:58:07.620 回答
1
我过去曾尝试对 bignums 进行编程，我的解决方案是将分子的最高有效数字除以分母的最高有效数字，并根据比例差异进行调整。这是答案的第一个数字。将这个乘以我的分母，然后从分子中减去它。然后将此作为新分子重复。这就像小学的长除法
10000 / 3
=10/3 * 1000 + ?
=3*1000 + ?
=3000 + (10000-3000*3)/3
=3000 + (1000 / 3) //repeat recursively from beginning
于 2011-10-29T05:37:26.730 回答
0
有一些非常快的（ O(n log n) time ）算法用于 bignum 乘法，因此您可以将其与二进制搜索一起使用以获得 O( n * ( log n )^2 ) 总时间
于 2011-10-29T10:20:06.463 回答
-1
我确实减去了 n* 倍的数字。但是，正如您所说，它很慢。
但考虑一下：
Dividend Divisor
123456789 987
9 digits vs 3 digits
9 digits - 3 digits = 6 , subtract 1 so the factor is 5: 10^5 = 100.000
所以：
9 digits 3+5 digits = 100.000 times
123.456.789 - 987*100.000 = 24.756.789
----------------------------------------------
8 digits 3+4 digits = 10.000 times (now 110.000 times)
24.756.789 - 9.870.000 = 14.886.789
-----------------------------------------------
8 digits 3+4 digits = 10.000 times (120.000 times)
14.886.789 - 9.870.000 = 5.016.789
-----------------------------------------------
7 digits 3+3 digits = 1000 times (121.000 times)
5.016.789 - 987.000 = 4.029.789
-------------------------------------------------
等等...
希望能帮助到你！
于 2014-10-06T20:37:34.413 回答