分数大

Question

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

基本上，我将数字存储为格式为

的两个long long unsigned int 带A * 2 ^ 64 + B的

B < 2 ^ 64。

这个数字可以被24整除，我想把它除以A / 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

然而，这是错误的。

（注意楼层是mod且A % 24是long double。正常分区存储在11000中，整数存储在<=>中。

由于<=>等于二进制的<=>，第二个加数不应该在第四个加数范围内改变，因为它向左移动了64位。

因此，如果<=>可以被24整除，而B不可以，则很容易显示它是错误的，因为它会返回一些非整数。

我的实施中出现了什么错误？

Answer 1

我能想到的最简单的方法是将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位数字，所以这应该仅适用于整数运算。

Answer 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

仍然需要找到常量<=>。有关如何在维基百科上执行此操作的说明。您还必须实现乘以128位数的功能。

希望这有帮助。

/A.B。

Answer 3

您不应该将long double用于<！>“正常部门<！>”;但也有整数。 <=>没有足够的有效数字来得到正确的答案（无论如何，整个操作是完整的操作，对吗？）。

Answer 4

  

由于二进制24等于11000，所以第二个加数不应该在第四个加数范围内改变，因为它向左移64位。

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

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

Answer 5

别。

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

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