如何对大量数字（大数）进行长除法 [英] How to implement long division for enormous numbers (bignums)

问题描述

我正在尝试对bignums执行长除法。不幸的是，由于嵌入式编程的限制，我无法使用GMP之类的库。此外，我想学习如何实施它的智力练习。到目前为止，我已经使用任意长度的字节数组完成了加法和乘法运算（所以每个字节都像一个以256为基数的数字）。

I'm trying to implement long division for bignums. I can't use a library like GMP unfortunately due to the limitations of embedded programming. Besides, i want the intellectual exercise of learning how to implement it. So far i've got addition and multiplication done using any-length arrays of bytes (so each byte is like a base-256 digit).

我只是在尝试开始实施除法/模数，我想知道从哪里开始？我在网上发现了很多高度优化（即不可读）的代码，这对我无济于事，而且我发现了很多技术性很高的数学白皮书，因此无法弥合理论与实现之间的鸿沟

I'm just trying to get started on implementing division / modulus and i want to know where to start? I've found lots of highly-optimised (aka unreadable) code on the net, which doesn't help me, and i've found lots of highly-technical mathematical whitepapers from which I can't bridge the gap between theory and implementation.

如果有人可以推荐一种流行的算法，并向我指出一个易于理解的解释，而这种解释倾向于实现，那就太好了。

If someone could recommend a popular algorithm, and point me to a simple to understand explanation of it that leans towards implmenentation, that'd be fantastic.

-edit：我需要在股息为〜4000bits，除数为〜2000bits时起作用的算法

-edit: I need algorithms which work when the dividend is ~4000bits, and divisor is ~2000bits

-edit：Will此算法与base-256一起工作吗？ http://courses.cs.vt.edu/~cs1104/ BuildingBlocks / divide.030.html

-edit: Will this algorithm work with 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

-edit: Is this the algorithm (newton division) i should really be using? http://en.wikipedia.org/wiki/Division_(digital)#Newton.E2.80.93Raphson_division

推荐答案

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

If you want to learn, then start with the pencil and paper method you used in elementary school. Believe it or not, that is essentially the same O(n^2) algorithm that is used in most bignum libraries for numbers that are in the range you are looking for. The tricky first step is called "quotient estimation", and that will probably be the hardest to understand. Once you understand that, the rest should come easy.

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

A good reference is Knuth's "Seminumerical Algorithms". He has many discussions about different ways to do quotient estimation both in the text and in the exercises. That book has chapters devoted to bignum implementations.

这篇关于如何对大量数字（大数）进行长除法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！