division - 如何对大量数字(bignums)实现长除法

Question

我正在尝试为bignums 实现长除法。不幸的是，由于嵌入式编程的限制，我无法使用像 GMP 这样的库。此外，我想要学习如何实现它的智力练习。到目前为止，我已经使用任意长度的字节数组完成了加法和乘法(因此每个字节就像一个基于 256 的数字)。

我只是想开始实现除法/模数，我想知道从哪里开始？我在网上找到了很多高度优化(又名不可读)的代码，这对我没有帮助，而且我发现了很多技术含量很高的数学白皮书，从中我无法弥合理论和实现之间的差距.

如果有人可以推荐一种流行的算法，并为我提供一个易于理解且倾向于实现的解释，那就太棒了。

-编辑:我需要在被除数约为 4000 位且除数约为 2000 位时起作用的算法

-编辑:该算法适用于 base-256 吗？ http://courses.cs.vt.edu/~cs1104/BuildingBlocks/divide.030.html

-编辑:这是我真正应该使用的算法(牛顿除法)吗？ http://en.wikipedia.org/wiki/Division_(digital)#Newton.E2.80.93Raphson_division

Answer 1

如果你想学，那就从你小学时用的笔和纸的方法开始。不管你相信与否，这本质上与大多数 bignum 库中使用的 O(n^2) 算法相同，用于计算您正在寻找的范围内的数字。棘手的第一步称为“商估计”，这可能是最难理解的。一旦你理解了这一点，剩下的就很容易了。

Knuth 的“半数值算法”是一个很好的引用。他在课文和练习中对商估计的不同方法进行了许多讨论。那本书有专门讨论 bignum 实现的章节。