5

我需要一些可以处理大整数（128 位）的除法算法。我已经问过如何通过位移运算符来做到这一点。但是，我目前的实现似乎要求更好的方法

基本上，我将数字存储为 2long long unsigned int的格式

A * 2 ^ 64 + B与B < 2 ^ 64.

这个数字可以被 整除24，我想把它除以24。

我目前的方法是将其转换为

A * 2 ^ 64 + B     A             B
--------------  = ---- * 2^64 + ----
      24           24            24

           A               A mod 24                    B         B mod 24
= floor( ---- ) * 2^64 +  ---------- * 2^64 + floor( ---- ) +   ----------
           24               24.0                      24           24.0

但是，这是错误的。

（请注意， floor 是A / 24并且mod是A % 24。正常除法存储在 中long double，整数存储在long long unsigned int.

由于24等于11000二进制，第二个加数不应该改变第四个加数范围内的任何东西，因为它向左移动了 64 位。

因此，如果A * 2 ^ 64 + B可以被 24 整除，而 B 不能，则很容易表明它存在错误，因为它返回了一些非整数。

我的实施中有什么错误？

4

5 回答 5

13

我能想到的最简单的方法是将 128 位数字视为四个 32 位数字：

A_B_C_D = A*2^96 + B*2^64 + C*2^32 + D

然后用 24 做长除法：

E = A/24 (with remainder Q)
F = Q_B/24 (with remainder R)
G = R_C/24 (with remainder S)
H = S_D/24 (with remainder T)

哪里的X_Y意思X*2^32 + Y。那么答案是E_F_G_H余数T。在任何时候，您只需要对 64 位数字进行除法，因此这应该仅适用于整数运算。

于 2009-11-27T13:12:09.273 回答
2

这可以用逆乘法解决吗？首先要注意的是，24 == 8 * 3所以结果

a / 24 == (a >> 3) / 3

那么除法x = (a >> 3)的结果是8 * (x / 3)。现在剩下的就是找到 的值了x / 3。

模算术表明存在一个数n，使得n * 3 == 1 (mod 2^128). 这给出了：

x / 3 = (x * n) / (n * 3) = x * n

剩下的就是找到常数n。在wikipedia上有一个关于如何做到这一点的解释。您还必须实现乘以 128 位数字的功能。

希望这可以帮助。

/AB

于 2009-11-27T13:45:46.290 回答
1

你不应该使用long double你的“正常除法”，但也应该使用整数。long double没有足够的有效数字来得到正确的答案（无论如何，重点是用整数运算来做到这一点，对吗？）。

于 2009-11-27T12:31:39.130 回答
1

由于 24 在二进制中等于 11000，因此第二个加数不应改变第四个加数范围内的任何内容，因为它向左移动了 64 位。

你的公式是用实数写的。(A mod 24) / 24 可以有任意小数位数（例如 1/24 是 0.041666666...），因此会干扰分解中的第四项，即使乘以 2^64 也是如此。

Y*2^64 不会干扰加法中较低权重的二进制数字的属性仅在 Y 是整数时才有效。

于 2009-11-27T12:32:32.867 回答
1

不。

去拿一个库来做这些事情——你会非常感谢你在调试奇怪的错误时选择的。

Snippets.org 不久前在其网站上有一个 C/C++ BigInt 库，谷歌也出现了以下内容：http: //mattmccutchen.net/bigint/

于 2009-11-27T12:49:04.640 回答