[Aporte] Serie de Fibonacci

[razpeitia]

Código Python:

def fib(n):
    "Complexity: O(k^n), k = golden ratio"
    if n < 2:
        return n
    else:
        return fib(n - 1) + fib(n - 2)
 

Código Python:

def fib(n):
    "Complexity: O(n)"
    i = 1
    j = 0
    for c in xrange(1, n + 1):
        t = i + j
        i = j
        j = t
    return j
 

Código Python:

def fib(n):
    "Complexity: O(log(n))"
    if n <= 0:
        return 0
    i = n - 1
    (a, b) = (1, 0)
    (c, d) = (0, 1)
    while i > 0:
        if i % 2:
            (a, b) = (d * b + c * a,  d * (b + a) + c * b)
        (c, d) = (c * c + d * d, d * (2 * c + d))
        i = i / 2
    return a + b
 

Código Python:

def fib():
    i = 1
    j = 0
    yield j
    while True:
        t = i + j
        i = j
        j = t
        yield j
 
 
for i in fib():
    print i
    if i > 100: break
 

Generador para recorrer los números de fibonacci.

Un pequeño aporte para obtener la serie de fibonacci.

Ademas existe una formula para obtener el fibonacci en la posicion N, pero tiende a fallar para numeros grandes, debido a que maneja numeros irracionales.

[AlvaroG]

Se puede simplificar la primera usando "memoización" (o como sea que se traduzca del inglés). De hecho la función de Fibonacci es el ejemplo más clásico de esta técnica.
Claro, se tiene que guardar una lista de elementos ya calculados y se hace una búsqueda en la lista para cada ejecución, pero se reduce la cantidad de llamadas a la función recursiva de forma espectacular. Una buena técnica para tener a mano

Código python:

fib_memo = {}
def fib(n):
    if n < 2: return 1
    if not fib_memo.has_key(n):
        fib_memo[n] = fib(n-1) + fib(n-2)
    return fib_memo[n]
 

Ver un ejemplo más complejo (y más práctico) en http://code.activestate.com/recipes/...return-values/

Para calcular fib(20) con la versión original, hay que llamar a fib() 21891 veces
Para calcular fib(20) con la versión memoizada, hay que llamar a fib() 39 veces


Saludos.

[razpeitia]

Eso parece programación dinámica, el único problema que he hecho con programación dinámica es el problema 3n+1

[AlvaroG]

Pues sí, parece ser la misma cosa (o al menos uno de los tres puntos que se menciona en la wiki). No sabía lo que era la programación dinámica, gracias por el enlace Si habrá cosas por aprender...

[AxL456]

Este tema es muy interesante, hasta los momentos la mejor explicacion de "memoizacion" y la serie de fibonacci que he visto es en el curso de programacion I de harvard (aunque usan C y no Python), aqui les dejo el video:

http://cs50.tv/2007/fall/#l=lectures...tures/4/week4f

salten directamente a el minuto 17 para ver la explicacion de la serie de fibonacci

Y aqui consegui uno en youtube donde explican "memoizacion" con python:
http://www.youtube.com/watch?v=9fMQQuK0GBI

[zerokilled]

esta interesante el tema de la programacion dinamica. me lei la wiki en la version ingles, que por cierto, esta mas completo. aun no comprendo todos los conceptos porque no estoy muy familiarizado con el tema. pero me llamo mucho la atencion eso de memoization. aunque no viene al caso, ya que se esta discutiendo en python, pero igual pienso que es aplicable para cualquier lenguaje. transcribi dos pseudocodigo a javascript (la funcion recursiva y la memoization), me sorprendio ver la diferencia de rapidez en resultados. aqui se los comparto...

Código:

// recursiva;
fib = function(n){
if(n == 0)return 0;
if(n == 1)return 1;
return fib(n - 1) + fib(n - 2);
}

// memoization top-down;
m = {0:0, 1:1};
fib = function(n){
if(!m.hasOwnProperty(n)) m[n] = fib(n - 1) + fib(n - 2);
return m[n];
}

intenten por ejemplo el valor 100 en ambas versiones. es sorprendente las diferencias de resultado. gracias por crear este tema, porque creo que de aqui a 10 años mas no me hubiera enterado. deberian de crear un foro especificamente para tecnicas de programacion que sea aplicable para cualquier lenguaje.

[AlvaroG]

