Inicio > Programing > Encontrar mis primeros mil millones de primos (python)

Encontrar mis primeros mil millones de primos (python)

find_prime_05
En el post anterior logré realizar con cierta rapidez, ahora que voy por más números realizo una pequeña modificación al la función utilizada para conocer el avance por que ha quedado de esta manera:

def find_primes(limit):
    primes = [2]
    i = 3
    while i <= limit:
        is_prime = True
        sqrt_limit = int(i**(0.5) + 1)
        for prime in primes:
            if i % prime == 0:
                is_prime = False
                break
            if prime >= sqrt_limit: 
                break
        if is_prime:
            primes.append(i)
            # Se imprime el primo encontrado y el avance en porciento
            print i, i / float(limit) * 100,"%"
        i += 2
    print
    print "Cantidad de números primos encontrados: ", len(primes)
    return primes

Así que ahora ejecuto el script para encontrar los números primos hasta 1,000,000,000

In [1]: import find_primes

In [2]: primes = find_primes.find_primes(1000000000)
...

y asi luce la salida después de unos 3min
find_primes-02

es de notar que el avance será un poco lento ya que en aproximadamente 10min llegaré al 10% del total a procesar y eso que sólo son mil millones de números a procesar, en realidad tendría que procesar más para lograr el número de primos propuesto.

Revisando el sitio http://primes.utm.edu/links/programs/sieves/Eratosthenes/index.html se menciona que uno de los mejores métodos para halar los números primos del 2 a N es usando la criba de Erastotenes.

Hay un ejemplo creado en javascript que se puede ver como funciona para N = 49 por default, pero yo lo he puesto para 10,000 y creo que cualquier abuelita con su criba a mano terminado ya hubiera, sin embargo es muy didáctico el programa http://toni.technetium.be/source/eratosthenes.php?49 .
find_primes_03

Así que voy a hacer la versión en python con la idea de optimizar aún más la búsqueda.

Lo primero es crear la lista de números, pero estoy trabajando con listas del orden de mil millones y efectivamente numéricamente hablando python puede manejar esas cantidades, pero la memoria de mi laptop parece que no, tengo 8GB de ram y al tratar de crear la lista de mil millones se la come rapidísimo y luego va por la swap que es de sólo 4GB el sistema comienza a colapsar.

Entonces la pregunta es…

¿cómo manejar una lista de mil millones de elementos sin que mi laptop colapse?

He optimizado hasta donde me ha sido posible el código, he hecho uso de la librería numpy que es una librería matemática y me permite manipular operaciones con arrays enteros, así como también finalmente he incluido el uso de time para conocer el tiempo de ejecución y también voy imprimiendo el avance.

import numpy
import time

def find_primes_crib(limit):

    t1 = time.time()
    cribe = numpy.arange(3, limit, 2, int)
    sqrt_limit = int(limit**(0.5)) + 1
    
    primes = [2]
    x = numpy.ones(len(cribe), bool)
    
    for i in cribe:
        if not x[numpy.nonzero(cribe == i)[0][0]]:
            continue
        if i <= sqrt_limit:
            primes.append(i)
            x = x & (cribe % i != 0)
            print i, i / float(limit) * 100, "%"
        else:
            break
     
    for i in numpy.nonzero(x == True)[0]:
        primes.append(cribe[i])
        print i, i / float(limit) * 100, "%"
    
    t2 = time.time()
            
    print
    print "Cantidad de números primos encontrados: ", len(primes)
    print "Tiempo requerido: ", t2-t1, "seg."
    return primes

El programa ha funcionado muy bien para números del orden de 100,000,000 tardando aproximadamente unos 350 segundos, pero para el caso de mil millones, requiere de mucha memoria y comienza a hacer mucho uso de la swap, así que todo el sistema se ve afectado.

Entonces necesito una manera de comenzar a trabajar con números de ese orden sin que la memoria de mi laptop sea un problema, ya que incluso estos son los primos del orden muy pequeños.

Categorías:Programing Etiquetas: , ,
  1. Aún no hay comentarios.
  1. 16 febrero, 2013 a las 09:51

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

PiKon

3D Printing + Raspberry Pi Camera = PiKon Telescope

gvSIG blog

gvSIG project blog

Python Adventures

Welcome to the Jungle!

A %d blogueros les gusta esto: