Complejidad computacional de BigInteger.multiply() en Java 8

2
3164
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:

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:

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:

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.

Y aquí tenemos la salida de su ejecución con Java 7:

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.

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:

para después, cambiar el siguiente fragmento método multiplyKaratsuba():

por el siguiente código

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.

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.

Dejar respuesta

Please enter your comment!
Please enter your name here