java - 为什么 java 的 BigInteger gcd 和 modInverse 这么慢？

Question

我正在尝试使用 java.math.BigInteger对于一些精确的整数矩阵计算，其中标量值达到数百万位。我注意到一些内置的 BigInteger 操作出乎意料地非常慢——特别是 gcd 的一些情况，以及 modInverse 的更多情况。看来我可以实现这些函数的自己的版本，速度要快得多。

我写了一个程序来打印计算时间gcd(10^n-3, 10^n) 用于将 n 的值增加到一百万左右，使用内置 gcd 或我自己的简单替代实现:

private static java.math.BigInteger myGcd(java.math.BigInteger a, java.math.BigInteger b)
{
    a = a.abs();
    b = b.abs();
    while (true)
    {
        if (b.signum() == 0) return a;
        a = a.mod(b);
        if (a.signum() == 0) return b;
        b = b.mod(a);
    }
} // myGcd

我在 ubuntu linux 下使用 java 8 运行它，运行时版本 1.8.0_111-8u111-b14-2ubuntu0.16.04.2-b14。在具有 java 运行时 1.8.0_92 的 macbook 上，时间大致相似。

内置 gcd 大致是二次方的:

# numDigits seconds
1 0.000005626
2 0.000008172
4 0.000002852
8 0.000003097
16 0.000019158
32 0.000026365
64 0.000058330
128 0.000488692
256 0.000148674
512 0.007579581
1024 0.001199623
2048 0.001296036
4096 0.021341193
8192 0.024193484
16384 0.093183709
32768 0.233919912
65536 1.165671857
131072 4.169629967
262144 16.280159394
524288 67.685927438
1048576 259.500887989

我的大致是线性的(对于所描述的情况；是的，我知道在最坏的情况下它必须是二次的):

# numDigits seconds
1 0.000002845
2 0.000002667
4 0.000001644
8 0.000001743
16 0.000032751
32 0.000008616
64 0.000014859
128 0.000009440
256 0.000011083
512 0.000014031
1024 0.000021142
2048 0.000036936
4096 0.000071258
8192 0.000145553
16384 0.000243337
32768 0.000475620
65536 0.000956935
131072 0.002290251
262144 0.003492482
524288 0.009635206
1048576 0.022034768

请注意，对于描述的一百万位数字，内置 gcd 需要超过 10000是我的两倍:259 秒对 .0220 秒。

内置的 gcd 函数是否在执行除欧几里德算法之外的其他操作？为什么？

我得到的内置 modInverse 与我自己的实现的时间相似使用扩展欧几里德算法(此处未显示)。与内置 gcd 相比，内置 modInverse 在更多情况下表现不佳，例如当 a 是一个小数，例如 2,3,4,... 而 b 很大时。

下面是上述数据的三个图(两个不同的线性比例，然后是对数比例):

程序 list 如下:

/*
  Benchmark builtin java.math.BigInteger.gcd vs. a simple alternative implementation.
  To run:
    javac BigIntegerBenchmarkGcd.java
    java BigIntegerBenchmarkGcd mine > OUT.gcd.mine
    java BigIntegerBenchmarkGcd theirs > OUT.gcd.theirs

    gnuplot
      set title "Timing gcd(a=10^n-3, b=10^n)"
      set ylabel "Seconds"
      set xlabel "Number of digits"
      unset log
      set yrange [0:.5]
      #set terminal png size 512,384 enhanced font "Helvetica,10"
      #set output 'OUT0.gcd.png'
      plot [1:2**20] "OUT.gcd.theirs" with linespoints title "a.gcd(b)", "OUT.gcd.mine" with linespoints title "myGcd(a,b)"
      #set output 'OUT1.gcd.png'
      unset yrange; replot
      #set output 'OUT2.gcd.png'
      set log; replot
*/
class BigIntegerBenchmarkGcd
{
    // Simple alternative implementation of gcd.
    // More than 10000 times faster than the builtin gcd for a=10^1000000-3, b=10^1000000.
    private static java.math.BigInteger myGcd(java.math.BigInteger a, java.math.BigInteger b)
    {
        a = a.abs();
        b = b.abs();
        while (true)
        {
            if (b.signum() == 0) return a;
            a = a.mod(b);
            if (a.signum() == 0) return b;
            b = b.mod(a);
        }
    } // myGcd

    // Make sure myGcd(a,b) gives the same answer as a.gcd(b) for small values.
    private static void myGcdConfidenceTest()
    {
        System.err.print("Running confidence test... ");
        System.err.flush();
        for (int i = -10; i < 10; ++i)
        for (int j = -10; j < 10; ++j)
        {
            java.math.BigInteger a = java.math.BigInteger.valueOf(i);
            java.math.BigInteger b = java.math.BigInteger.valueOf(j);
            java.math.BigInteger theirAnswer = a.gcd(b);
            java.math.BigInteger myAnswer = myGcd(a, b);
            if (!myAnswer.equals(theirAnswer)) {
                throw new AssertionError("they say gcd("+a+","+b+") is "+theirAnswer+", I say it's "+myAnswer);
            }
        }
        System.err.println("passed.");
    }

    public static void main(String args[])
    {
        boolean useMine = false;
        if (args.length==1 && args[0].equals("theirs"))
            useMine = false;
        else if (args.length==1 && args[0].equals("mine"))
            useMine = true;
        else
        {
            System.err.println("Usage: BigIntegerBenchmarkGcd theirs|mine");
            System.exit(1);
        }

        myGcdConfidenceTest();

        System.out.println("# numDigits seconds");
        for (int numDigits = 1; numDigits <= (1<<20); numDigits *= 2)
        {
            java.math.BigInteger b = java.math.BigInteger.TEN.pow(numDigits);
            java.math.BigInteger a = b.subtract(java.math.BigInteger.valueOf(3));

            System.out.print(numDigits+" ");
            System.out.flush();

            long t0nanos = System.nanoTime();
            java.math.BigInteger aInverse = useMine ? myGcd(a, b)
                                                    : a.gcd(b);
            long t1nanos = System.nanoTime();

            double seconds = (t1nanos-t0nanos)/1e9;
            System.out.println(String.format("%.9f", seconds));
        }
    } // main
} // class BigIntegerBenchmarkGcd

Answer 1

对于位长相差不超过 1 的 BigInteger a 和 b，a.gcd(b) 使用 binary GCD algorithm，它执行 O(n) 次减法和移位(其中 n 是整数的位长度)。它的运行时间弱依赖于输入整数是什么，例如，它们彼此之间有多接近。在您的情况下，b - a = 3，并且在您实现欧几里德算法 b = b.mod(a) 的第一次迭代中已经是 3。因此算法的步数不t 取决于整数的长度，并立即退出。

顺便说一句，10^n 总是与 10^n - 3 互质。