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

Question

这几天我一直在研究这个问题，一直没能找到答案。我已经想出了一个算法，如果除数只有一个词的话。但是，如果除数是多个词，我会得到一些奇怪的答案。我知道这个问题在这里已经问过几次了，但是除了用教科书的方法或者去拿一本关于这个问题的书之外，没有一个明确的答案。我已经可以让我的大整数库中的每个函数工作，除了除法。似乎有些人认为大整数除法是一个NP难问题，而且我有这个问题的麻烦，我倾向于同意。
数据存储在一个结构中，该结构包含指向uint16或uint32数组的指针，这取决于是否支持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 */
  };

这与我问的另一个关于 inline assembler的问题有关，因为这就是它的用途。
到目前为止我所发现的：
Algorithm for dividing very large numbers
What is the fastest algorithm for division of crazy large integers?
https://en.wikipedia.org/wiki/Division_algorithm
Newton-Raphson Division With Big Integers
还有一堆关于这个问题的学术论文。
到目前为止我所做的：
我有一个基本的程序，但它把一个多字大整数除以一个字我试图实现牛顿-拉斐逊算法，但这不起作用，因为我得到了一些非常奇怪的结果。我从微积分学知道牛顿的方法，但这是整数数学，不是浮点。我理解Goldschmidt除法算法背后的数学原理，但我不清楚如何用整数数学实现它其中一些算法的部分问题在于它们需要一个基数为2的对数函数。我知道如何使用浮点和泰勒级数实现对数函数，但不知道如何使用整数数学。
我试过查看 GMP库，但是除法算法没有很好的文档记录，这有点超出我的想象似乎他们在不同的地方使用不同的算法，这增加了混乱。
对于学术论文，我主要理解数学（我已经清除了基本微积分数学、多变量微积分和常微分方程），但再一次，我的数学知识与使用整数数学实现之间存在脱节。我看到有人建议用小学的方法，从我能确定的情况来看，这种方法类似于移位减法，但我也不太确定如何实现这种方法。有什么想法吗？代码会很好。
编辑：
这是为了我个人的学习经验。我想知道是怎么做的。
编辑：2016年6月4日
我已经有一段时间没有在这方面工作了，因为我有其他的铁在火和其他项目的工作。现在，我已经重温了这个项目，我终于实现了大整数除法使用两种不同的算法。最基本的是移位减法。使用CPU除法指令的高速算法只在除数为一个字时调用这两种算法都被证实工作正常，因为它们产生的结果已经用 here进行了检查。现在，所有的基本数学和逻辑函数都已经实现了。这些函数包括加法、减法、乘法、除法、用模数除法、模数除法和，或不除法、异或、求反、反转（反射）、向左移位、向右移位、向左旋转和向右旋转我可以根据需要添加其他功能。谢谢所有回复的人。

Answer 1

C并没有为这类部门提供任何特殊服务。
如果你想解决这个问题，你需要自己实现这个解决方案。
我在Stack Overflow上发现一些链接，可以帮助您选择适合您需要的解决方案：
What is the fastest algorithm for division of crazy large integers?
或
Division of Large numbers