martes, junio 08, 2010

El problema 10 del proyecto Euler o la criba de Eratóstenes

Si van al proyecto Euler y consultan el problema 10 van a encontrar que consiste en lo siguiente:

La suma de los primos menores a 10 es 2 + 3 + 5 + 7 = 17

Encuentra la suma de los primos menores a 2 millones.

Para resolverlo implementé una criba de Eratóstenes que tardó horas en obtener la respuesta (en términos de tiempo de ejecución eso equivale a eras geológicas). Escribí la solución en el proyecto Euler, recibí una palomita y luego leí la implementación de los autores del proyecto Euler, que también proponían una criba de Eratóstenes. Terminando de leer me levanté, fuí al espejo y dije:

- Controlzape eres un pendejo.

Bueno, ahora vamos por partes para que entiendan ese bonito momento de autoconocimiento.

¿Qué es una criba de Eratóstenes?

Es un método de hace un par de milenios para hallar números primos o más específicamente para discriminar factores de números primos. Aunque añejo es efectivo (sobre todo si se implementa bien, no con las patas como lo venía yo haciendo).

A grandes rasgos se trata de lo siguiente:

1. Escribes una lista del 2 hasta el número N que deseas evaluar.

2. Tacha todos los pares mayores a 2.

3. Escoges el siguiente número (P) más próximo que quedó sin tachar.

4. Tacha los multiplos de P hasta el número N.

5. Repite 3 y 4 hasta que ya no haya más números P para escoger.

6. Los números que quedaron sin tachar son los primos que hay del 2 hasta el N.

Así platicado esto (añadiendo la sumatoria del ejercicio 10 del proyecto Euler) lo que se necesita es un arreglo de 2 millones de booleanos cuyos elementos estén inicializados en falso; un loop que descarte a los índices pares superiores a 2 del arreglo poniéndolos en true; un loop anidado dentro de otro para ejecutar los pasos 3 y 4 del algoritmo, y por último, un loop sencillo que recorra el arreglo de booleanos, una vez terminada la criba, para ver cuales quedaron sin tachar e irlos sumando. La implementación es la siguiente (en Java):


Como ya lo dije, ese código tardó horas en llegar a la respuesta correcta. El que mencionaban en el proyecto Euler tardó segundos.

¿Qué le faltaba a mi implementación de la criba de Eratóstenes?

Tres cosas. La primera y más importante para disminuir el tiempo de ejecución es la siguiente: no es necesario que el loop externo de la criba evalúe todos los números impares de 2 hasta 2 millones. Basta con que evalúe de 2 hasta el entero mayor de la raíz cuadrada de 2 millones que equivale a 1415. ¿Por qué hasta ahí? Muy simple, porque los números no primos que hay entre la raíz cuadrada de N y N son multiplos de los números primos menores a la raíz cuadrada de N. Todos ellos.

Al aplicar al código esa característica de la criba de Eratóstenes, en vez de un loop anidado que efectúe millones de millones de operaciones, tenemos un loop anidado que efectúa miles de millones de operaciones. Eso en vez de tardar horas, tarda segundos.

El segundo defecto que tiene mi implementación se compone con un corolario de lo de la raíz de N: sí los números no primos después de raíz de N se pueden expresar como multiplicaciones entre primos menores a raíz de N, entonces eso significa que al evaluar cada número primo para descartar a sus múltiplos conviene empezar a evaluar no desde el número primo más 1, como yo muy tarugamente le estaba haciendo, sino que hay que empezar a evaluar desde el cuadrado del número primo. O en otras palabras, todos los números no primos que hay antes del cuadrado de ese número primo son múltiplos de los primos menores al que estamos evaluando.

Aplicar al código esta otra característica de la criba significa sustituir el loop interno de la criba para que empiece a evaluar en el cuadrado del indice del loop externo. A medida que la criba se vaya evaluando ese loop interno avanzará más rápido.

El tercer defectote de mi implementación es el siguiente: no es necesario hacer la operación de módulo para encontrar multiplos. Hay que aprovechar la característica de la criba y que ya eliminamos a los números pares para que la propia evaluación del loop nos posicione en los índices de la criba que serán múltiplos del primo que estamos evaluando y tacharlo sin hacer una operación de módulo. Esto significa que el loop interno de la criba hay que modificarlo para que se ejecute no en cada número impar, sino en cada número primo multiplicado por dos (la multiplicación por dos es para no recorrer los números pares -ya descartados- que también son múltiplos del número primo). Ahora bien, ahora sólo resta estar seguro de que no entremos al loop interior a menos que el loop exterior ya nos haya dado un número primo. Eso se consigue con una condicional.

