En una materia de mi carrera Lic. Informática, mi docente nos dio de tarea(reto) calcular los números primos que se encuentran en el rango de mil millones números (100.000.000.000) y generarlo en un archivo.
Cualquiera dirá hallar el numero primo es fácil, si es verdad de echo ya hay algoritmos que te calculan los números primos, pero para un rango de mil millones la cosa se complica.
El reto esta en generarlo en el menor tiempo posible en el lenguaje funcional Haskell.
Mi docente me explico un poco como funciona la criba de Erastotenes, entonces decidí aplicar ese algoritmo para generar los números primos.
Este es mi primer intento para 10 millones de números:
Y obtuve los siguientes resultados
$ time ./Primes
real 1m8.407s
user 1m5.015s
sys 0m0.815s
Con mi código, de entrada no podre superar el reto, entonces me puse a analizar por que tardaba tanto y como podía mejorarlo.
Pude hacer la siguiente mejora para mil millones de números:
$time ./Primos
real 4m59.920s
user 4m40.015s
sys 0m6.015s
Si hacemos una comparación con mi primera versión, logre mejorar bastante ya que para el primero solo calculo para diez millones y para el segundo calculo para mil millones números.
Haciendo cálculos matemáticos 100 * 5 (redondeado al tiempo que tardo para mil millones) = 500 minutos y lo dividimos en 60 minutos, nos dará el siguiente resultado 500/60 = 8.33.
Esto quiere decir que para calcular el rango de mil millones de números tardara 8 horas con 33 minutos.
muy interesante tu solucion,
ResponderEliminaraunque me confundi un poco con los tiempos que pusiste, ...los intercambiaste
$time ./Primos
real 4m59.920s
user 4m40.015s
sys 0m6.015s
real 1m8.407s
user 1m5.015s
sys 0m0.815s
por cierto hay un concurso de numeros primos, aquel q alle el numero primo mas grande se ganara 100.000 $
ResponderEliminarte paso el articulo en el cual hallaron un numero primo de 13 millones de digitos.
http://www.neoteo.com/numero-primo-de-13-millones-de-digitos-13748.neo
tu ya probaste con 9 digitos que tanto tiempo te tomaria con 13 millones?
@Daniel la primera solución es para diez millones de números(10000000) y tarda 1m8.407s. La segunda solución es para mil millones de números(1000000000) y tarda 4m59.920s.
ResponderEliminarEn realidad probé para 10 dígitos; ahora para poder hacer para 13 millones de dígitos necesito un buen procesador y un disco de mas de un terabyte de espacio disponible ya que para 10 dígitos el archivo generado pesa 1.3G.
Pienso que el algoritmo se puede mejorar aplicando programación dinámica y así poder cumplir con mi reto para cien mil millones de números(12 dígitos) en el menor tiempo posible. Luego probare mi solución en una súper computadora :)
hola me podrias ayudar como implementar los numeros primos del 1 al 100 en haskell ?
ResponderEliminar