Próbuję użyć java.math.BigInteger dla niektórych dokładnych obliczeń macierzy całkowitych, w których wartości skalaryczne uzyskują do milionów cyfr. Zauważyłem, że niektóre z wbudowanych operacji BigInteger są nieoczekiwanie bardzo powolne - w szczególności niektóre przypadki gcd i wiele innych przypadków modInverse. Wydaje się, że mogę wdrożyć własne wersje tych funkcji, które są znacznie szybsze.dlaczego java's BigInteger gcd i modInverse są takie wolne?
Napisałem program, który drukuje czasy obliczania GCD (10^n-3, 10^n) w przypadku zwiększenia wartości n do miliona lub więcej, używając albo wbudowanego GCD lub własną prostą alternatywną implementację :
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
Pobiegłem go przy użyciu Java 8 pod ubuntu Linux, wersji Runtime 1.8.0_111-8u111-b14-2ubuntu0.16.04.2-b14. Czasy są mniej więcej podobne, na MacBoorze z językiem wykonawczym java 1.8.0_92.
Builtin GCD jest w przybliżeniu kwadratowa:
# 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
Kopalnia jest w przybliżeniu liniowa (dla przypadku opisanego, tak, wiem, że to musi być kwadratowa w najgorszym przypadku):
# 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
Zawiadomienie że dla miliona cyfr opisanego przypadku wbudowane gcd zajmuje więcej niż 10000 razy tak długo, jak moje: 259 sekund vs. 0,220 sekund.
Czy wbudowana funkcja gcd działa inaczej niż algorytm euklidesowy? Czemu?
Dostaję podobne czasy dla wbudowanego modInverse vs. moja własna implementacja używając rozszerzonego algorytmu euklidesowego (nie pokazano tutaj). Wbudowany modInverse robi źle w jeszcze większej liczbie przypadków niż wbudowany gcd, np. kiedy a jest małą liczbą jak 2,3,4, ... a b jest duże.
Oto trzy działki z powyższych danych (dwie różne skale liniowe a następnie skala logarytmiczna):
Oto listing programu:
/*
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
kod źródłowy Java dla BigInteger jest dostępna dla Lektura i analiza. –
[Implementacja OpenJDK] (http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/8u40-b25/java/math/BigInteger.java # BigInteger.gcd% 28java.math.BigInteger% 29), nawiasem mówiąc. – chrylis
Jeśli masz lepszą implementację, prześlij ją, aby mogła ją użyć następna wersja Java, zakładając, że jest równa dla wszystkich przypadków użycia. – Andreas