字符串中的大数除法 [英] Division of large numbers in strings

问题描述

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

I wrote a program to divide large numbers using strings in C++. That is a string is used to store each digit of the number. I used continuous subtraction to get the remainder and quotient.

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

但是问题是这种方法对于非常大的数非常慢。
还有什么其他方法可以使其更快？

But the problem is this method is extremely slow for very large numbers. What other possible method is there to make it fast?

推荐答案

一种用于快速进行bignum计算的方法是使用

One approach to get fast bignum computation is to use high values for the base.

例如，考虑总和

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

当手工进行此计算时，您从最右边的数字开始并对其求和，如果结果超过9，则牢记进位。从右至左3 + 3 = 6，4+ 2 = 6、3 + 8 = 1 +携带1、2 + 8 + 1 = 1 +携带1，依此类推。

When doing this computation by hand you start from rightmost digit and sum them keeping a "carry" in mind if the result gets past 9. From right to left 3+3=6, 4+2=6, 3+8=1+carry 1, 2+8+1=1+carry 1 and so on.

但是您可以做的是计算多个位数的块...例如

What you can do is however do the computation in multiple digits chunks... for example

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，依此类推。

This is the same computation as before but now I'm using base 1000 instead of base 9 (digits go from 000 to 999) and I can use the same approach. Rightmost digit is 343+823=166 carry 001, 342 + 384 + 001 = 691, 922 + 932 = 854 carry 001 and so on.

进行乘法运算（除法算法也需要），对于32位整数的基数的合理选择是9999，因为9999 * 9999仍然小于2 ** 32，因此可以直接计算而不会溢出。

To be able to easily do multiplications (needed also for the division algorithm) a reasonable choice for the base with 32-bit integers is 9999 because 9999*9999 is still less than 2**32 and so can be computed directly without overflows.

使用10 ** n形式的基数可以轻松地一次以十进制数字输出结果。

Using a base in the form of 10**n makes it easy to print out results in decimal one digit at a time.

这篇关于字符串中的大数除法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！