我需要将表示为字节数组中数字的数字与非标准字节数相除。它可能是 5 个字节或 1 GB 或更多。除法应该用表示为字节数组的数字来完成，而不需要任何数字转换。
问问题
20437 次
2 回答
17
对于真正的大整数，分而治之的除法最终比教科书方法快得多。
GMP是一个最先进的大数字库。对于几乎所有事情，它都有不同算法的几种实现，每种算法都针对特定的操作数大小进行了调整。
这是 GMP 的“除法算法”文档。算法描述有点简洁，但当您想了解更多信息时，它们至少可以为您提供一些信息。
Brent 和 Zimmermann 的 Modern Computer Arithmetic是一本关于大数算术理论和实现的好书。如果您想知道已知内容，可能值得一读。
于 2013-06-26T15:33:15.353 回答
10
与小学长除法类似的标准长除法算法是Knuth 4.3.1 中描述的算法 D。Knuth 在他书中的那一部分对除法进行了广泛的讨论。这样做的结果是，有比算法 D 更快的方法，但它们并没有快很多，而且比算法 D 复杂得多。
如果您确定要获得尽可能快的算法，则可以求助于所谓的 SRT 算法。
Wikipedia Division Algorithm中的方式涵盖了所有这些以及更多内容。
于 2013-06-26T14:12:24.803 回答