Continuando con uno de mis pasatiempos favoritos, que es la búsqueda de números primos, en esta ocasión deseo compartir con todos ustedes los avances que he realizado en la materia. En primer lugar, tengo que mencionar que siempre busco superarme, por lo que en este caso no fue la excepción, mis metas eran reducir el tiempo necesario para encontrar números primos y poder duplicar la cantidad de números primos encontrados.
Para ello hago uso de la programación multihilo, si tú no sabes que es la programación multihilo, te recomiendo leer este artículo que he redactado previamente: ¿Que es la programación multihilo?.
En esta entrada tampoco hablare de la metodología que uso para poder comprobar si un número es primo, esta información está presente en otro artículo: 100 Primeros Millones de Números Primos.
Una vez aclarados los puntos anteriores, la primera tarea que realice fue realizar la implementación de la programación multihilo (tarea nada sencilla y más en C++), si bien tengo experiencia en la programación multihilo, toda esta experiencia ha sido en Java, además que no eran aplicaciones en donde se buscara un alto rendimiento. Por lo que gran parte de la implementación multihilo se ha hecho gracias al ejemplo proporcionado en Dev-C++.
Otro punto importante a mencionar fue la búsqueda de un semáforo de alto rendimiento, para ello me ayudé de Google y Stackoverflow, en donde pude encontrar la respuesta en esta entrada.
A diferencia de la anterior implementación en donde solamente se hacía uso de una lista ligada para almacenar los números primos encontrados, en este caso, se crea una lista ligada para cada uno de los hilos de ejecución, de esta manera, no se pierde tiempo intentando ordenar de menor a mayor. Para poder realizar las comparaciones, los hilos pueden acceder a cualquiera de las listas ligadas. Por último, para poder almacenar todos los números primos encontrados, lo que se hace es determinar cuál es el número más pequeño que existe en todas las listas ligas, se almacena en un fichero de salida y se elimina de la lista ligada, este procedimiento se repite hasta terminar de vaciar todas las listas ligadas.
Intel Core i5-4210U y 8 GB RAM 1600 MHz DDR3
100 Millones de Números Primos
10 Millones de Números Primos
1 Millón de Números Primos
Intel Core i7-6700 y 12 GB RAM
200 Millones de Números Primos
100 Millones de Números Primos
10 Millones de Números Primos
1 Millón de Números Primos
Resultados
Al final los resultados que obtenemos han sido sorprendentes, haciendo uso de la programación multihilo, ha sido posible reducir aproximadamente en un 50% el tiempo pasando de 36 minutos a 15 minutos en el mismo ordenador con un procesador Intel Core i5-4210U (un procesador con 2 procesos, 4 hilos). En contra parte, el procesador Intel Core i7-6700, es casi 3 veces más rápido que el Intel Core i5-4210U, en donde se puedo encontrar los mismo 100 millones de números primos en solo 6 minutos. Aprovechando la velocidad superior del procesador i7, fue que tome la decisión de buscar 200 millones de números primos, es importante mencionar que esta búsqueda no se realizó desde 0, ya que, para acelerar un poco la búsqueda, se ingresó a través de un fichero TXT los 100 primeros millones de números primos, por lo que el tiempo total de cálculo seria de 28 minutos, si se piensa en una búsqueda completa de los 200 números primos.
Descargas
Descargar Código en CPP y EXE desde Github
Primeros 200 Millones de Números Primos TXT (Comprimido con 7z)
Dado que el archivo TXT es muy pesado de más de 1 Gb, necesitaras de un lector que sea capaz de poder abrir este tipo de archivos, por lo que les recomiendo EmEditor, el cual lo pueden descargas desde la siguiente página.