[fuera de tema]
zerokilled, si te interesa aplicar algunas técnicas interesantes (recursión, clausuras, memorización), bien explicadas en Javascript, te recomiendo el libro "Javascript: The Good Parts" de Douglas Crockford. No es muy caro, alrededor de 30 dólares en Amazon.
También están los videos del YUI Theater (http://developer.yahoo.com/yui/theater/) que cubren muchos de los temas del libro.
[/fuera de tema]

"técnicas de programación aplicable a cualquier lenguaje" suena como algo para el foro de Programación o para el de Ingeniería de Software (que a pesar de tener ese nombre tan formal, se supone que está para esta clase de temas).
El tema de la memorización es realmente aplicable a cualquier lenguaje, solamente se necesita recursión básica y vectores. Una clausura (closure) sería recomendable por "elegancia", para que el vector de resultados fuese inexistente a los ojos del resto del programa.

Sin duda está bueno discutir estos temas, siempre se aprende algo


Saludos.

[sam90]

Aca una forma iterativa de calcular fibonacci. No usa un vector. Es rapido para calcular un numero.

Código C++:

int fibwhile (int n){
    int res=1,res2 = 1, res3 = 1;
    while (n>2){
        res3 = res;
        res = res + res2;
        res2 = res3;
        n--;
    }
    return res;
}
 

Aunque si queremos hacer varias llamada a esta funcion en diferentes parte del programa, lo mas optimo es hacerla por dinamica que guarde en un vector los resultados y despues se obtienen en tiempo constante.

[zerokilled]

<offtopic>
@AlvaroG,
pues si, justamente tengo ese libro de Douglas. solo que no me lo he leido por completo. justamente hoy en la mañana estaba hojeando el libro y para mi sorpresa doy con el tema de memoization. las otras dos tecnicas ya las conocia.
</offtopic>

tendre que verificar bien a fondo los foros que has mencionado porque me parece que las veces que lo he visitado los temas estan enfocados a otras cosas. pero gracias por dejarme saber un lugar mas exacto donde buscar.

[AlvaroG]

Es que pocas veces se pregunta sobre técnicas, la mayor parte de las consultas son sobre cómo hacer x en el lenguaje z, y por tanto la pregunta termina perdida en el foro de z
Es inevitable, supongo. Un foro de buenas prácticas o técnicas de programación sería muy bueno pero seguramente tendría nada más un par de temas.


Saludos.

[Bosc]

Que interesante todo lo que esplicais,,, aunque mi nivel de programación es == 1 en una escala del 1 al 10 ..jajjaja me pierdo leyendo los codigos, pero capto la idea de lo que se pretende con la programacion dinamica.

Ojala algun dia me aproxime a vuestro nivel.

Saludos a todos

[caricatos]

Hola:

Me acuerdo que resolví el nº de fibonacci con asm (en viejos tiempos), simplemente usando un array binario, y sumar la celda par a la impar y viceversa según el número buscado con un bucle. Creo que es lo más rápido...

También pido disculpas por usar javascript:

function fibo(n) {
f = [0, 1];
for (i = 0; i < n; i++) f[i % 2] += f[(i+1) % 2];
return f[n % 2];
}

Saludos

[AlvaroG]

Cuesta ver lo que realmente hace esa función, pero si no me equivoco la serie de pasos es esta:
Al declarar el vector, queda esto
f[0] = 0
f[1] = 1

Y luego el bucle corre, generando:

f[0] = f[1] ( => f[0] =1)
f[1] = 2
f[0] = 3
f[1] = 5

Efectivamente resultando cada paso la suma de los dos anteriores. Cuesta verlo, pero produce el resultado esperado. Muy ingenioso, de verdad

[caricatos]

Hola:

Viendo como generar la serie como un array haciendo un pequeño retoque, me dí cuenta que tal como puse el algoritmo, el array inicial estaba al revés (f=[1,0]), y con esos retoques se obtiene la serie completa así:

Código:

function fibo(n) {
	r = [0];
	f = [1, 0];
	for (i = 0; i < n; i++) {
		f[i % 2] += f[(i+1) % 2];
		r.push(f[i % 2]);
	}
	return r;
}

Ahora el resultado fibo(1000) tarda en obtenerse algo más de 100 milisegundos ; y devuelve:

Código:

0,1,1,2,3,5,8,13,21,34,55,89,144,...
...,4.346655768693743e+208

Con el algoritmo recursivo, es impensable llegar al índice 50 (incluso solo devolviendo un número y no la serie) ...

Saludos

[razpeitia]

Caricatos: El operador modulo (a mi parecer) puede ser un poco lento cuando de trata de potencias de 2.

El mismo codigo pero mas rapido podria ser sustituyendo i % 2 por i & 1. Ya que solo nos interesa el bit de paridad.

[caricatos]

Iniciado por razpeitia

Caricatos: El operador modulo (a mi parecer) puede ser un poco lento cuando de trata de potencias de 2.

El mismo codigo pero mas rapido podria ser sustituyendo i % 2 por i & 1. Ya que solo nos interesa el bit de paridad.

Sí, seguro que tienes razón, tan solo lo puse de forma fácil de implementar (lo consideraré en el futuro), ya que como expliqué antes, lo había implementado en ensamblador, y en tal caso se consulta el flag de paridad...

Buen aporte... me gustaría saber como se queda el código en python, y sobre todo saber los tiempos de respuesta... supongo que versiones recurrentes no se podrían evaluar.

Saludos

[AlvaroG]

Iniciado por caricatos

me gustaría saber como se queda el código en python, y sobre todo saber los tiempos de respuesta

No muy diferente al código que pusiste, al menos la "traducción literal":

Código Python:

def fib(n):
    r = [0]
    f = [1, 0]
 
    for i in range(0, n):
        f[i % 2] += f[(i+1) % 2]
        r.append(f[i%2])
 
    return r
 

Creo que la generación de la lista debería poder hacerse con un generador, pero ahora mismo no se me ocurre cómo.
La función puede calcular fib(10000) casi inmediatamente, demora muchísimo más imprimir la lista de resultados dado que el número devuelto es el número completo, no abreviado con exponentes). Increíble

