Búsqueda paralela de números primos

"Sieve for Seven", Scot Nelson.

Los números primos son aquellos números naturales mayores que 1 que sólo tienen dos divisores: el 1 y él mismo. Hay muchos problemas en Matemáticas relacionados con los números primos, algunos de ellos aún sin resolver, como la Conjetura de Goldbach. El objetivo de hoy será hallar todos los números primos hasta 2·10⁹.

Existen varios algoritmos para obtener listas de números primos, tal vez el más común sea la criba de Eratóstenes, que consiste en escribir una lista con todos los números que queremos estudiar y, partiendo del primero, tachar todos sus múltiplos, y repetir el proceso cada vez con el primer número que no hayamos tachado.

Este algoritmo presenta dos problemas:

1. Es destructivo (consiste en descartar), por lo que a priori consume demasiada memoria, y mucho tiempo en escribir candidatos.
2. Eliminar objetos de una lista impide trabajar con ella desde otra hebra, ni siquiera para iterar, con lo que perdemos la posibilidad de trabajar con multinúcleo.

Para solucionar esto podemos hacerlo al revés: considerar un número candidato X y buscar si hay alguno anterior en la lista que lo divida. Si no lo encontramos, consideraremos que X es primo y lo agregamos a la lista. Mantendremos la lista ordenada para que baste con buscar divisores hasta √X.

Esta técnica nos proporciona dos ventajas:

1. La única modificación que haremos a la lista será añadir al final, de forma que en lugar de una lista podríamos utilizar un vector, cuyo acceso es mucho más rápido.
2. Es posible paralelizar, porque podemos conseguir que los posibles divisores de cada candidato pertenezcan al vector que ya tenemos.

Para que esto funcione, dividiremos el algoritmo en etapas, en cada una de ellas consideraremos el último número primo encontrado, y su cuadrado será el último candidato posible en la siguiente etapa.

Todos los nuevos candidatos se reparten entre distintos procesos, que mantendrán el vector anterior como sólo lectura. Cada proceso tendrá un vector propio para guardar los número primos que encuentre, y al final de la etapa, todos ellos se añadirán al vector principal.

Esta gráfica muestra la mejora de tiempo que hemos conseguido con esta modificación de la criba de Eratóstenes:

Gráfica realizada con LibreOffice Calc.

En el siguiente enlace se puede descargar el algoritmo de la criba de Eratóstenes (eratosthenes), la versión constructiva paralelizable (list) y una utilidad derivada para consultar si un número es primo (primeq). Está programada en C++ con OpenMP y viene compilada para Windows x64 y Linux x64, acompañada del código fuente:

Descargar primes.zip

Hemos probado el programa en un ordenador portátil con un Intel Core i7 de 4 núcleos con la siguiente orden para buscar todos los números primos hasta 2·10⁹

$ ./list 2000000000

Y ha encontrado 98.222.287 números primos en 8:48 minutos, un tiempo aceptable, con una ganancia de 3,5 sobre la versión secuencial (./list -seq), generando un archivo de 1GB con todos ellos. En un sobremesa con un Core i7 más moderno ha tardado 4:20 minutos. ¡Reto superado!