除以非常大的数的算法
我需要编写一个算法（我不能使用任何第三方库，因为这是一个作业）来除（整数除法，浮动部分不重要）非常大的数字，例如 100 - 1000 位数字。我找到了 http://en.wikipedia.org/wiki/Fourier_division 算法，但我没有知道这是否是正确的方法。您有什么建议吗？
1) check divisior < dividend, otherwise it's zero (because it will be an int division)
2) start from the left
3) get equal portion of digits from the dividend
4) if it's divisor portion is still bigger, increment digits of dividend portion by 1
5) multiply divisor by 1-9 through the loop
6) when it exceeds the dividend portion, previous multiplier is the answer
7) repeat steps 3 to 5 until reaching to the end
I need to write an algorithm(I cannot use any 3rd party library, because this is an assignment) to divide(integer division, floating parts are not important) very large numbers like 100 - 1000 digits. I found http://en.wikipedia.org/wiki/Fourier_division algorithm but I don't know if it's the right way to go. Do you have any suggestions?
1) check divisior < dividend, otherwise it's zero (because it will be an int division)
2) start from the left
3) get equal portion of digits from the dividend
4) if it's divisor portion is still bigger, increment digits of dividend portion by 1
5) multiply divisor by 1-9 through the loop
6) when it exceeds the dividend portion, previous multiplier is the answer
7) repeat steps 3 to 5 until reaching to the end
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
我想像小学那样划分“长”路将是一条潜在的路线。我假设您收到的是字符串形式的原始数字，所以您要做的就是解析每个数字。示例：
步骤 0：
步骤 1：“13 能进 4 几次？ 0
步骤 2：“13 能进 45 进多少次？ 3
步骤 3：“13 可以变成 63 多少次？4
等等。通过这种策略，您可以拥有任意数字长度，并且只需要在内存中为 int（除数）和 double（被除数）保留足够的数字。 （假设我正确地理解了这些术语）。
当您到达没有数字剩余的点并且计算不会进行 1 次或多次时，您将返回结果，该结果已经是。格式化为字符串（因为它可能比 int 更大）。
I'd imagine that dividing the 'long' way like in grade school would be a potential route. I'm assuming you are receiving the original number as a string, so what you do is parse each digit. Example:
Step 0:
Step 1: "How many times does 13 go into 4? 0
Step 2: "How many times does 13 go into 45? 3
Step 3: "How many times does 13 go into 63? 4
etc etc. With this strategy, you can have any number length and only really have to hold enough digits in memory for an int (divisor) and double (dividend). (Assuming I got those terms right). You store the result as the last digit in your result string.
When you hit a point where no digits remain and the calculation wont go in 1 or more times, you return your result, which is already formatted as a string (because it could be potentially larger than an int).
对于大数来说，最简单的除法算法是移位和减法。
这种转变不必是字面意义上的。例如，您可以编写一个算法来从另一个值中减去左移值，而不是在相减之前实际将整个值左移。比较也是如此。
长除法很难实现，因为长除法的步骤之一就是长除法。如果除数是一个 int，那么你可以很容易地进行长除法。
The easiest division algorithm to implement for large numbers is shift and subtract.
The shifting need not be literal. For example, you can write an algorithm to subtract a left shifted value from another value, instead of actually shifting the whole value left before subtracting. The same goes for comparison.
Long division is difficult to implement because one of the steps in long division is long division. If the divisor is an int, then you can do long division fairly easily.
Knuth, Donald，《计算机编程艺术》，ISBN 0-201-89684-2，第 2 卷：半数值算法，第 4.3.1 节：经典算法
Knuth, Donald, The Art of Computer Programming, ISBN 0-201-89684-2, Volume 2: Seminumerical Algorithms, Section 4.3.1: The Classical Algorithms
您可能应该尝试诸如长除法之类的方法，但使用计算机单词而不是数字。
在高级语言中，最方便的做法是将“数字”视为最大固定精度整数大小的一半。对于长除法，您需要处理部分中间结果可能相差一的情况，因为固定精度除法只能处理任意精度除数的最高有效部分。
有更快、更复杂的方法来进行任意精度算术。查看相应的维基百科页面。特别是，当仔细实施时，牛顿-拉夫森方法可以确保除法的时间性能在任意精度乘法的恒定因子内。
You should probably try something like long division, but using computer words instead of digits.
In a high-level language, it will be most convenient to consider your "digit" to be half the size of your largest fixed-precision integer. For the long division method, you will need to handle the case where your partial intermediate result may be off by one, since your fixed-precision division can only handle the most-significant part of your arbitrary-precision divisor.
There are faster and more complicated means of doing arbitrary-precision arithmetic. Check out the appropriate wikipedia page. In particular, the Newton-Raphson method, when implemented carefully, can ensure that the time performance of your division is within a constant factor of your arbitrary-precision multiplication.
除非你的作业的一部分是完全原创的，否则我会使用我（我假设你）在小学教过的手工进行大除法的算法。
Unless part of your assignment was to be completely original, I would go with the algorithm I (and I assume you) were taught in grade school for doing large division by hand.