Comentarios

1. Vesión modificada para dar el nth número fibonacci en lugar del comportamiento anterior:

   ---

   #!/usr/bin/env python
   # -*- coding: utf-8 -*-
   # $Id: fibo2.py,v f1da7fe85ab7 2006/12/11 18:06:29 -0400 $
   
   def fibogen(n):
       """
       fibogen(n) -> generator
   
       #for testing in doctest ;-)
       >>> [n for n in fibogen(-1)]
       [None]
       >>> [n for n in fibogen(0)]
       [0]
       >>> [n for n in fibogen(18)]
       [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584]
       """
       nth, n_0, n_1 = 0, 1, 1
   
       if n < 0:
           yield None
           raise StopIteration
       if n == 0:
           yield 0
           raise StopIteration
       if n > 0:
           yield n_0
           nth = nth+1
       if n > 1:
           yield n_1
           nth = nth+1
   
       n_n = n_1+n_0
       while nth < n:
           yield n_n
           nth, n_0, n_1 = nth+1, n_1, n_n
           n_n = n_1+n_0
   
   def _test():
       import doctest
       doctest.testmod()
   
   if __name__ == "__main__":
       _test()
   
   

   Rho on Monday, 11 December 2006, 18:08 BOT # |

2. Vi que la generación de la secuencia de fibonacci en una lista, ej:

   >>> [n for n in fibogen(18)]
       [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584]

    tiene la desventaja de comerse toda la memoria, si digamos queremos calcular el número fibo un millón (1000000).

   Pero de la siguiente manera en consuma de memoria es constante, podría decir O(1)  --si alguien me ayuda en los conceptos please!!!--, ej:

   >>> from fibo2 import fibogen
   >>> i, n = 0, 0
   >>> fgen = fibogen(1000000)
   >>> while i < 1000000:
   ...     i, n = i+1, fgen.next()
   ...
   >>> n

    El resultado, que tardo unos minutos (~30) lo pueden bajar acá: fibo_unmillon.txt

   
   

   Rho on Monday, 11 December 2006, 18:44 BOT # |

3. Otra versión, usando la formula no recursiva y con la ayuda de GMP para evitar el error de "Out of Range". En este caso es mucho más rápido que la versión en puro python.

    Calcula fibo(1000000) en segundos.

   ---

   #!/usr/bin/env python
   # -*- coding: utf-8 -*-
   # $Id: fibo4.py,v 96aa622d6820 2006/12/11 19:09:00 -0400 $
   
   def fibo(n):
       """
       Ref: http://es.wikipedia.org/wiki/Sucesi%C3%B3n_de_Fibonacci
       """
       from gmpy import mpf,mpz
   
       phi = mpf(1.6180339887498949) # (1+sqrt(5))/2
       rho = mpf(-0.6180339887498949) # (1-sqrt(5))/2
       sqrt_5 = mpf(2.2360679774997898) # sqrt(5)
   
       F = lambda n: (phi**n - rho**n)/sqrt_5
   
       if n < 0:
           return None
       if n in (0,1):
           return n
       else:
           return mpz(F(n))
   
   def _test():
       import doctest
       doctest.testmod()
   
   if __name__ == "__main__":
       _test()
   
   

   Rho on Monday, 11 December 2006, 19:09 BOT # |

4. Pero, si se trata de cosas serías, mejor usar el método fibo del módulo GMP (GNU Multiple Precision Arithmetic Library)

   fib(...)
       fib(n): returns the n-th Fibonacci number; takes O(n) time; n must be
       an ordinary Python int, >=0.

   
   >>> from gmpy import fib
   >>> fib(1000)
   mpz(43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875L)
   
   

   Rho on Monday, 11 December 2006, 19:12 BOT # |

5. ese es el punto.....en este tipo de lenguajes de evaluación rígida no es posible jugar

   con valores inmensos o inmesa cantidad de valores, trta con lenguajes que implementan 

   evaluación perezosa (i.e Haskell) y la vida te ira mejor.....especialmente en esto de la evaluación y calculo sobre conjuntos No finitos.

     

    

   Marcelo Flores on Wednesday, 13 December 2006, 14:30 BOT # |