大数的分区

我需要一些可以处理大整数（128位）的除法算法。我已经问过如何通过位移操作符来完成它。不过，我目前的实现似乎要求一个更好的办法大数的分区

基本上，我店数为两个long 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

改造它。然而，这是越野车。

（注意，地板是A/24并且mod是A % 24，正常分裂被存储在long double，整数被存储在long long unsigned int。

由于24等于二进制11000，所述第二被加数不应该在第四个加数的范围内改变一些东西，因为它向左移动64位

因此，如果A * 2^64 + B可以被24整除，而B不是，那么它很容易发现它的错误，因为它返回一些非整数号码

我的实现中有什么错误？

来源

2009-11-27 Etan

位移法的问题是什么？ – 2009-11-27 13:15:54

当你已经能够划分int64的 – Etan 2009-11-27 15:12:37

我能想到的最简单的方法是将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-27 13:12:09 interjay

它不会阻止你的算法工作，但F，G和H每个都可以大于2^32。我很难与E_F_G_H表示看起来像串联这一事实相一致，但一旦理解了这一点，这是一个非常好的算法。 – 2009-11-27 13:36:16

实际上，F，G和H将小于2^32，因为Q，R和S都小于24.所以E_F_G_H表示法*是串联的。 – interjay 2009-11-27 13:51:14

对！我忘记了我的铅笔和纸张部门...我记得有一个不愉快的猜测部分，但那是除数的数字太多。只要除数本身足够短以至落入原始分割工作的范围内（这里就是这种情况），在应用铅笔和纸张分割算法时从不需要猜测。对困惑感到抱歉。 – 2009-11-27 14:34:37

你不应该使用long double作为你的“正常部门”，而是那里的整数。 long double没有足够的有效数字来得到答案（无论如何，整个问题的关键是用整数运算来做到这一点，对吗？）。

来源

2009-11-27 12:31:39

时，它似乎是过度杀伤性的，它的全部点是将128位int除以24，这导致史诗般的失败。长双有64位的尾数，所以这不应该成为一个问题。还是呢？ – Etan 2009-11-27 12:36:57

Etan应该链接到eir原始问题。看来，目标不是用整数来完成，而是要做到这一点。此外，“long double”可以小到64位双倍，但也可以更大（例如10个字节的扩展双倍，但是任何东西，实际上...... IEEE 754主要是参考比特大小）。因此它*可能*可能具有必要的精度（我并不是说使用浮点运算来完成像128位整数运算那样简单的操作是个好主意）。 – 2009-11-27 12:39:17

如何分割而不用长双？ – Etan 2009-11-27 12:40:05

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

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

Y * 2^64不干扰较低权重二进制数字的属性仅在Y是整数时起作用。

来源

2009-11-27 12:32:32

它会干扰小数，因为您无法将它们准确地写在那里。在二进制中，它有一个有限的实现，因为1/24可以写入数字的结尾。 – Etan 2009-11-27 12:39:01

@Etan真的吗？需要多少位数字才能用二进制表示1/24呢？（如果这个问题太难了，以二进制数字的个数开始，它代表1/3） – 2009-11-27 12:47:48

1/24 =二进制0.00001010101010101 ...序列永远持续。 – dave4420 2009-11-27 12:51:16

不要。

去抓一个图书馆来做这个东西 - 你会非常感谢你选择调试奇怪的错误。

片段。org前段时间在它的网站上有一个C/C++ BigInt库，Google也发布了以下内容：http://mattmccutchen.net/bigint/

来源

2009-11-27 12:49:04

我必须手动完成它，因为它是针对ACM ICPC问题的。 – Etan 2009-11-27 12:50:26

这可能用反乘法来解决吗？要注意的第一件事是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位数字。

希望这会有所帮助。

/A.B。

来源

2009-11-27 13:45:46

回答

相关问题