El código entonces queda así (señalé en rojo las modificaciones).


Y obtiene uno la respuesta en 2 patadas.

pd. Para entender estas características de la criba de Eratóstenes lo que recomiendo es que hagan una, a mano, hasta 100. Después de tachar todos los pares (excepto el dos), y de efectuar los pasos, se darán cuenta que terminan justo después de tachar los múltiplos de 7 a partir del 49 y recorriéndolos de 14 en 14.

13 comentarios :

cineto dijo...

que etiqueta tan simpática, la "de pasos de baile"

Rodion Romanov Rashkolnikov dijo...

Me pendejeó esta entrada. No entendí ni el códifo, ni lo de los cuadrados de N y N ni des donde salió el 1415... mañana lo leo de nuevo. :(

Ahora Que Hice dijo...

Yo mejor no le entro a la prueba de escritorio, porque donde la cague, me quedo sentado hasta el final del universo, mejor voy y bajo el código para python o ruby, digo, para estar en la onda de hoy.

Ahora Que Hice dijo...

Aprovecho para recomendar el libro "De Euclides a Java", de Ricardo Peña Marí, ISBN:978-607-7551-06-5, que me regresó a la memoria con este post. Viene al caso porque uno de sus capitulos trata aquello de que hay algoritmos que por su coste en tiempo, son prácticamente inviables. De ahí que obtener la mayor brevedad en la ejecución de una rutina de código es objeto de análisis obcecado en las universidades, institutos y algunos congales en la doctores.

El Contador Ilustrado dijo...

cual fue el punto de eso?

yo confundido

controlzape dijo...

Rodion: tienes razón eso de N y N estaba confuso. Ya lo modifiqué.

Ahora que hice: Ah me late el título de ese libro. La sig visita que haga a la biblioteca central me consigo una copia.

ContadorIlustrado: Hacer mates y computación.

LoudTheremin dijo...

Borra mi comment si quieres, no importa. Digo, por aquello de arruinar la respuesta.

Pero me salio 17 y me senti tan pero tan bien de que java sigue teniendo sentido para mi.

Anónimo dijo...

hazlo en C

JRPB dijo...

Que chido que te hayas ido por el método elegante. Yo lo resolví en C y fuerza bruta, con un método nada respetable para determinar si un número es primo o no: if(!fmod(val, i)) return 0;

Donde 'val' es el número en cuestión e 'i' es el candidato a múltiplo. Iterando desde 2 hasta el primer entero mayor o igual a la raíz cuadrada de val Si el residuo de la división entre ambos es cero, el número no puede ser primo; en caso contrario se suma a un total global (después de cumplir todas las iteraciones). Tarda algunos segundos pero da la respuesta correcta.

Ya casi termina el semestre y le podré dedicar otro rato esto. Me quedé en el 16. Saludos.

ivan dijo...

Es muy simple entender porque se saca hasta la raiz cuadrada, si quiero sacar que si el 101 calculo hasta la raiz cuadrada las divisiones para 100 es 10,.. Nos quedamos con el entero Ejemplo:
Si divido 100 por 2 nos da 50.5 así indirectamente ya dividimos 100 por 50 y nos da 2. Si dividimos por 3 nos da 33.66, así segimos dividiendo hasta llegar a dividir por 10 y qe 10.1, seguir a 11 no hace falta ya que dividiendo por 9 nos da 11.2 sino dio exacto tampoco lo dara dividiendo por 11.

ivan dijo...

Las cribas de erastotenes y la de atkin varios ejemplos de varias personas son lentos, yo cree mi propia criba completamente diferente y supera varias veces esto evaluo de 1 hasta los 500 millones en 18 seg.Sin multitareas en una laptop simple comprada hace 2 años

controlzape dijo...

Muy bien, pero ¿dónde está el código?

Anónimo dijo...

recién acabo de leer tu artículo, y para tratar de entenderlo por completo, estoy siguiéndolo con el conjunto de números del 2 al 100 donde N=100 y raíz(N)+1=11. Pues bien, en el párrafo donde dices que los números no primos después de raíz(N) se pueden expresar como multiplicaciones entre primos menores a raíz(N), noto que por ejemplo el 39 sólo se puede expresar como 3x13... donde 13 es un primo mayor a raíz(N)... espero haberme explicado y espero me puedas orientar. Gracias!