A propósito, fib(10000) es
33644764876431783266621612005107543310302148460680 06390656476997468008144216666236815559551363373402 55820653326808361593737347904838652682630408924630 56431887354544369559827491606602099884183933864652 73130008883026923567361313511757929743785441375213 05205043477016022647583189065278908551543661595829 87279682987510631200575428783453215515103870818298 96979161312785626503319548714021428753269818796204 69360978799003509623022910263681314931952756302278 37628441540360584402572114334961180023091208287046 08892396232883546150577658327125254609359112820392 52853934346209042452489294039017062338889910858410 65183173360437470737908552631764325733993712871937 58774689747992630583706574283016163740896917842637 86242128352581128205163702980893320999057079200643 67426202389783111470054074998459250360633560933883 83192338678305613643535189213327973290813373264265 26339897639227234078829281779535805709936910491754 70808931841056146322338217465637321248226383092103 29770164805472624384237486241145309381220656491403 27510866433945175121615265453613331113140424368548 05106765843493523836959653428071768775328348234345 55736671973139274627362910821067928078471803532913 11767789246590899386354593278945237776744061922403 37638674004021330343297496902028328145933418826817 68389307200363479562311710310129195316979460763273 75892535307725523759437884345040677155557790564504 43016640119462580972216729758615026968443146952034 61493229110597067624326851599283470989128470674086 20085871350162603120719031720860940812983215810772 82076353186624611278245537208532365305775956430072 51774431505153960090516860322034916322264088524885 24331580515348496224348482993809050704834824493274 53732624567755879089187190803662058009594743150052 40253270974699531877072437682590741993963226598414 74981936092852239450397071654431564213281576889080 58783183404917434556270520223564846495196112460268 31397097506938264870661326450766507461151267752274 86215986425307112984411826226610571635150692600298 61704945425047491378115154139941550671256271197133 25276363193960690289565028826860836224108205056243 0701794976171121233066073310059947366875L

En comparación, la versión recursiva original demora algo maś de 10 segundos para calcular fib(35).
La versión modificada para usar memorización falla con "RuntimeError: maximum recursion depth exceeded" al intentar calcular fib(1000), aunque es casi instantánea en los casos donde funciona.


Saludos

[razpeitia]

Iniciado por AlvaroG

La versión modificada para usar memorización falla con "RuntimeError: maximum recursion depth exceeded" al intentar calcular fib(1000), aunque es casi instantánea en los casos donde funciona.

Eso es por que el stack (pila) de python es muy pequeña.
Un pequeño programa para checar el tamaño de la pila en python, en C es mucho mas grande.

Código Python:

def f(n):
    print n
    try:
        f(n + 1)
    except RuntimeError:
        exit()
 
f(1)
 

[caricatos]

Hola:

¿Qué numerazo... ?...

Probé con javascript obtener fib(10000) y en todos los navegadores la respuesta es "Infinity" ... y otra cosa curiosa es que no puedo conseguir el número sin comprimir... incluso fabricándome una funcioncita que va dividiendo el resultado por 10 hasta quedarse en cero...

Y por cierto, no hice cálculos de eficiencia o de velocidad pero la versión de control de paridad es:

Código:

function fib(n) {
	r = [0];
	f = [1, 0];
	for (i = 0; i < n; i++) {
		f[i & 1] += f[(i + 1) & 1];
		r.push(f[i & 1]);
	}
	return r;
}

Saludos

[zerokilled]

[offtopic]
¿¡numerazo!? a mi por poco se me cae la quijada.

@caricatos,
ya me habia topado que numeros muy altos en javascript devuelven Infinity pero no se me ocurrio obtener un numero real. lo que si me dio curiosidad fue determinar cuanto tiempo demora javascript en devolver el resultado con numeros altos. en chrome, solo pude llevar hasta fib(14568). mas alla de eso me rebota el error Maximum call stack size exceeded.
[/offtopic]

