- NeoFronteras - http://neofronteras.com -

Optimizan la criba de Eratóstenes

Inventan un nuevo algoritmo que ahorra memoria a la hora de implementar la criba de Eratóstenes.

Foto

Los números primos nos producen fascinación. Esos números que sólo son divisibles por ellos y por la unidad, son los números “fundamentales” a partir de los que se pueden obtener los demás. Los números no primos, o compuestos, no son más que el producto de varios números primos.

Hay algunas conjeturas que van más allá, como la de Goldbach, que sostiene que todo número par mayor que 2 puede obtenerse como la suma de dos primos. Sin embargo, todavía no se ha conseguido demostrar esta conjetura. Tampoco se ha demostrado que sea falsa, pues no se han encontrado contraejemplos pese a que se ha explorado hasta números muy grandes.

Se ha tenido más éxito con la conjetura débil de Goldbach que sostiene que todo número impar mayor que 5 se puede obtener como suma de tres primos, como 3 + 3 + 5 = 11 o 19 + 13 + 3 = 35. Esta conjetura fue demostrada en 2013 después de 271 años por matemático peruano Harald Helfgott (Universidad de Göttingen).

Pero este matemático no se ha conformado con esto y ha desarrollado un algoritmo que mejora la criba de Eratóstenes para encontrar números primos, que es del año 240 AC. La versión de Helfgott reduce mucho el uso de memoria de computador y puede, por tanto, reducir el tiempo de ejecución de un programa que busque números primos.

Eratóstenes era un astrónomo, matemático y geógrafo que además fue director de la biblioteca de Alejandría. Es famoso por calcular el tamaño de la Tierra.

Hace 23 siglos se disponía poco más que el conteo de pasos para medir distancias. Pero ya se habían inventado las Matemáticas y, además de la Aritmética, se disponía de la Geometría. En esa época Eratóstenes midió los pasos entre lo que es la actual Asuán en Egipto y Alejandría (u ordenó a alguien para que lo hiciera o copió el dato oficial disponible).

Durante el solsticio de verano el Sol proyecta sombras verticales en Asuán a mediodía, así que los rayos del sol son verticales y, en época, Eratóstenes podía medir al ángulo relativo del Sol en Alejandría durante el solsticio de verano midiendo la sombra proyectada por un palo (usó probablemente en realidad un cuadrante solar o algo similar).

Eratóstenes sabía que la Tierra era redonda, como cualquier persona instruida de la época, y se propuso medir el tamaño de este mundo usando esos datos, su intelecto y un poco de geometría. Si la unidad de medida fue el estadio egipcio (no se está seguro de este punto, pues pudo ser el estadio griego el usado) el matemático, astrónomo y geógrafo logró medir un valor para la circunferencia terrestre de 39.614,4 km frente a los 40.008 km reales, valor que arroja menos de un 1% de error relativo. A la hora de calcular la distancia a la Luna fue menos afortunado y calculó que había 123.280 km en lugar de los 384.400 km reales. Para la distancia Tierra-Sol obtuvo 139.996.500 km frente a los 149.597.870 km reales. Aunque en estos casos las órbitas elípticas no arrojan una distancia fija en el tiempo.

De todos modos, el error que cometió fue muy pequeño dada la existencia casi nula de tecnología de precisión en esa época.

Volviendo al asunto de los números primos, Eratóstenes propuso su famosa criba que permite ir encontrando números primos. De toda la lista de números naturales de un intervalo dado eliminamos primero todos los pares (salvo el 2 al ser primo), pues son múltiplos de 2 y, por tanto, compuestos. Luego los múltiplos de 3 (salvo el 3) y así sucesivamente. En cada paso nos van quedando cada vez menos números a comprobar. Los que van sobreviviendo son primos.

Este procedimiento sencillo puede enunciarse en un algoritmo que puede ser programado en un computador, pero su implementación requiere de mucha memoria. Los ordenadores actuales son muy rápidos y pueden efectuar cálculos en paralelo, pero la memoria siempre representa una limitación para los cálculos.

Para saber cómo de bueno es un algoritmo se deben considerar dos cosas: el número de operaciones por bit del input y el número de bits que hay que almacenar en la memoria mientras que las instrucciones son ejecutadas. La criba de Eratóstenes es relativamente eficiente respecto al número de operaciones a ser realizadas por bit, pues crece en proporción al tamaño del intervalo considerado. Pero la necesidad de memoria crece mucho con el tamaño del intervalo considerado y esto limita la eficiencia de la criba.

Hay otras cribas y algoritmos además de la de Eratóstenes, pero la ventaja de esta es que puede trabajar conjuntamente en la factorización de compuestos, que es la descomposición de un compuesto en producto de primos. Esto de la factorización es algo fundamental en la seguridad de sistema RSA de cifrado de clave pública, pues se basa en la dificultad de factorizar un compuesto formado por dos primos muy grandes. El RSA es el sistema que permite el comercio en Internet y las operaciones bancarias.

Helfgott ha sido capaz de modificar esta criba para que funcione con menos memoria en lo llama “método circular”. Así por ejemplo, para calcular primos en el entorno de los billones, la criba modificada requiere sólo unos pocos millones de bits en lugar de miles de millones que necesita la criba de Eratóstenes tradicional. Es decir, en lugar de necesitar una memoria de tamaño N sólo se necesita una memoria de tamaño raíz cuadrada de N.

Las principales ideas sobre este método se presentaron en julio pasado en XXI congreso de Álgebra Latinoamericano que se celebró en Nuevos Aires y en el Sinapsis 2016 de París.

Copyleft: atribuir con enlace a http://neofronteras.com/?p=5075 [1]

Fuentes y referencias:
Artículo en Scientific American. [2]
Esquema: Wikipedia.