一个大整数如何除以另一个大整数？

Question

最近几天我一直在研究这个，但我一直无法找到答案。我想出了一种算法，如果除数只有一个词，它就可以工作。但是，如果除数是多个词，那么我会得到一些奇怪的答案。我知道这个问题在这里已经被问过几次了，但是除了使用教科书方法或去买一本关于这个主题的书外，没有明确的答案。除了除法之外，我已经能够让我的大整数库中的每个函数都可以工作。似乎有些人认为大整数除法是一个 NP 难题，并且由于我遇到的麻烦，我倾向于同意。

数据存储在一个结构中，该结构包含指向 uint16_t 或 uint32_t 数组的指针，具体取决于是否支持 long long 数据类型。如果不支持 long long，则 uint16_t 用于捕获乘法和加法运算中的任何进位/溢出。我目前拥有的函数是加法、减法、乘法、2 的补码否定、比较、和、或、异或、非、左移、右移、左旋转、右旋转、位反转（反射）、一些转换例程，随机数填充例程和其他一些实用例程。除除法外，所有这些都正常工作（我在计算器上检查了结果）。

typedef struct bn_data_t bn_t;
struct bn_data_t
  {
    uint32 sz1;         /* Bit Size */
    uint32 sz8;         /* Byte Size */
    uint32 szw;         /* Word Count */
    bnint *dat;         /* Data Array */
    uint32 flags;       /* Operational Flags */
  };

这与我询问的关于内联汇编器的另一个问题有关，因为这就是它的用途。

到目前为止我发现了什么：

除法非常大的数字

疯狂大整数除法的最快算法是什么？

https://en.wikipedia.org/wiki/Division_algorithm

具有大整数的 Newton-Raphson 除法

还有一堆关于这个主题的学术论文。

到目前为止我尝试过的：

我有一个基本的例程工作，但它将多字大整数除以单个字。我曾尝试实现 Newton-Raphson 算法，但这不起作用，因为我得到了一些非常奇怪的结果。我从它所基于的微积分中知道牛顿的方法，但这是整数数学而不是浮点数。我了解 Goldschmidt 除法算法背后的数学原理，但我不清楚如何用整数数学来实现它。其中一些算法的部分问题在于它们需要以 2 为底的对数函数。我知道如何使用浮点数和泰勒级数实现对数函数，但在使用整数数学时不知道。

我曾尝试查看GMP库，但除法算法没有很好的文档记录，而且有点超出我的想象。似乎他们在不同的点使用不同的算法，这增加了混乱。

对于学术论文，我主要了解数学（我已经清除了基本微积分数学，多变量微积分和常微分方程），但再次，我的数学知识和使用整数数学实现之间存在脱节。我已经看到有人建议使用小学方法，据我所知，该方法类似于移位减法方法，但我也不太确定如何实施该方法。有任何想法吗？代码会很好。

编辑：

这是我个人的学习经验。我想了解它是如何完成的。

编辑：2016 年 6 月 4 日

我已经有一段时间没有从事这项工作了，因为我还有其他熨斗和其他项目要处理。现在我重新审视了这个项目，我终于使用两种不同的算法实现了大整数除法。基本的一种是这里概述的移位减法方法。使用CPU除法指令的高速算法只有在除数为一个字时才会调用。两种算法都已被确认可以正常工作，因为它们产生的结果已经过在线大数计算器的检查. 所以现在，所有基本的数学和逻辑功能都已实现。这些函数包括加、减、乘、除、模除、模、和、或、非、异或、求反、反向（反射）、左移、右移、左旋转和右旋转。当他们需要时，我可能会添加其他功能。感谢所有回复的人。

Answer 1

教科书上的除法（长除法）算法通常用于以 10 为基数的操作数，也可用于任意大的操作数。我假设我们正在通过 base 中的数字数组来实现大数字B。

当我们手动对小数操作数执行长除法时，我们通常依靠反复试验来找到每个商位d。但是，当对基数中的大操作数使用长除法时，可以用一种有效的方法（归功于 DA Pope 和 ML Stein）来代替这种试错B。

为了猜测d，我们可以使用除数的第一位数字 ( e) 和“当前余数”的前两位数字 ( yz) （由长除法的减法步骤得出）。比如说，是通过将数字除以 得到的估计d1值。可以证明，如果除数具有某些属性（这些属性总是可以实现的，请参阅下面的链接），则或或一定是所需的数字。可以一一检查这三个候选者中的每一个是否具有所需的属性。dyzed1d1-1d1-2dd

因此，每个商位的查找变得高效，而对于其余部分，我们可以遵循迭代长除法过程。有关该算法及其在 C 语言中的实现的详细信息，请参阅以下文章（由我撰写）：

https://mathsanew.com/articles/implementing_large_integers_division.pdf