使用基数为 2^64 的大整数数组进行递归除法

Question

我需要能够除两个大整数 A 和 B 并得到结果商 Q 和余数 R。我发现了很多关于“就像在小学一样做除法”的帖子，但不知道这如何适用于这个情况，基数为 2^64。

例如，假设我有一个由 a_2 = 120、a_1 = 2 和 a_0 = 240 组成的数字 A，其中 a_2 对应于 2^(64*2)、a_1 对应于 2^(64*1) 等。想要将其除以 B，其中 b_1 = 1300 且 b_0 等于 3。

我该怎么做？

谢谢

Answer 1

Java BigInteger 类有一个divideAndRemainder(BigInteger val) 方法，该方法以数组形式返回(Q,R)。

示例：

BigInteger a=new BigInteger("2").pow("128").multiply("120").add(new BigInteger("2").pow("64").multiply("2")).add(new BigInteger("240"));
BigInteger b=new BigInteger("2").pow("64").multiply("1300").add(new BigInteger("3"));
BigInteger[] qr=a.divideAndRemainder(b);

虽然这并不是您所要求的，不是吗？

我没有按照你的要求做，但我看过其他解决方案。无论您是否使用大数字，数学本质上都是相同的，因此为了学习该技术，我建议您使用较小的机器字长进行学习，然后将知识应用到 64 位版本。这将使建模和验证变得更容易。

如果我（现在）明白你在问什么，你可以拥有一个 4 位数字（十六进制）序列和一个可以执行 mod、div、add、乘操作的 8 位处理器。如何将其分成块来解决任意宽度的数字除法？

例如，您可以验证十进制数 1441/3=480r1。在您的 8 位机器中，您需要 (Q,R) 作为方程 ( 0x05a1 / 0x3 )。您可以从左到右计算，取余数并将其应用于下一个数字的高位半字节。因此，您计算 0x5/0x3=1r2，然后 0x2a/0x3=er0，然后 0x01/0x3=0r1。结果中的序列“1e0”与您的预期值 (0x1e0=480) 匹配，最后的余数与您预期的 1 匹配。

外推到 64 位，您将使用相同的技术，但以 32 位块进行处理，这样您就可以将先前的余数放在字的高位半部分中。