7

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

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

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

-edit：我需要在被除数为~4000bits，除数为~2000bits 时工作的算法

-edit：这个算法是否适用于 base-256 ？http://courses.cs.vt.edu/~cs1104/BuildingBlocks/divide.030.html

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

4

3 回答 3

5

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

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

于 2010-07-08T00:06:53.657 回答
1

您是否在代码中使用 void Four1(long double[],int,int) 然后进行卷积，然后很好地进行逆变换，我得到了乘法运算，但是当我尝试以同样的方式进行除法时，它会吐出一个结果退出所以我情不自禁，但如果你有一本名为“C++ 中的数字食谱”的书，请转到接近结尾处，你会发现你正在寻找的内容实际上是从第 916 页到第 926 页开始的。

于 2014-12-02T19:32:11.990 回答
0

这个问题已经超过 2 年了，但是对于这个大小数字，您可以查看 OpenSSL 源代码。它使用这种大小的数字执行 RSA，因此有许多针对 1000 到 4000 位数优化的数学例程。

于 2012-12-18T03:15:21.927 回答