我在考虑一种大数除法的算法:用余数bigint C除以bigint D，我们知道C在基数b中的表示形式，D的形式为b ^ k-1。这可能是最简单的示例显示。让我们尝试用C = 21979182173除以D = 999。
实际上，21979182173/999 = 22001183和其余356。
我已经计算了复杂度，并且，如果我没有记错的话，该算法应该在O(n)中工作，n是基数b表示中C的位数。我还在C++中完成了该算法的非常粗糙且未经优化的版本(仅针对b = 10)，并针对GMP的通用整数除法算法进行了测试，它的确确实比GMP表现更好。我在所看到的任何地方都找不到实现这种功能的东西，因此我不得不诉诸通用部门对其进行测试。
我发现有几篇文章讨论了看起来非常相似的问题，但是没有一篇文章专注于实际的实现，尤其是在不同于2的基础上。我想这是因为数字的内部存储方式，尽管提到的算法似乎对例如，即使考虑到这一点，b = 10。我也尝试与其他人联系，但同样无济于事。
因此，我的问题是:是否有一篇文章或一本书或其他内容描述了上述算法，可能讨论了实现方法？如果没有，那么尝试在C/C++中实现和测试这样的算法对我来说是否有意义，或者该算法天生就不好？
另外，我不是程序员，虽然我在编程方面相当不错，但是我承认我对计算机“内部”知识不多。因此，请原谅我的无知-这篇文章中很可能有一件或多件非常愚蠢的事情。再次抱歉。
非常感谢!
进一步澄清意见/答案中提出的观点:
谢谢大家，由于我不想在同一件事上评论所有出色的答案和建议，所以我想谈谈很多您涉及的问题。
我完全知道，一般而言，以2 ^ n为基数工作显然是最有效的处理方式。几乎所有的bigint库都使用2 ^ 32或其他值。但是，如果我们将bigints作为基数b中的一个数字数组实现了(我强调，这仅对这种特定算法有用)!当然，我们要求b在这里是“合理的”:b = 10(最自然的情况)似乎足够合理。我知道考虑内存和时间的内部存储方式，或多或少会降低效率，但是如果我的(基本的，可能有缺陷的)测试是正确的，我能够比GMP的一般部门更快地得出结果，实现这种算法将很有意义。
Ninefingers注意到，在这种情况下，我将不得不使用昂贵的模运算。我希望不会:仅通过查看old + new + 1的位数就可以看到old + new是否越过，例如999。如果它有4位数字，我们就完成了。更重要的是，由于old <999和new <= 999，我们知道如果old + new + 1有4位数字(不能有更多数字)，则(old + new)％999等于删除( old + new + 1)，我认为我们可以廉价地做到这一点。
当然，我既不反对该算法的明显局限性，也不主张不能改进-它只能用特定类别的数字进行除法，我们必须事先知道以b为底的股息的表示形式。但是，例如对于b = 10，后者似乎很自然。
现在，假设我们已经实现了如上所述的bignums。假设以b为底的C =(a_1a_2 ... a_n)和D = b ^ k-1。该算法(可能会进行更优化)将像这样。我希望没有很多错别字。
在那里，感谢您与我讨论这个问题-正如我所说，如果没有人看到致命的缺陷，这对我来说似乎是一种有趣的“特殊情况”算法，可以尝试实现，测试和讨论。如果到目前为止还没有广泛讨论，那就更好了。请让我知道你的想法。抱歉，帖子很长。
另外，还有一些个人评论:
@Ninefingers:实际上，我对GMP的工作原理，它的功能以及一般的bigint除法算法有一些(非常基础的)知识，因此我能够理解您的大部分观点。我还知道GMP是经过高度优化的，并且可以针对不同的平台进行自定义，因此，我当然不会在总体上“打败”它-似乎和用尖头棍攻击坦克一样富有成果。但是，这不是该算法的概念-它在非常特殊的情况下(似乎没有涵盖GMP)起作用。无关紧要的是，您确定大数除法在O(n)中完成吗？我见过最多的是M(n)。 (如果我理解正确的话，那么在实践中(Schönhage–Strassen等)可能无法达到O(n)。如果我正确的话，仍然没有达到O(n)的Fürer算法几乎是纯粹的理论上的。)
@Avi Berger:尽管这个想法很相似，但实际上似乎与“铸出九分”并不完全相同。但是，如果我没有记错的话，上述算法应该一直有效。
最佳答案
您的算法是以10为基础的算法的一种变体，称为“铸成9”。您的示例使用的是基数1000，然后“转换”出999(基数少一)。过去在小学时曾教过这种方法，可以快速检查手头的计算。我有一个高中数学老师，他震惊地得知它不再被教了，于是我们为之付出了很多。
以1000为基数淘汰999不能作为通用除法算法。它将生成与实际商和余数模999相乘的值-而不是实际值。您的算法有些不同，我尚未检查它是否有效，但是它基于有效地使用1000底数和除数比1底数小1的基础。如果要尝试将其除以47，则必须先转换为以48为基数的系统。
谷歌“播出9”以获得更多信息。
编辑:我本来阅读您的帖子的速度太快了，您确实知道这是一种有效的算法。正如@Ninefingers和@Karl Bielefeldt在他们的评论中比我更清楚地指出，您的效果估算中未包含的内容是转换为适合于当前特定除数的基数。
关于c++ - 整数除法算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/5097383/