[AlvaroG]

Iniciado por caricatos

Probé con javascript obtener fib(10000) y en todos los navegadores la respuesta es "Infinity" ... y otra cosa curiosa es que no puedo conseguir el número sin comprimir... incluso fabricándome una funcioncita que va dividiendo el resultado por 10 hasta quedarse en cero...

Python tiene la particularidad de utilizar enteros de largo arbitrario.
Es decir, el tipo entero "base" tiene un límite, y se hacen operaciones con él mientras se pueda. Cuando este tipo se desborda, se utiliza automáticamente el tipo long, de largo arbitrario, más lento pero que permite mostrar todos los dígitos.
Gracias a eso puede mostrar el número completo

[zerokilled]

@AlvaroG,
¿que tal? veras, estoy haciendo un desafio que realizó nuestro amigo caricatos en el foro Javascript. como ya habia mencionado caricatos, en javascript los numeros grandes se comprimen usando notacion exponencial. el desafio consiste en adquirir la cifra de una posicion dada en la serie fibonacci sin comprimir. el punto es que me dio curiosidad intentar la posicion 10000 y compararla con la cifra que antes nos mostrastes. pero tengo duda... ¿que posibilidad hay que en python, en algun punto de la calculacion, los numeros se truncan? la pregunta porque mi resultado no es el mismo del que nos compartes. esta es la cifra que obtengo.

32410299554128898509095014053145272693389029309118 51482631092153391329051453381408508511847983222132 79692640628014462682249930438740513749783895372061 72926321955923681625807731523740287505379141075511 29182758534489154566168394244167327647609377135670 86128014801069708178842949819608705790174659625840 95927044664136765451335711628216927892583892146530 73050080585675605006497530663962305548459172750568 58421555128109557174446011160879885406701558401568 85356378144625558777640501252970761201975955311235 64985474627415049611548140161476072671287811847642 29426277420655590258472548909385053969669356066918 25013676681291136101795610548851132457927487136889 81739562440304867970333622867076333700006650506023 65217333347825543792123499130261774325796527450281 29363509131478757338516576599441218887901888786374 56354087474931555483533356541815237271228877474747 37637732813404537021025145375166345284985778445900 47804064374352945610287140827671246120242172085895 17118850405585051308520605714373387197722802090378 93290660083873080828475925476771728180826196648752 24624876533490815572188255787689947366875

[AlvaroG]

Pues estuve revisando, y la función de python me da números que coinciden con los que he encontrado en las interwés
Comprobé contra los de esta página: http://www.maths.surrey.ac.uk/hosted...le.html#fib100, y parece que coinciden. Lo interesante es que en fib(200) ya se utiliza en Python el tipo long int, y el resultado es correcto (me parece importante destacarlo ya que en parte muestra que el tipo long int no tiene pérdida de precisión). Quizás quieras comparar tu función contra esos resultados.

caricatos, la función original que pusiste estaba bien. En la versión que solamente devuelve un número, f debe inicializarse como [0,1] o fib(n) devuelve en realidad fib(n-1). En la versión que devuelve una lista, debe inicializarse como [1,0]. Supongo que el asunto es la inicialización de r como [0] (una lista / vector de 1 elemento) y el hecho de que en cada paso se le añade una entrada.


Saludos

[caricatos]

Iniciado por AlvaroG

Pues estuve revisando, y la función de python me da números que coinciden con los que he encontrado en las interwés
Comprobé contra los de esta página: http://www.maths.surrey.ac.uk/hosted...le.html#fib100, y parece que coinciden. Lo interesante es que en fib(200) ya se utiliza en Python el tipo long int, y el resultado es correcto (me parece importante destacarlo ya que en parte muestra que el tipo long int no tiene pérdida de precisión). Quizás quieras comparar tu función contra esos resultados.

caricatos, la función original que pusiste estaba bien. En la versión que solamente devuelve un número, f debe inicializarse como [0,1] o fib(n) devuelve en realidad fib(n-1). En la versión que devuelve una lista, debe inicializarse como [1,0]. Supongo que el asunto es la inicialización de r como [0] (una lista / vector de 1 elemento) y el hecho de que en cada paso se le añade una entrada.


Saludos

Hola:

Tienes razón, y así empiezo la inicialización ahora... además, si hacemos un bucle desde 0 a 0, no se entrará nunca al cuerpo del bucle y por consiguiente la lista (o mejor dicho serie) quedaría vacía... y no es así.

Saludos

[zerokilled]

@AlvaroG,
¡gracias por revisarlo! pues al final hice lo mismo que tu, comparar mis resultados con alguna lista ya generada en internet. me fije en varias fuentes por los resultados y era una señal clara de que tenia algo mal. pero si no fuera porque compare los resultados, nunca me habria fijado del problema logistico que tenia. ¡gracias una vez mas!