非常大数的模数

Question

用户将使用标准输入法输入 2 个整数 x 和 y。您需要计算 x 模 y (x % y) 的余数。

现在，问题来了：

0 <= x <= 10^100000，（这是 "less than or equal" 不是箭头）。 0 < y <= 100000

我们正在寻找最佳解决方案（时间复杂度）。

我在Whosebug上没有找到答案，所以在找到解决方案后我想我应该把这个问题在这里提出以供将来参考，看看是否有更好的方法。

Answer 1

BigInteger has the divideAndRemainder(...) 方法，returns 一个 BigInteger 数组，第一项是除法结果，第二项是余数（这是 mod 在 Java).

更新

包括 Mark Dickinson 对其他答案的评论：

There's a much simpler linear-time algorithm: set acc to 0, then for each digit d in x in turn (left to right), convert d to an integer and set acc = (acc * 10 + d) % y. Once the digits are consumed, acc is your result.

按照描述实现了所有 3 种算法：

private static int testMarkDickinson(String x, int y) {
    int acc = 0;
    for (int i = 0; i < x.length(); i++)
        acc = (acc * 10 + x.charAt(i) - '0') % y;
    return acc;
}

private static int testHovercraftFullOfEels(String x, int y) {
    return new BigInteger(x).divideAndRemainder(BigInteger.valueOf(y))[1].intValue();
}

private static int testMrM(String x, int y) {
    String s = x;
    while (s.length() >= 7) {
        int len = Math.min(9, s.length());
        s = Integer.parseInt(s.substring(0, len)) % y + s.substring(len);
    }
    return Integer.parseInt(s) % y;
}

使用种子随机数进行可验证测试（不想硬编码 98765 数字）：

public static void main(String[] args) {
    Random r = new Random(98765);
    char[] buf = new char[98765];
    for (int i = 0; i < buf.length; i++)
        buf[i] = (char)('0' + r.nextInt(10));

    String x = new String(buf);
    int y = 98765;

    System.out.println(testMarkDickinson(x, y));
    System.out.println(testHovercraftFullOfEels(x, y));
    System.out.println(testMrM(x, y));

    long test1nano = 0, test2nano = 0, test3nano = 0;
    for (int i = 0; i < 10; i++) {
        long nano1 = System.nanoTime();
        testMarkDickinson(x, y);
        long nano2 = System.nanoTime();
        testHovercraftFullOfEels(x, y);
        long nano3 = System.nanoTime();
        testMrM(x, y);
        long nano4 = System.nanoTime();
        test1nano += nano2 - nano1;
        test2nano += nano3 - nano2;
        test3nano += nano4 - nano3;
    }
    System.out.printf("%11d%n%11d%n%11d%n", test1nano, test2nano, test3nano);
}

输出：

3 个结果相同，但性能有明显差异，M 先生的 "better solution" 是其中最差的。

Answer 2

比BigInteger更好的解决方案如下：

1- 将 x 作为字符串读取，将 y 作为整数读取。

2- 把x左边的前9个字符截下来，转换成整数i。

3- 计算 i % y 并将其附加到 x 的开头。

4- 从 2 开始重复，直到 x 字符串小于 7（int 的最大长度 - divider 的最大长度）。

5- 将 s 与 x 的剩余部分连接起来并计算模数。

此解决方案不受任何整数长度的限制。

非常大数的模数

Modulus of a very large number

java

algorithm

optimization

numeric