如何对大量数字（bignums）实施长除法
我正在尝试为 bignum 实现长除法。不幸的是，由于嵌入式编程的限制，我无法使用像 GMP 这样的库。此外，我想要学习如何实施它的智力练习。到目前为止，我已经使用任意长度的字节数组完成了加法和乘法（因此每个字节就像一个基于 256 的数字）。
我只是想开始实施除法/模数，我想知道从哪里开始？我在网上找到了很多高度优化（又名不可读）的代码，这对我没有帮助，而且我发现了很多技术含量很高的数学白皮书，从中我无法弥合理论和实现之间的差距。
如果有人可以推荐一种流行的算法，并为我提供一个简单易懂且倾向于实现的解释，那就太好了。
-编辑：我需要在被除数约为 4000 位且除数约为 2000 位时起作用的算法
-编辑：此算法是否适用于 base-256 ？ http://courses.cs.vt.edu/~cs1104/ BuildingBlocks/divide.030.html
-编辑：这是我真正应该使用的算法（牛顿除法）吗？ http://en.wikipedia.org/wiki/Division_(数字）#Newton.E2.80.93Raphson_division
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: I need algorithms which work when the dividend is ~4000bits, and divisor is ~2000bits
-edit: Will this algorithm work with base-256 ? http://courses.cs.vt.edu/~cs1104/BuildingBlocks/divide.030.html
-edit: Is this the algorithm (newton division) i should really be using? http://en.wikipedia.org/wiki/Division_(digital)#Newton.E2.80.93Raphson_division
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
如果你想学习，那就从你小学时用的笔和纸的方法开始。不管你相信与否，这本质上与大多数 bignum 库中使用的 O(n^2) 算法相同，用于计算您正在寻找的范围内的数字。棘手的第一步称为“商估计”，这可能是最难理解的。一旦你明白了这一点，剩下的事情就很容易了。
一个很好的参考是 Knuth 的“半数值算法”。他在课文和练习中多次讨论了进行商估计的不同方法。那本书有专门讨论 bignum 实现的章节。
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.
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.
这个问题已有 2 年多了，但是对于这个大小的数字，您可以查看 OpenSSL 源代码。它使用这种大小的数字进行 RSA，因此有许多针对 1000 到 4000 位数字进行优化的数学例程。
This question is over 2 years old, but for this size numbers you can look at the OpenSSL source code. It does RSA with this size numbers so has lots of math routines optimized for 1000 to 4000 bit numbers.
您是否在代码中使用 void Four1(long double[],int,int) ，然后进行卷积，然后进行逆变换？我得到了乘法，但是当我尝试以相同的方式进行除法时，它会输出一个结果退出，所以我无法帮助，但如果你有一本名为“C++ 中的数字食谱”的书，请转到接近结尾处，你会发现你正在寻找的内容实际上是从第 916 页到第 926 页开始的。
Are you using the void Four1(long double[],int,int) in your code and then convolving and then doing a inverse transform well I got multiplication to work but when I tried to do division the same way it spat out one result then quit so I cannot help but if you have the tome called "Numeric Recipes in C++" go to near the end and you will find what you are looking for actually it starts on Page 916 to 926.