算法:Donald Knuth 除法算法混淆

Question

我正在尝试实现一个除以两个大精度数字的程序(我将它们作为字符串)。来自 Stack Overflow 上其他问题的人建议实现 Donald Knuth 的 The Art of Computer Programming 一书中解释的算法。在阅读过程中，我对算法有了一个大概的了解，但我在某些地方感到困惑。

1. 该算法使用长除法的概念。我一直不明白程序是如何在执行算法时“猜测”商的数字的。

2. 即使它“猜”到，我应该如何将被除数的部分除以除数？假设我必须将除数转换为 int...

3. ...如果除数很大怎么办？问题不是一样吗？

我们将不胜感激。

提前致谢。

Answer 1

我只能建议，除法可以通过除法器和被除数之间的数字之间的差异来实现。然后将除法器与基于数字差异的一些猜测相乘并对其进行更改，直到获得所需的输出。是的，如果计算非常大的数据，您必须编写自己的加法、乘法函数并使用数组。

更新通过术语基本提示。假设，1923/695作为|695| = 3，取被除数的前3位，尝试除法。由于 193<695 加商 0，除法加一位。现在我们必须将 1923 除以 695。这个算法的优点是您每次都必须猜测 1-9 之间的数字。要优化和减少猜测次数，您可以实现 if 条件，例如，如果除数 > 除数*5，您的猜测将是 6、7、8 和 9。等等。

我以前用这个方法计算大数的阶乘。希望这对您也有帮助。