经过几次乘法**有溢出**有可能得到一个数字的原始值吗？

Question

总结：假设我有一个unsigned int数字。然后我将其相乘几次（并且出现溢出，这是预期的）。那么是否可以“恢复”回原来的值呢？

---

详细：

这一切都是关于 Rabin-Karp 滚动哈希。我需要做的是：我有一个长字符串的哈希值 - 例如：“abcd”。然后我得到了较短子字符串的哈希值 - 例如“cd”。如何使用两个给定的哈希值以 O(1) 计算“ab”哈希值？

我现在拥有的算法：

• 从“abcd”哈希中减去“cd”哈希（从多项式中删除最后一个元素）
• 将“abcd”哈希除以

  p ^ len( "cd" )

  ，其中

  p

  是基数（素数）。

所以这是：

a * p ^ 3 + b * p ^ 2 + c * p ^ 1 + d * p ^ 0

- abcd

c * p ^ 1 + d * p ^ 0

- cd

ab 得到：

（ 
  (a * p ^ 3 + b * p ^ 2 + c * p ^ 1 + d * p ^ 0 ) -
  （c * p ^ 1 + d * p ^ 0 ） 
）
/(p^2)
= a * p ^ 1 + b * p ^ 0

如果我没有溢出（如果

p

是小数字），这是可行的。但如果不是 - 它就不起作用。

有什么技巧吗？

附注

c++

标签是因为数字溢出，因为它是特定的（并且与python、scheme或sth不同）

Answer 1

不知道溢出部分，但有一种方法可以恢复原始值。

中国剩余定理有很大帮助。我们打电话给

h = abcd - cd

。 G 是值

h

，没有溢出

G = h + k*2^32

，假设溢出只是

%2^32

。因此

ab = G / p^2

。

G = h (mod 2^32)
G = 0 (mod p^2)

如果 p^2 和 2^32 互质。这个关于中国剩余定理的页面给了我们

G = h * b * p^2 (mod 2^32 * p^2)

其中

b

是 p^2 模 2^32 的模乘逆，

b * p^2 = 1 (mod 2^32)

。计算出

G

后，只需除以

p^2

即可找到

ab

。

Answer 2

扩展欧几里得算法是一个很好的解决方案，但它过于复杂且难以实现。还有更好的。

---

还有另一种方法可以做到这一点（感谢我的朋友（:）

维基百科中有一篇不错的文章 - 模乘法逆在这种情况下使用欧拉定理，当

m

和

a

互质时：

其中

φ(m)

是 欧拉 totient 函数。

在我的例子中，

m

（模）是哈希类型的大小 -

2^32

、

2^64

等（在我的例子中为 64 位）。
嗯，这意味着，我们应该只找到

φ(m)

的值。但想一想 -

m == 2 ^ 64

所以，这给了我们保证

m

将与所有奇数互质，并且 不会与任何偶数互质。所以，我们需要做的就是得到所有值的个数，然后除以 2。

此外，我们知道

m

将是无符号的，否则我们会遇到一些问题。这让我们有机会做到这一点：

hash_t x = -1;
x /= 2;
hash_t a_reverse = fast_pow( a, x );

嗯，对于 64 位数字，

x

确实是一个很大的数字（19 位：

9 223 372 036 854 775 807

），但是

fast_pow

非常快，我们可以缓存反向数字，以防我们需要多个查询。

fast_pow

是一个众所周知的算法：

hash_t fast_pow( hash_t source, hash_t pow )
{
    if( 0 == pow )
    {
        return 1;
    }

    if( 0 != pow % 2 )
    {
        return source * fast_pow( source, pow - 1 );
    }
    else
    {
        return fast_pow( source * source, pow / 2  );    
    }

}

---

添加：例如：

    hash_t base = 2305843009213693951;  // 9th mersenne prime
    hash_t x = 1234567890987654321;

    x *= fast_pow( base, 123456789 );   // x * ( base ^ 123456789 )

    hash_t y = -1;
    y /= 2;
    hash_t base_reverse = fast_pow( base, y );

    x *= fast_pow( base_reverse, 123456789 );   // x * ( base_reverse ^ 123456789 )
    assert( x == 1234567890987654321 ) ;

工作完美且速度非常快。

Answer 3

你有一个 * b = c mod 2^32 （或者根据你如何进行哈希来修改其他东西）。如果你能找到 d 使得 b * d = 1 mod 2^32 （或 mod 其他），那么你可以计算 a * b * d = a 并检索 a.如果 gcd(b, mod 2^32) = 1 那么你可以使用 http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm 找到 x 和 y 使得 b * x + 2^32 * y = 1 ， 或者 b * x = 1 - y * 2^32，或 b * x = 1 mod 2^32，所以 x 是您要乘以的数字。

Answer 4

您应该使用无符号整数来获取定义的溢出行为（模 2^N）。有符号整数溢出未定义。

此外，您应该乘以 p 的乘法逆元模适当的值，而不是除法。例如，如果 p=3 并且您的哈希值是 8 位，则乘以 171，因为 171*3=513=2*256+1。如果 p 和模值互质，则存在乘法逆元。

Answer 5

这里只是部分侧面回答：我相信使用无符号整数是不是严格必要的。您可以使用补语。

但请注意，这将有 -0 和 +0 的单独表示，并且您可能必须在此过程中手动编写算术运算。

某些处理器指令与整数表示无关，但并非全部。

Answer 6

所以溢出其实只是你的编译器对你好而已； C/++ 标准实际上表明溢出是未定义的行为。因此，一旦溢出，实际上您无能为力，因为您的程序不再是确定性的。

您可能需要重新考虑算法，或者添加模运算/减法来修复您的算法。