Complejidad computacional de BigInteger.multiply() en Java 8

2
4966
En Java8, BigInteger incluye algoritmos con una menor complejidad computacional para la multiplicación y división de cifras grandes.  Aún podría mejorarse más paralelizando el método multiply() con Fork/Join.

[box style=»1″]

É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.

Heinz es el creador de "The Java Specialists' Newsletter".
Doctor en Informática, Heinz ha participado en el desarrollo de grandes aplicaciones en Java, ha formado a miles de desarrolladores profesionales y es ponente habitual en las principales conferencias sobre Java.
Reconocido como Java Champion por Sun Microsystems -los creadores de Java- por su trabajo en mejorar Java, Heinz imparte cursos de JavaSpecialists.eu por todo el mundo, de forma remota y presencial. Es autor de dichos cursos, incluidos 'Java Specialists Master', 'DesignPatterns and Concurrency Specialists' y 'Performance and Concurrency for Java 8'.

2 COMENTARIOS

  1. 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.

DEJA UNA RESPUESTA

Por favor ingrese su comentario!

He leído y acepto la política de privacidad

Por favor ingrese su nombre aquí

Información básica acerca de la protección de datos

  • Responsable:
  • Finalidad:
  • Legitimación:
  • Destinatarios:
  • Derechos:
  • Más información: Puedes ampliar información acerca de la protección de datos en el siguiente enlace:política de privacidad