Neden java'nın BigInteger gcd ve modInverse çok yavaş?

Question

Skaler değerlerin milyonlarca haneye ulaştığı kesin tamsayı matris hesaplamaları için java.math.BigInteger 'u kullanıyorum. Bazı yerleşik BigInteger işlemlerinin beklenmedik şekilde çok yavaş olduğunu fark ettim - özellikle bazı gcd durumları ve daha pek çok modInverse durumu. . Bu işlevlerin kendi sürümlerini çok daha hızlı uygulayabiliyorum.

Ben yerleşik gcd ya da kendi basit bir alternatif uygulama kullanarak, bu yüzden bir milyona ya n up değerlerini artırmak için gcd (10^n-3, 10^n) hesaplanması için zamanlamaları yazdıran bir program yazdım :

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 

ben ubuntu linux, çalışma zamanı sürümü 1.8.0_111-8u111-b14-2ubuntu0.16.04.2-b14 altında java 8 kullanarak koştu. Zamanlamaları, nispeten, java runtime 1.8.0_92 ile bir macbook üzerinde, kabaca benzer.

Builtin gcd kabaca kuadratik geçerli:

# 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 

Mine kabaca doğrusal (anlatılan durum için; evet, ben en kötü durumda kuadratik olmak zorunda biliyorum):

# 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 

Bildirimi Açıklanan durumun bir milyon rakamı için, yerleşik gcd, benimki kadar 10000 katından daha fazla zaman alır: 259 saniye - .0220 saniye.

Yerleşik gcd işlevi, öklid algoritmasından başka bir şey mi yapıyor? Niye ya?

Uzun süreli öklid algoritmasını (burada gösterilmiyor) kullanarak, yerleşik modInverse ve kendi uyguladığım için benzer zamanlamalar alıyorum. Yerleşik modInverse, yerleşik gcd, örn. a 2,3,4 gibi küçük bir sayı olduğunda ... ve b büyüktür.

İşte yukarıdaki üç veri planları yer alıyor (iki farklı doğrusal ölçekler ve ardından günlük ölçek):

/* 
    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

BigInteger için:

İşte

programı girişidir Bit uzunlukları 1'den fazla farklı olmayan a ve b, a.gcd(b) kullanır binary GCD algorithm, O (n) çıkarmaları ve vardiyalarını (burada n tamsayıların bit uzunluğudur) yapar. Çalışma zamanı, giriş tam sayılarının ne olduğu konusunda zayıf bir şekilde bağlıdır, örneğin, birbirlerine ne kadar yakın oldukları. Sizin durumunuzda, b - a = 3 ve Euclid algoritmasının uygulamanızın ilk yinelemesinde zaten b = b.mod(a) 3'tür. Bu nedenle, algoritmanın adım sayısı tam sayıların uzunluklarına bağlı değildir ve hemen çıkar. BigInteger 3.