Éste artículo es una traducción al castellano de la entrada original publicada, en inglés, por Dr. Heinz Kabutz en su número 236 del JavaSpecialists newsletter. Puedes consultar el texto original en Javaspecialists’ Newsletter #236: Computational Complexity of BigInteger.multiply() in Java 8
Este artículo se publica traducido en adictos, con permiso del autor, por David Gómez García, (@dgomezg)consultor tecnológico en Autentia, colaborador de JavaSpecialists e instructor certificado para impartir los cursos de JavaSpecialists.
[/box]
Complejidad computacional de BigInteger.multiply() en Java 8
Curioseando por el código de Java de forma aleatoria, hace unos meses, encontré que BigInteger había sido mejorado. En versiones anteriores, el método multiply implementaba el mismo mecanismo que utilizaba tu profesor de matemáticas en primaria para torturarte: O(n2). En un número anterior de Javaspecialists’ Newsletter, ya comenté que el algoritmo de Karatsuba es mejor cuando tenemos números grandes, ya que proporciona O(n lg 3) o O(n 1,585). Otro algoritmo es el algoritmo de Toom-Cook (también conocido como Toom-3), que tiene O(n 1,465). Aunque ambos parecen muy similares, la diferencia es grande cuando n crece. Aquí tenemos un pequeño código que lo demuestra:
public class BigOComparison {
public static void main(String... args) {
for (int n = 1; n <= 1_000_000_000; n *= 10) {
double n_2 = Math.pow(n, 2);
double n_1_585 = Math.pow(n, 1.585);
double n_1_465 = Math.pow(n, 1.465);
double karatsuba_faster_than_quadratic = n_2 / n_1_585;
double toom_cook_faster_than_karatsuba = n_1_585 / n_1_465;
System.out.printf("%d\t%.2fx\t%.2fx%n",
n, karatsuba_faster_than_quadratic,
toom_cook_faster_than_karatsuba);
}
}
}
Podemos comprobar que, a medida que n incrementa su valor, la diferencia en la complejidad computacional se hace más evidente. Con n = 1_000_000_000, n1,585 resulta 5.000 veces más rápido que n2. Pero n1,465 todavía es 12 veces más rápido:
1 1.00x 1.00x 10 2.60x 1.32x 100 6.76x 1.74x 1000 17.58x 2.29x 10000 45.71x 3.02x 100000 118.85x 3.98x 1000000 309.03x 5.25x 10000000 803.53x 6.92x 100000000 2089.30x 9.12x 1000000000 5432.50x 12.02x
Naturalmente, hay costes de inicialización que no se tienen en cuenta en la notación de Landau (O grande). Por este motivo, sólo deberíamos utilizar Karatsuba para cifras grandes, y Toom Cook para cifras aún mayores.
Java 8 incluye ambos algoritmos en la implementación de BigInteger. Para comprobar la mejora en el rendimiento, aquí vemos el cálculo de Fibonacci con el Algoritmo de la suma de los cuadrados de Dijkstra:
public class Fibonacci {
public BigInteger f(int n) {
if (n == 0) return BigInteger.ZERO;
if (n == 1) return BigInteger.ONE;
if (n % 2 == 1) { // F(2n-1) = F(n-1)^2 + F(n)^2
n = (n + 1) / 2;
BigInteger fn_1 = f(n - 1);
BigInteger fn = f(n);
return fn_1.multiply(fn_1).add(fn.multiply(fn));
} else { // F(2n) = ( 2 F(n-1) + F(n) ) F(n)
n = n / 2;
BigInteger fn_1 = f(n - 1);
BigInteger fn = f(n);
return fn_1.shiftLeft(1).add(fn).multiply(fn);
}
}
public BigInteger f_slow(int n) {
if (n == 0) return BigInteger.ZERO;
if (n == 1) return BigInteger.ONE;
return f_slow(n - 1).add(f_slow(n - 2));
}
}
El método f_slow() está preparado para permitirnos probar nuestro algoritmo rápido, pero no será útil por encima de n=30.
Aquí tenemos una clase de test que podemos ejecutar con Java 7 y con Java 8 para comprobar cómo la reducción de la complejidad computacional en el algoritmo de multiply() acelera la ejecución en Java 8.
public class FibonacciTest {
public static void main(String... args) {
Fibonacci fib = new Fibonacci();
for (int i = 0; i < 10; i++) {
if (!fib.f(i).equals(fib.f_slow(i))) {
throw new AssertionError("Mismatch at i=" + i);
}
}
for (int n = 10000; n < 50_000_000; n *= 2) {
timeTest(fib, n);
}
}
private static void timeTest(Fibonacci fib, int n) {
System.out.printf("fib(%,d)%n", n);
long time = System.currentTimeMillis();
System.out.println(fib.f(n).bitLength());
time = System.currentTimeMillis() - time;
System.out.println("time = " + time);
}
}
Y aquí tenemos la salida de su ejecución con Java 7:
heinz$ java -showversion FibonacciTest java version "1.7.0_80" Java(TM) SE Runtime Environment (build 1.7.0_80-b15) Java HotSpot(TM) 64-Bit Server VM (build 24.80-b11, mixed mode) fib(10,000) 6942 time = 14 fib(20,000) 13884 time = 10 fib(40,000) 27769 time = 11 fib(80,000) 55539 time = 23 fib(160,000) 111078 time = 51 fib(320,000) 222157 time = 108 fib(640,000) 444314 time = 181 fib(1,280,000) 888629 time = 590 fib(2,560,000) 1777259 time = 2530 fib(5,120,000) 3554518 time = 8785 fib(10,240,000) 7109037 time = 34603 fib(20,480,000) 14218074 time = 142635 fib(40,960,000) 28436148 time = 586950
Podemos comprobar como, a medida que el valor de n se duplica, el tiempo de ejecución básicamente se cuadruplica. También se puede ver, en el numero de bits, que los resultados son relativamente grandes.
Y ahora con Java 8. Para numeros pequeños, no observamos mucha diferencia respecto a Java 7, pero empezamos a ver divergencia aproximadamente en fib(1.280.000). Java 8 calcula fib(40.960.000) alrededor de 50 veces más rápido. No he tenido paciencia suficiente para hacer el cálculo con cifras mayores, porque tenía un vuelo que coger :-). No obstante, esperaría que el siguiente punto de cálculo fuese más o menos 75 veces más rápido.
heinz$ java -showversion FibonacciTest java version "1.8.0_74" Java(TM) SE Runtime Environment (build 1.8.0_74-b02) Java HotSpot(TM) 64-Bit Server VM (build 25.74-b02, mixed mode) fib(10,000) 6942 time = 6 fib(20,000) 13884 time = 3 fib(40,000) 27769 time = 7 fib(80,000) 55539 time = 16 fib(160,000) 111078 time = 27 fib(320,000) 222157 time = 40 fib(640,000) 444314 time = 58 fib(1,280,000) 888629 time = 155 fib(2,560,000) 1777259 time = 324 fib(5,120,000) 3554518 time = 734 fib(10,240,000) 7109037 time = 1661 fib(20,480,000) 14218074 time = 4412 fib(40,960,000) 28436148 time = 11870
Así pues, ahora ya hemos visto que Java 8 ha mejorado al menos en un punto. De todas formas, no ha sido suficiente, en mi opinión. Tanto Karatsuba como Toom-Cook pueden mejorarse todavía más con una división recursiva. Si realmente necesitas trabajar con cifras realmente grandes, probablemente querrás poner la carga en el hardware. Yo lo he probado modificando BigInteger para añadirle una pequeña MultiplyTask:
private static final class MultiplyTask
extends RecursiveTask {
private final BigInteger b1, b2;
public MultiplyTask(BigInteger b1, BigInteger b2) {
this.b1 = b1;
this.b2 = b2;
}
protected BigInteger compute() {
return b1.multiply(b2);
}
}
para después, cambiar el siguiente fragmento método multiplyKaratsuba():
BigInteger p1 = xh.multiply(yh); // p1 = xh*yh BigInteger p2 = xl.multiply(yl); // p2 = xl*yl
por el siguiente código
MultiplyTask mt1 = new MultiplyTask(xh, yh); mt1.fork(); BigInteger p2 = xl.multiply(yl); // p2 = xl*yl BigInteger p1 = mt1.join();//xh.multiply(yh); // p1 = xh*yh
Por defecto, este nuevo código utiliza el Pool común de Fork/Join, pero sería genial añadir un nuevo método a BigInteger que nos permitiese multiplicar en paralelo, por ejemplo: BigInteger.multiply(BigInteger, ForkJoinPool) o más explicitamente BigInteger.multiplyParallel(BigInteger, ForkJoinPool).
Mis modificaciónes a BigInteger han funcionado bastante bien. También he utilizado ManagedBlocker para implementar un «esquema de caché reservada» en Fibonacci que evite calcular el mismo número dos veces. ManagedBlocker funciona muy bien y mantiene los cores de mi máquina más ocupados.
Aquí teneis un tweet donde se ve en funcionamiento mi solución en paralelo sin utilizar ManagedBlocker. Observa que los cores están ociosos, especialmente al principio de la ejecución, cuando las cifras que se están multiplicando son pequeñas. En este segundo tweet, con el mismo código, pero con el «esquema de cache reservada» que usa ManagedBlocker para mantener el ForkJoinPool más activo. fib(1_000_000_000) acaba un 8% más rápido, según se ve en el gráfico de las CPUs, utilizando el hardware disponible mucho mejor. Si tienes curiosidad, este es el tipo de conceptos sobre los que hablamos en el curso de «Extreme Java – Concurrency and Performance for Java 8», que también puedes recibir en Español.
Espero que hayas disfrutado del artículo y que te haya resultado útil.
Saludos desde la soleada y acogedora Grecia.
Heinz.
Genial el artículo, y genial leer sobre algoritmos, su complejidad computacional, y notación de Landau, que prácticamente no había vuelto a ver desde mis tiempos de facultad.
Que bien, este tipo de tests dejan ver el nivel de refinamiento y eficiencia de un lenguaje.