如何实现大数字的长划分(bignums)

Question

我正在尝试为bignums实施长期划分.由于嵌入式编程的局限性,遗憾的是我无法使用像GMP这样的库.此外,我希望学习如何实施它的智力练习.到目前为止,我已经使用任意长度的字节数组完成了加法和乘法运算(所以每个字节就像一个基数为256的数字).

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

如果有人可以推荐一个流行的算法,并指出一个简单易懂的解释,倾向于implmenentation,那就太棒了.

-edit:我需要的算法在被除数为~4000位时有效,除数为~2000位

-edit:这个算法能用base-256吗？http://courses.cs.vt.edu/~cs1104/BuildingBlocks/divide.030.html

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

Answer 1

如果您想学习，请从小学时使用的铅笔和纸本方法开始。信不信由你，这与大多数bignum库中使用的O（n ^ 2）算法本质上是相同的，即所寻找范围内的数字。棘手的第一步称为“商估计”，这可能是最难理解的。一旦您了解了，其余的就应该变得容易了。

一个很好的参考是Knuth的“ Seminumerical Algorithms”。他在课文和练习中都讨论了不同的商估计方法。那本书有专门讨论bignum实现的章节。