非常大的数字相除的算法

Question

我需要编写一个算法（不能使用任何第三方库，因为这是一项任务），来除以非常大的数字，例如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

- pocoa

---

如果你能在纸上进行长除法，那么你已经掌握了一个解决这个问题的好算法。 - Carl Norum

@Neil：嗯，我不指望收到代码示例。我只是期望学习一些数学技巧来超越语言的限制。 - pocoa

@pocoa：那你应该添加作业标签。该标签表示你需要帮助/想法/建议，但不希望别人替你完成工作。 - Neil N

@Carl：我认为当你需要用75除以一个120位数时，这并不容易 :) 这就是为什么我在问的原因。 - pocoa

尝试使用牛顿-拉弗森迭代法。在处理数百万位数字等大量数字时，还有一些其他技术可以稍微更快，但牛顿-拉弗森方法更为直接，并且在许多其他问题上非常有用。 - honestann

Answer 1

我认为像小学一样长除法是一个可行的方法。我假设你收到的原始数字是一个字符串，因此你需要解析每个数字。例如：

步骤0：

   /-----------------
13 | 453453453435....

第一步： "13可以被4整除几次？0"

     0
   /-----------------
13 | 453453453435....

步骤2： "13可以整除45多少次？3次。

     03
   /-----------------
13 | 453453453435....
   - 39
     --
      6

第三步： "13能整除63多少次？答案是4"

等等等等……使用这种策略，您可以处理任何长度的数字，并且只需在内存中保留int（除数）和double（被除数）所需的足够位数。 （假设我用的术语是正确的）。将结果存储为结果字符串中的最后一位数字。

当您无法再将计算除以1或更多次时，您返回已经格式化为字符串的结果，因为它可能比int还要大。

- Tejs

---

很久以前，我曾经阅读过一个 MP 库（http://gmplib.org/，我想是这个网站）的源代码。它使用了这种方法来处理“中等大小”的数字（比 long 大，小于约 30 字节），然后对于非常大的数字则切换到 Fourier 除法。有趣的是，看看现在是否仍然采用这种方法。 - Rodney Schuler

@rschuler：傅里叶除法算法可以解决这个问题，对吗？ - pocoa

你的解决方案仅适用于小除数。当除数也是一个大数时，情况会变得更加复杂。 - pocoa

Answer 2

对于大数而言，最容易实现的除法算法是移位减法。

if numerator is less than denominator then finish
shift denominator as far left as possible while it is still smaller than numerator
set bit in quotient for amount shifted
subtract shifted denominator from numerator
repeat
the numerator is now the remainder

移位操作不一定是字面意义上的。例如，你可以编写一个算法，在减去左移后的值之前，而不是实际将整个值向左移动。比较也是一样。

长除法难以实现，因为长除法中的一个步骤本身就是长除法。如果被除数是整数，则可以相对容易地进行长除法运算。

- drawnonward

Answer 3

Knuth, Donald，《计算机程序设计艺术》，ISBN 0-201-89684-2，第二卷：半数值算法，第4.3.1节：经典算法。

- Doug Currie

---

谷歌一下吧，你会发现很多关于对 Knuth 所记录的算法进行“改进”的论文在线上。 - Doug Currie

@pocoa，你应该去学校图书馆借这本书，它非常出色。 - avakar

有没有人在类似C语言的语言中拥有Knuth算法D的1对1的朴素但可行的实现？我被多个步骤所困惑，例如D1引入新数字u_(m+n)，如果d = 1，则应将其设置为0，但是其他情况呢？在步骤D4中，如果任何数字<0，我应该将b^(n+1)添加到所有数字中吗？我要向左边添加的借位应该是1吗？此外，我的大脑难以替换u。D6为什么要将0乘以v_(n-1)？我完全意识到我只是太笨了，无法理解他。我找到了https://skanthak.homepage.t-online.de/division.html，但有许多优化等。 - Peheje

Answer 4

你应该尝试类似长除法的方法，但使用计算机术语而不是数字。

在高级语言中，最方便的方法是将“数字”视为固定精度整数的一半大小。对于长除法方法，您需要处理部分中间结果可能偏离一个的情况，因为您的固定精度除法只能处理任意精度除数的最高有效部分。

有更快更复杂的进行任意精度算术的方法。请查看适当的wikipedia page。特别是，牛顿-拉夫森方法在仔细实现时可以确保您的除法时间性能与任意精度乘法相差不大。

- comingstorm

Answer 5

除非你的作业要求完全原创，否则我建议使用我们（包括你）在小学学习手算大数除法时所学的算法。

- Fletcher Moore

---

是的，如果我找不到更好的算法，我会自己实现 :) - pocoa

设定一个时间限制，不要花太多时间去寻找“更好”的算法。在等待答案的同时，实现小学算法。 :-) - Thomas Matthews

@Thomas：啊哈哈哈..也许这应该是答案！:)) 谢谢提醒！ - pocoa