不使用 Math.BigInteger 的高幂模数

Question

我要把这个公式变成java代码：

$h(s)= \left (1+ \sum_{i=0}^{s.length()-1)} s.charAt(i) \cdot 256^i \right ) mod (n)$

如果我可以使用 Math.BigInteger 之类的库，那会容易得多，但不幸的是，没有它我应该这样做。 Whosebug 上的一些类似问题建议编写一个自己的 bignum 库，但我想在没有它的情况下进行。

现在，我的进度是在这一步：

int h(String s) {
  long value = 1;
  int mod = ht.length;

  for (int i=0; i < s.length()-1; i++) {
     h += s.charAt(i) * Math.pow(256,i);
  }
  return (int) h % mod;
}

我知道幂的值很快就会超出整数范围，所以我考虑编写一个自己的方法来计算该值的幂和模。我的数学知识还不够好，不知道何时使用模数以及如何简化事情。

提前致谢！

Answer 1

基本上，您应该将 modulo 移到等式的更深处，以在每一步都保持较低的值。为此，您基本上可以使用 module 规则：

(a + b) % n = (a % n + b % n) % n
(a * b) % n = (a % n * b % n) % n

首先将其移入循环：

h = (h + s.charAt(i) * Math.pow(256, i)) % mod;

然后也将它移到 pow 中：

h = (h + s.charAt(i) * Math.pow(256 % mod, i)) % mod;

最后，我将停止使用 pow，因此在每个步骤后 mod 进行一些自定义供电，例如
((((256 % mod) * 256 % mod) * 256 % mod) ... )

Answer 2

我觉得你在看快modular exponentiation:

让我们考虑这个简单的公式来解释它是如何工作的：

x = A^B % C 作为 x = 5^117 % 19

1。将 B 分解为 2 的幂

117 = (2^0 + 2^2 + 2^4 + 2^5 + 2^6) 117 = (1 + 4 + 16 + 32 + 64 )

2。计算 mod C 为 2 <= B

的幂

5^2 mod 19 = (5^1 * 5^1) mod 19 = (5^1 mod 19 * 5^1 mod 19) mod 19
5^2 mod 19 = (5 * 5) mod 19 = 25 mod 19
5^2 mod 19 = 6

5^4 mod 19 = (5^2 * 5^2) mod 19 = (5^2 mod 19 * 5^2 mod 19) mod 19
5^4 mod 19 = (6 * 6) mod 19 = 36 mod 19
5^4 mod 19 = 17

5^8 mod 19 = (5^4 * 5^4) mod 19 = (5^4 mod 19 * 5^4 mod 19) mod 19
5^8 mod 19 = (17 * 17) mod 19 = 289 mod 19
5^8 mod 19 = 4

5^16 mod 19 = (5^8 * 5^8) mod 19 = (5^8 mod 19 * 5^8 mod 19) mod 19
5^16 mod 19 = (4 * 4) mod 19 = 16 mod 19
5^16 mod 19 = 16

5^32 mod 19 = (5^16 * 5^16) mod 19 = (5^16 mod 19 * 5^16 mod 19) mod 19
5^32 mod 19 = (16 * 16) mod 19 = 256 mod 19
5^32 mod 19 = 9

5^64 mod 19 = (5^32 * 5^32) mod 19 = (5^32 mod 19 * 5^32 mod 19) mod 19
5^64 mod 19 = (9 * 9) mod 19 = 81 mod 19
5^64 mod 19 = 5

3。计算 X

5^117 mod 19 = ( 5^1 * 5^4 * 5^16 * 5^32 * 5^64) mod 19
5^117 mod 19 = ( 5^1 mod 19 * 5^4 mod 19 * 5^16 mod 19 * 5^32 mod 19 * 5^64 mod 19) mod 19
5^117 mod 19 = ( 5 * 17 * 16 * 9 * 5 ) mod 19
5^117 mod 19 = 61200 mod 19 = 1
5^117 mod 19 = 1

为什么这可以解决您的问题

您的 A 或 B 可能远高于 Integer 限制。

而不是对所有值求和，然后最终应用 modulus 你可以求和到整数限制，然后应用上面的公式，然后再次开始求和，并重新应用公式，等等，因为 6 % 4 == (3 % 4) + (3 % 4) % 4

Answer 3

如果你从后面走，你根本不需要拿任何权力。在每一步简单地乘以 256 将产生相同的效果（后面的值 "accumulate" 更多乘法，将它们提高到所需的幂）。例如（未测试）

int h(String s) {
  int res = 0;
  int n = ht.length;

  for (int i = s.length() - 1; i >= 0; i--) {
     // using a long here to prevent premature wrapping
     long t = res * 256L + s.charAt(i);
     res = (int)(t % n);
  }
  return (res + 1) % n;
}

还要注意 ht.length 不应该是二的幂（所以你不能跳过循环中的模数减少，如果 ht.length was 2 的幂），因为如果它是 2 的幂，那么哈希值（最多）取决于前 4 个字符，这显然很糟糕。

Answer 4

我默认为你的 n 选择了一个大素数，问你的导师，但是使用任何非素数都不是一个好主意。如果那是散列中的桶数 table，请确保该数字是质数。另外，您不能在 for 循环的退出条件中 -1，因为您漏掉了最后一个字符。

private static int MAX_PRIME = 2147483647; //largest positive 32 signed int prime (also happens to be the largest positive 32 signed int)

public static int hash(String s) {
    return hash(s, MAX_PRIME);
}

public static int hash(String s, int primeN) {
    long h = 1;
    long m = 1;

    for (int i = 0; i < s.length(); i++) {
        h += s.charAt(i) * m;
        h %= primeN;
        m *= 256;
        m %= primeN;
    }

    return (int) h;
}

如果您想测试正确性，那么您可以将生成的哈希值与 BigInteger 实现进行比较：

public static int hashBigInt(String s) {
    return hashBigInt(s, MAX_PRIME);
}

public static int hashBigInt(String s, int primeN) {
    final BigInteger bi256 = BigInteger.valueOf(256);
    BigInteger h = BigInteger.ONE;
    BigInteger m = BigInteger.ONE;

    for (int i = 0; i < s.length(); i++) {
        h = h.add(BigInteger.valueOf(s.charAt(i)).multiply(m));
        m = m.multiply(bi256);
    }

    return h.mod(BigInteger.valueOf(primeN))
            .intValue();
}

不使用 Math.BigInteger 的高幂模数

Modulo of high powers without using Math.BigInteger

java

math

modulo

exponent

1。将 B 分解为 2 的幂

2。计算 mod C 为 2 <= B

3。计算 X

为什么这可以解决您的问题