Foro de elhacker.net

Programación => Programación C/C++ => Mensaje iniciado por: do-while en 20 Julio 2013, 14:11 pm


Título: Sucesion de Fibonacci recursiva optimizada
Publicado por: do-while en 20 Julio 2013, 14:11 pm
¡Buenas!

Esta mañana me he dedicado a perder el tiempo, así que comparto el tiempo perdido con vosotros y no tengo la sensación de haberlo perdido para nada.

Se trata de la sucesión de Fibonacci (ya conocida por todos (supongo)).

El algoritmo obtenido no es tan rápido como la versión iterativa (creo que anda cerca), pero mejora con creces la versión recursiva.

Evidentemente no es inmediata, como la formula que obtiene el enésimo termino en función de n y de phi (el numero aureo...)

Tampoco he utilizado programación dinamica, así que el único problema de memoria, si lo hubiese, estaría originado por una cantidad excesiva de llamadas recursivas.

Aquí os dejo un par de códigos. El primero con explicaciones sobre como se llega a la formula utilizada y con una comparación entre el algoritmo clásico y el optimizado, y el segundo para utilizarlo desde la linea de comandos, por si a alguien le hace ilusión.

¡Saludos!

Código
  1. /*
  2.   JUGANDO UN POCO CON LA SUCESION DE FIBONACCI
  3.   ============================================
  4.  
  5.   La sucesion de Fibonacci se define de forma recursiva como:
  6.  
  7. fibo(n) = n  si n = 0 ó 1
  8. fibo(n) = fibo(n - 1) + fibo(n - 2) si n > 1
  9.  
  10.   Aplicar la recursion de esta forma hace que el numero de llamadas sea de orden
  11. exponencial con respecto al tamaño inicial del dato, por lo que el algoritmo se
  12. vuelve lento rapidamente.
  13.  
  14.   Suponiendo n suficientemente grande podemos descomponer fibo(n - 1) en el paso
  15. de recurcion como sigue:
  16.  
  17. fibo(n) = fibo(n - 1) + fibo(n - 2) = (fibo(n - 2) + fibo(n - 3)) + fibo(n - 2) =
  18. = 2 * fibo(n - 2) + fibo(n - 3)
  19.  
  20.   Aplicamos el mismo proceso a fibo(n - 2):
  21.  
  22. fibo(n) = 2 * fibo(n - 2) + fibo(n - 3) = 2 * (fibo(n - 3) + fibo(n - 4)) + fibo(n - 3) =
  23. = 3 * fibo(n - 3) + 2 * fibo(n - 4)
  24.  
  25.   Y para ver las cosas mas claras lo repetimos con fibo(n - 3):
  26.  
  27. fibo(n) = 3 * fibo(n - 3) + 2 * fibo(n - 4) = 3 * (fibo(n - 4) + fibo(n - 5) + 2 * fibo(n - 4) =
  28. = 5 * fibo(n - 4) + 3 * fibo(n - 5)
  29.  
  30.   Por si no queda claro donde queremos llegar resumimos lo que tenemos hasta ahora:
  31.  
  32.   Cada una de las siguientes expresion son iguales a fibo(n):
  33.  
  34. 1 * fibo(n - 1) + 1 * fibo(n - 2) = fibo(2) * fibo(n - 1) + fibo(1) * fibo(n - 2) =
  35. 2 * fibo(n - 2) + 1 * fibo(n - 3) = fibo(3) * fibo(n - 2) + fibo(2) * fibo(n - 3) =
  36. 3 * fibo(n - 3) + 2 * fibo(n - 4) = fibo(4) * fibo(n - 3) + fibo(3) * fibo(n - 4) =
  37. 5 * fibo(n - 4) + 3 * fibo(n - 5) = fibo(5) * fibo(n - 4) + fibo(4) * fibo(n - 5)
  38.  
  39.   Si seguimos de esta forma podemos intuir que
  40.  
  41.   fibo(n) = fibo(k + 1) * fibo(n - k) + fibo(k) * fibo(n - k - 1) := F(n,k) para 0 <= k < n
  42.  
  43.   Se puede demostrar por induccion que fijando un N natural (N >= 2) se tiene que
  44.  
  45.   fibo(N) = F(N,k) para todo 0 <= k < N
  46.  
  47.   y que fijado K natural para todo n > K se tiene que
  48.  
  49.   fibo(n) = F(n,K)
  50.  
  51.   por lo tanto tenemos:
  52.  
  53.   fibo(n) = F(n,k) = fibo(k + 1) * fibo(n - k) + fibo(k) * fibo(n - k - 1) para 0 <= k < n
  54.  
  55.  
  56.   SUCESION DE FIBONACCI OPTIMIZADA
  57.   ================================
  58.  
  59.   Escribiremos fibo(n) como  f(n), es mas corto :-)
  60.   Partiendo de la expresion F(n,k) consideraremos dos casos:
  61.  
  62.   - n par:
  63.  
  64.         Sea k = n / 2
  65.  
  66.         Asi F(n,k) = f(k + 1) f(n - k) + f(k) f(n - k - 1) =
  67.         f(n/2 + 1) f(n/2) + f(n/2) f(n/2 - 1) =
  68.         =f(n/2) (f(n/2 + 1) + f(n/2 - 1)
  69.  
  70.         F(n,n/2) = f(n / 2) * (f(n / 2 + 1) + f(n / 2 - 1)) := F(n)
  71.  
  72.     - n impar:
  73.  
  74.         Sea k = (n - 1) / 2
  75.  
  76.         F(n,k) = f(k + 1) f(n - k) + f(k) f(n - k - 1) =
  77.         f((n - 1) / 2 + 1) f((n + 1) / 2) + f((n - 1) / 2) f((n + 1) / 2 - 1) =
  78.         f((n + 1) / 2) f((n + 1) / 2) + f((n - 1) / 2) f((n - 1) / 2) =
  79.         (f((n + 1) / 2))^2 + (f((n - 1) / 2))^2
  80.  
  81.         F(n,(n - 1)/2) = (f((n + 1) / 2))^2 + (f((n - 1) / 2))^2 := F(n)
  82.  
  83.     Por lo tanto definimos la sucesion de Fibonacci como sigue:
  84.  
  85.     fibo(0) = 0
  86.     fibo(1) = 1
  87.     fibo(n) = F(n) si n > 1
  88.  
  89.     donde:
  90.         F(n) = fibo(n / 2) * (fibo(n / 2 + 1) + fibo(n / 2 - 1)) si n par
  91.         F(n) = (fibo((n + 1) / 2))^2 + (fibo((n - 1) / 2))^2     si n impar
  92.  
  93.     Observemos ahora que si n==2,
  94.  
  95.     fibo(2) = F(2) = fibo(1) * (fibo(2) + fibo(0)) = fibo(1) * fibo(2)
  96.  
  97.     y tenemos una recursion infinita, ya que para calcular fibo(2) hay que calcular fibo(2)...
  98.  
  99.     Asi pues, tenemos la definicion final de la sucesion de Fibonacci:
  100.  
  101.     fibo(0) = 0
  102.     fibo(1) = 1
  103.     fibo(2) = 1
  104.     fibo(n) = F(n) si n > 1
  105.  
  106.     con F(n) como antes.
  107.  
  108.     Definiendo fibo(n) de esta forma, en cada paso de recursion generamos dos o tres llamadas
  109.     a la misma funcion fibo, pero en cada una de ellas reducimos el tamaño del dato inicial a
  110.     la mitad, por lo que el coste computacional es mucho menor (¿Cual es el coste? No se calcularlo)
  111. */
  112.  
  113. #include <stdio.h>
  114. #include <stdlib.h>
  115. #include <time.h>
  116.  
  117. #define MIN 37
  118. #define MAX 42
  119.  
  120. typedef unsigned long long fibo_t;
  121.  
  122. unsigned long long llamadas_clasico;
  123. unsigned long long llamadas_optimizado;
  124.  
  125. fibo_t fibo_clasico(fibo_t n)
  126. {
  127.     llamadas_clasico++;
  128.  
  129.     if(n == 0)
  130.         return 0;
  131.     if(n == 1)
  132.         return 1;
  133.  
  134.     return fibo_clasico(n - 1) + fibo_clasico(n - 2);
  135. }
  136.  
  137. fibo_t fibo(fibo_t n)
  138. {
  139.     llamadas_optimizado++;
  140.  
  141.     if(n == 0)
  142.         return 0;
  143.     if(n == 1)
  144.         return 1;
  145.     if(n == 2) //Evitamos recurion infinita si n == 2
  146.         return 1;
  147.  
  148.     if(n % 2) //n impar y mayor que 2
  149.     {
  150.         fibo_t k1,k2;
  151.  
  152.         k1 = fibo((n + 1) / 2);
  153.         k2 = fibo((n - 1) / 2);
  154.  
  155.         return k1 * k1 + k2 * k2;
  156.     }
  157.  
  158.     //n par y mayor que 2
  159.     return fibo(n / 2) * (fibo((n / 2) + 1) + fibo((n / 2) - 1));
  160.     //si n == 2 fibo(n / 2) * fibo(n / 2 + 1) = fibo(1) * fibo(2)
  161.     //habria recursion infinita si no se pone n == 2 como caso base
  162. }
  163.  
  164. int main(int argc, char *argv[])
  165. {
  166.     fibo_t i,valor;
  167.     time_t ini;
  168.  
  169.     printf("Fibonacci clasico:\n");
  170.  
  171.     ini = time(NULL);
  172.  
  173.     for(i = MIN ; i < MAX ; i++)
  174.     {
  175.         llamadas_clasico = 0;
  176.         valor = fibo_clasico(i);
  177.  
  178.         printf("  fibo_clasico(%llu) = %llu (%llu llamadas)\n",i,valor,llamadas_clasico);
  179.     }
  180.  
  181.     printf("%llu segundos\n",time(NULL) - ini);
  182.  
  183.     printf("\nFibonacci optimizado:\n");
  184.  
  185.     ini = time(NULL);
  186.  
  187.     for(i = MIN ; i < MAX ; i++)
  188.     {
  189.         llamadas_optimizado = 0;
  190.         valor = fibo(i);
  191.  
  192.         printf("  fibo(%llu) = %llu (%llu llamadas)\n",i,valor,llamadas_optimizado);
  193.     }
  194.  
  195.     printf("%llu segundos\n",time(NULL) - ini);
  196.  
  197.     return 0;
  198. }
  199.  

Código
  1. #include <stdio.h>
  2.  
  3. typedef unsigned long long fibo_t;
  4.  
  5. fibo_t fibo(fibo_t n)
  6. {
  7.     if(n == 0)
  8.         return 0;
  9.     if(n == 1)
  10.         return 1;
  11.     if(n == 2)
  12.         return 1;
  13.  
  14.     if(n % 2)
  15.     {
  16.         fibo_t k1,k2;
  17.  
  18.         k1 = fibo((n + 1) / 2);
  19.         k2 = fibo((n - 1) / 2);
  20.  
  21.         return k1 * k1 + k2 * k2;
  22.     }
  23.  
  24.     return fibo(n / 2) * (fibo((n / 2) + 1) + fibo((n / 2) - 1));
  25. }
  26.  
  27. int convertir(char *s, fibo_t *valor)
  28. {
  29.     *valor = 0;
  30.  
  31.     while(*s)
  32.     {
  33.         if((*s) < '0' || (*s) > '9')
  34.         {
  35.             *valor = 0;
  36.             return 0;
  37.         }
  38.  
  39.         *valor *= 10;
  40.         *valor += (*(s++)) - '0';
  41.     }
  42.  
  43.     return 1;
  44. }
  45.  
  46. int main(int argc, char *argv[])
  47. {
  48.     int i;
  49.     fibo_t n;
  50.  
  51.     if(argc < 2)
  52.     {
  53.         fprintf(stderr,"\nLinea de comandos: %s PARAMETRO_1 [PARAMETRO_2 ... PARAMETRO_N]\n\n",argv[0]);
  54.         fprintf(stderr,"Los distintos parametros deben ser enteros positivos\n");
  55.         return 1;
  56.     }
  57.  
  58.     fprintf(stdout,"\n");
  59.  
  60.     for(i = 1 ; i < argc ; i++)
  61.     {
  62.         if(!convertir(argv[i],&n))
  63.             fprintf(stderr,"%s: parametro incorrecto\n",argv[i]);
  64.         else
  65.             fprintf(stdout,"%s(%llu) = %llu\n",argv[0],n,fibo(n));
  66.     }
  67.  
  68.     return 0;
  69. }
  70.  

Título: Re: Sucesion de Fibonacci recursiva optimizada
Publicado por: 0xDani en 20 Julio 2013, 20:08 pm
Muy buen código, y de hecho si que está optimizado  :o

Cita de: Program output
Fibonacci clasico:
  fibo_clasico(37) = 24157817 (78176337 llamadas)
  fibo_clasico(38) = 39088169 (126491971 llamadas)
  fibo_clasico(39) = 63245986 (204668309 llamadas)
  fibo_clasico(40) = 102334155 (331160281 llamadas)
  fibo_clasico(41) = 165580141 (535828591 llamadas)
46 segundos

Fibonacci optimizado:
  fibo(37) = 24157817 (88 llamadas)
  fibo(38) = 39088169 (141 llamadas)
  fibo(39) = 63245986 (90 llamadas)
  fibo(40) = 102334155 (131 llamadas)
  fibo(41) = 165580141 (95 llamadas)
0 segundos

Título: Re: Sucesion de Fibonacci recursiva optimizada
Publicado por: amchacon en 20 Julio 2013, 23:11 pm
¿46 segundos?  :huh: A mí me ha tardado 2-3 segundos el método clásico.

Excelente código, aunque voy a ser un poco troll y voy a mejorar el método clásico:

Código
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <time.h>
  4.  
  5. #define MIN 37
  6. #define MAX 42
  7.  
  8. typedef unsigned long long fibo_t;
  9.  
  10. unsigned long long llamadas_clasico;
  11. unsigned long long llamadas_optimizado;
  12.  
  13. #define MAX_CACHE 33
  14.  
  15. unsigned long long Fibonaci_Cache[MAX_CACHE] = {1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597
  16. ,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269,2178309,31524578};
  17.  
  18. fibo_t fibo_clasico(fibo_t n)
  19. {
  20.     llamadas_clasico++;
  21.  
  22.     if(n < MAX_CACHE)
  23.         return Fibonaci_Cache[n];
  24.  
  25.     return fibo_clasico(n - 1) + fibo_clasico(n - 2);
  26. }
  27.  
  28. fibo_t fibo(fibo_t n)
  29. {
  30.     llamadas_optimizado++;
  31.  
  32.     if(n == 0)
  33.         return 0;
  34.     if(n == 1)
  35.         return 1;
  36.     if(n == 2) //Evitamos recurion infinita si n == 2
  37.         return 1;
  38.  
  39.     if(n % 2) //n impar y mayor que 2
  40.     {
  41.         fibo_t k1,k2;
  42.  
  43.         k1 = fibo((n + 1) / 2);
  44.         k2 = fibo((n - 1) / 2);
  45.  
  46.         return k1 * k1 + k2 * k2;
  47.     }
  48.  
  49.     //n par y mayor que 2
  50.     return fibo(n / 2) * (fibo((n / 2) + 1) + fibo((n / 2) - 1));
  51.     //si n == 2 fibo(n / 2) * fibo(n / 2 + 1) = fibo(1) * fibo(2)
  52.     //habria recursion infinita si no se pone n == 2 como caso base
  53. }
  54.  
  55. int main(int argc, char *argv[])
  56. {
  57.     fibo_t i,valor;
  58.     time_t ini;
  59.  
  60.     printf("Fibonacci clasico:\n");
  61.  
  62.     ini = time(NULL);
  63.  
  64.     for(i = MIN ; i < MAX ; i++)
  65.     {
  66.         llamadas_clasico = 0;
  67.         valor = fibo_clasico(i);
  68.  
  69.         printf("  fibo_clasico(%llu) = %llu (%llu llamadas)\n",i,valor,llamadas_clasico);
  70.     }
  71.  
  72.     printf("%llu segundos\n",time(NULL) - ini);
  73.  
  74.     printf("\nFibonacci optimizado:\n");
  75.  
  76.     ini = time(NULL);
  77.  
  78.     for(i = MIN ; i < MAX ; i++)
  79.     {
  80.         llamadas_optimizado = 0;
  81.         valor = fibo(i);
  82.  
  83.         printf("  fibo(%llu) = %llu (%llu llamadas)\n",i,valor,llamadas_optimizado);
  84.     }
  85.  
  86.     printf("%llu segundos\n",time(NULL) - ini);
  87.  
  88.     return 0;
  89. }

Ala, ahora los tiempos y las llamadas deberían ser parecidos :xD

Título: Re: Sucesion de Fibonacci recursiva optimizada
Publicado por: eferion en 20 Julio 2013, 23:53 pm
Si quieres darle una pequeña vuelta de tuerca más puedes usar los siguientes trucos:

mejor preincrementos a postincrementos:

Código
  1. // esto
  2. ++variable;
  3.  
  4. // es mas optimo que esto ( como norma general, ya que depende de las optimizaciones del compilador )
  5. variable++;[/code ]
  6.  
  7. Para dividir entre dos, es muuuucho más óptimo usar desplazamientos binarios:
  8.  
  9. [code=c]
  10. // esto
  11. variable = variable >> 1;
  12.  
  13. // es más óptimo que esto
  14. variable = variable / 2;

Esto lo podrías optimizar un pelin ( siendo quisquillosos )

Código
  1. // Con código redundante
  2. if(n == 0)
  3.     return 0;
  4. if(n == 1)
  5.     return 1;
  6. if(n == 2) //Evitamos recurion infinita si n == 2
  7.     return 1;
  8.  
  9. // Optimizado
  10. if(n == 0)
  11.     return 0;
  12. if(n <= 2) // Se evita una comprobacion en cada pasada
  13.     return 1;

Si reutilizas algún cálculo costoso, intenta precalcularlo

Código
  1. // Sin optimizar
  2. return fibo(n / 2) * (fibo((n / 2) + 1) + fibo((n / 2) - 1));
  3.  
  4. // Optimizado
  5. int temp = n / 2; // o mejor aun temp = n >> 1;
  6. return fibo( temp ) * ( fibo( temp + 1 ) + fibo( temp - 1 ) );

También creo recordar, no estoy 100% seguro, que para saber si un número es divisible entre 2 se puede optimizar también de la siguiente forma ( como no aprovechando desplazamientos binarios ):

Código
  1. // Sin optimizar
  2. if(n % 2) //n impar y mayor que 2
  3.  
  4. // optimizado
  5. if ( ( n >> 1 << 1 ) == n )

Esto último básicamente consiste en eliminar el bit de menor peso del número ... si es par, ese dígito es cero y el número permanece invariable.

Son truquillos tontos si quieres conseguir arañar hasta la última señal de reloj del procesador.

Eso si, te lo has currado, no voy a ser yo el que te quite el mérito.

Enhorabuena.[/code]

Título: Re: Sucesion de Fibonacci recursiva optimizada
Publicado por: 0xDani en 21 Julio 2013, 00:49 am
@eferion, había visto algún artículo sobre optimización de código hasta esos extremos en ensamblador, pero nunca se me había ocurrido hacerlo en C  :P Supongo que para echar el rato está bien xD

EDIT: Estos tíos sí que lo flipaban con la optimización: http://www.thehackademy.net/madchat/vxdevl/vxmags/ddt-1/DDT%231.2_G

Título: Re: Sucesion de Fibonacci recursiva optimizada
Publicado por: do-while en 21 Julio 2013, 08:35 am
Cita de: 0xDani en 21 Julio 2013, 00:49 am
EDIT: Estos tíos sí que lo flipaban con la optimización: http://www.thehackademy.net/madchat/vxdevl/vxmags/ddt-1/DDT%231.2_G

Aunque he leído muy poco, el texto parece entretenido. A ver que se cuentan.

Un amigo está haciendo un trabajo sobre como los compiladores de C (no se si se centra en gcc...) traducen a código máquina y, por lo que me dijo, hay diferencias entre variable++, ++variable,variable = variable + 1 y variable += 1. No se si todas las expresiones anteriores generan distinto código máquina o si alguna es equivalente a alguna de las otras... ¿Sabéis algo mas sobre esto?

¡Saludos!

Acabo de leerlo. No me parece demasiado interesante. Se centra sobre todo en reducir la cantidad de código máquina generado. No busca reducir el coste computacional del algoritmo. Si el código inicial tiene un orden O(n), el final tendrá el mismo, por lo que desde el punto de vista del algoritmo, no gana nada...

Título: Re: Sucesion de Fibonacci recursiva optimizada
Publicado por: amchacon en 21 Julio 2013, 11:00 am
Cita de: do-while en 21 Julio 2013, 08:35 am
Acabo de leerlo. No me parece demasiado interesante. Se centra sobre todo en reducir la cantidad de código máquina generado. No busca reducir el coste computacional del algoritmo. Si el código inicial tiene un orden O(n), el final tendrá el mismo, por lo que desde el punto de vista del algoritmo, no gana nada...
Todas las optimizaciones en ensamblador son lineales ;)

Cita de: do-while en 21 Julio 2013, 08:35 am
Un amigo está haciendo un trabajo sobre como los compiladores de C (no se si se centra en gcc...) traducen a código máquina y, por lo que me dijo, hay diferencias entre variable++, ++variable,variable = variable + 1 y variable += 1. No se si todas las expresiones anteriores generan distinto código máquina o si alguna es equivalente a alguna de las otras... ¿Sabéis algo mas sobre esto?
Hay una gran diferencia entre variable = variable +1  y usar los operadores de incremento. La primera expresión tienes que mover la variable en un registro, sumarle 1 y devolverlo a la memoria RAM.

La segunda expresión puede hacerse en una sola sentencia con una sentencia de esamblador (creo que era incr).

De todas formas, si activas las optimización del compilador, probablemente esto te lo haga automático.

Título: Re: Sucesion de Fibonacci recursiva optimizada
Publicado por: 0xDani en 21 Julio 2013, 16:56 pm
Cita de: do-while en 21 Julio 2013, 08:35 am
Acabo de leerlo. No me parece demasiado interesante. Se centra sobre todo en reducir la cantidad de código máquina generado. No busca reducir el coste computacional del algoritmo. Si el código inicial tiene un orden O(n), el final tendrá el mismo, por lo que desde el punto de vista del algoritmo, no gana nada...

Claro, yo me refería más bien al tipo de optimizaciones que señalaba @eferion. Y en cuanto a las dudas de los incrementos, en un compilador moderno no tiene importancia, porque van a optimizar el código.

Título: Re: Sucesion de Fibonacci recursiva optimizada
Publicado por: Shout en 21 Julio 2013, 18:29 pm
@eferion
Realmente no tiene sentido lo de num >> 1 para dividir entre 2.
Lo digo por esto:
(http://puu.sh/3Ic1o.png)
Son 1.000.000.000 iteraciones  :silbar: :silbar:

En este benchmark, ">>" ha tardado más, pero seguramente es porque tengo un montón de cosas abiertas, ya que antes no tenía abierto nada (ni siquiera VC++) y ">>" fue un poco más rápido (0.05 segundos), pero aún así creo que no vale la pena complicar el código (legibilidad) por 0.1 segundos. Recuerda, no son 1.000 ni 1.000.000 iteraciones, son ¡1.000.000.000!

Título: Re: Sucesion de Fibonacci recursiva optimizada
Publicado por: rir3760 en 21 Julio 2013, 19:17 pm
Cita de: eferion en 20 Julio 2013, 23:53 pm
Para dividir entre dos, es muuuucho más óptimo usar desplazamientos binarios:
Código
  1. // esto
  2. variable = variable >> 1;
  3.  
  4. // es más óptimo que esto
  5. variable = variable / 2;
En el desplazamiento si la variable es de un tipo entero con signo el valor del bit de relleno depende de la implementación, en otras palabras no esta garantizado que el resultado de ambas operaciones (división y desplazamiento) sea el mismo. Si es un tipo sin signo el bit de relleno siempre es cero, ahí no hay problema.

Cita de: eferion en 20 Julio 2013, 23:53 pm
También creo recordar, no estoy 100% seguro, que para saber si un número es divisible entre 2 se puede optimizar también de la siguiente forma ( como no aprovechando desplazamientos binarios ):

Código
  1. // Sin optimizar
  2. if(n % 2) //n impar y mayor que 2
  3.  
  4. // optimizado
  5. if ( ( n >> 1 << 1 ) == n )
Ya que los números pares (positivos) tienen el bit menos significativo a cero se puede reducir la expresión a "!(n & 1)". Y si invertimos la condición (verificar impares) terminamos utilizando un operador:
Código
  1. if (n & 1){
  2.    /* impares */
  3. }else {
  4.    /* pares */
  5. }

Pero como ya se comento es mejor dejar ciertas mejoras (por ejemplo división vs desplazamiento) al compilador.

Un saludo

Título: Re: Sucesion de Fibonacci recursiva optimizada
Publicado por: eferion en 22 Julio 2013, 07:13 am
Cita de: rir3760 en 21 Julio 2013, 19:17 pm
En el desplazamiento si la variable es de un tipo entero con signo el valor del bit de relleno depende de la implementación, en otras palabras no esta garantizado que el resultado de ambas operaciones (división y desplazamiento) sea el mismo

Tenía entendido que en el caso de los procesadores empleados en PCs... intel, amd, etc... si se da esa condición.

Título: Re: Sucesion de Fibonacci recursiva optimizada
Publicado por: do-while en 22 Julio 2013, 09:28 am
¡Buenas!


Había leido que de las operaciones "elementales" (+, -, * , / y %), las que mas le costaban al procesador eran / y %, la división, y efectivamente:
Código
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <time.h>
  4.  
  5. #define MAX 10000000000LLU
  6.  
  7. int main(int argc, char *argv[])
  8. {
  9.     unsigned long long i,x,y;
  10.     time_t ini;
  11.  
  12.     ini = time(NULL);
  13.  
  14.     for(i = 0 ; i < MAX ; i++)
  15.         if(i % 2);
  16.  
  17.     printf("%lu segundos\n", time(NULL) - ini);
  18.  
  19.     ini = time(NULL);
  20.  
  21.     for(i = 0 ; i < MAX ; i++)
  22.         if(i & 1);
  23.  
  24.     printf("%lu segundos\n", time(NULL) - ini);
  25.  
  26.     return 0;
  27. }
  28.  

Se nota la diferencia, pero para que sea considerable, he tenido que llegar a 10^10 iteraciones...

Aun así, se ve que es preferible comprobar el bit menos significativo en un código que requiera continuamente la comprobación de la paridad de un numero a utilizar el operador módulo.

¡Saludos!

Título: Re: Sucesion de Fibonacci recursiva optimizada
Publicado por: eferion en 22 Julio 2013, 10:08 am
Cita de: do-while en 22 Julio 2013, 09:28 am
Se nota la diferencia, pero para que sea considerable, he tenido que llegar a 10^10 iteraciones...

Está claro que, pese a ser más pesada, una operación de división está lo suficientemente optimizada ( al menos cuando se manejan números enteros ) como para no ser un lastre excesivo... salvo que estés en un entorno de tiempo real crítico.

Lo que sí está claro es que, sobretodo en el caso de bucles con un gran número de repeticiones, las pequeñas optimizaciones se van notando cada vez más... obviamente hacer una sustitución así en, por ejemplo, una función que se ejecuta una vez cada vez que un usuario hace click sobre un botón no es una mejora a la que el vayas a sacar partido realmente.

La siguiente mejora que podrías plantearte en este código es el que sea capaz de manejar números realmente grandes... de 100, 200 ... 1000 cifras.

Funciones matemáticas optimizadas y con opción a manejar números grandes... más sus optimizaciones para números enteros normales, sería una buena base para sacar una librería matemática interesante.

Título: Re: Sucesion de Fibonacci recursiva optimizada
Publicado por: amchacon en 22 Julio 2013, 10:43 am
Cita de: do-while en 22 Julio 2013, 09:28 am
Se nota la diferencia, pero para que sea considerable, he tenido que llegar a 10^10 iteraciones...
Tú código no es correcto para cualquier compilador actual, mi compilador directamente se salta los fors y los ifs porque los considera que son inútiles. La prueba está en que los fors no aparecen en el código ensamblador:

Código
  1. .file	"main.cpp"
  2. 	.def	__main;	.scl	2;	.type	32;	.endef
  3. 	.section .rdata,"dr"
  4. .LC0:
  5. 	.ascii "%lu segundos\12\0"
  6. 	.section	.text.startup,"x"
  7. 	.p2align 4,,15
  8. 	.globl	main
  9. 	.def	main;	.scl	2;	.type	32;	.endef
  10. 	.seh_proc	main
  11. main:
  12. .LFB49:
  13. 	pushq	%rsi
  14. 	.seh_pushreg	%rsi
  15. 	pushq	%rbx
  16. 	.seh_pushreg	%rbx
  17. 	subq	$40, %rsp
  18. 	.seh_stackalloc	40
  19. 	.seh_endprologue
  20. 	call	__main
  21. 	movq	__imp__time64(%rip), %rbx
  22. 	xorl	%ecx, %ecx
  23. 	call	*%rbx
  24. 	xorl	%ecx, %ecx
  25. 	movq	%rax, %rsi
  26. 	call	*%rbx
  27. 	leaq	.LC0(%rip), %rcx
  28. 	movq	%rax, %rdx
  29. 	subq	%rsi, %rdx
  30. 	call	printf
  31. 	xorl	%ecx, %ecx
  32. 	call	*%rbx
  33. 	xorl	%ecx, %ecx
  34. 	movq	%rax, %rsi
  35. 	call	*%rbx
  36. 	leaq	.LC0(%rip), %rcx
  37. 	movq	%rax, %rdx
  38. 	subq	%rsi, %rdx
  39. 	call	printf
  40. 	xorl	%eax, %eax
  41. 	addq	$40, %rsp
  42. 	popq	%rbx
  43. 	popq	%rsi
  44. 	ret
  45. 	.seh_endproc
  46. 	.ident	"GCC: (rev1, Built by MinGW-builds project) 4.8.1"
  47. 	.def	printf;	.scl	2;	.type	32;	.endef

Lo modifique tal que así:

Código
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <time.h>
  4.  
  5. #define MAX 5000000000LLU
  6.  
  7. int main(int argc, char *argv[])
  8. {
  9.     unsigned long long i;
  10.     unsigned int Contador = 0;
  11.     time_t ini;
  12.  
  13.     ini = time(NULL);
  14.  
  15.     for(i = 0 ; i < MAX ; i++)
  16.        Contador += i% 2;
  17.  
  18.     printf("%lu segundos\n", time(NULL) - ini);
  19.  
  20.     ini = time(NULL);
  21.  
  22.     for(i = 0 ; i < MAX ; i++)
  23.         Contador -= i&1;
  24.  
  25.     printf("%lu segundos\n", time(NULL) - ini);
  26.  
  27.      printf("%d",Contador);
  28.  
  29.     return 0;
  30. }

Ahora si que se nota que hace las operaciones, aunque haciendo pruebas. Me di cuenta que ambas operaciones dependían más del factor suerte que de otra cosa (a veces ganaba uno, otra veces ganaba otro y otras veces empataban). Analizando el código ASM:

Código
  1. 	.file	"main.cpp"
  2. 	.def	__main;	.scl	2;	.type	32;	.endef
  3. 	.section .rdata,"dr"
  4. .LC0:
  5. 	.ascii "%lu segundos\12\0"
  6. .LC1:
  7. 	.ascii "%d\0"
  8. 	.section	.text.startup,"x"
  9. 	.p2align 4,,15
  10. 	.globl	main
  11. 	.def	main;	.scl	2;	.type	32;	.endef
  12. 	.seh_proc	main
  13. main:
  14. .LFB49:
  15. 	pushq	%rdi
  16. 	.seh_pushreg	%rdi
  17. 	pushq	%rsi
  18. 	.seh_pushreg	%rsi
  19. 	pushq	%rbx
  20. 	.seh_pushreg	%rbx
  21. 	subq	$32, %rsp
  22. 	.seh_stackalloc	32
  23. 	.seh_endprologue
  24. 	xorl	%ebx, %ebx
  25. 	call	__main
  26. 	movq	__imp__time64(%rip), %rsi
  27. 	xorl	%ecx, %ecx
  28. 	call	*%rsi
  29. 	xorl	%edx, %edx
  30. 	movabsq	$5000000000, %r8
  31. 	movq	%rax, %rdi
  32. 	.p2align 4,,10
  33. .L3:
  34. 	movl	%edx, %ecx
  35. 	addq	$1, %rdx
  36. 	andl	$1, %ecx
  37. 	addl	%ecx, %ebx
  38. 	cmpq	%r8, %rdx
  39. 	jne	.L3
  40. 	xorl	%ecx, %ecx
  41. 	call	*%rsi
  42. 	leaq	.LC0(%rip), %rcx
  43. 	movq	%rax, %rdx
  44. 	subq	%rdi, %rdx
  45. 	call	printf
  46. 	xorl	%ecx, %ecx
  47. 	call	*%rsi
  48. 	xorl	%edx, %edx
  49. 	movabsq	$5000000000, %r8
  50. 	movq	%rax, %rdi
  51. 	.p2align 4,,10
  52. .L5:
  53. 	movl	%edx, %ecx
  54. 	addq	$1, %rdx
  55. 	andl	$1, %ecx
  56. 	subl	%ecx, %ebx
  57. 	cmpq	%r8, %rdx
  58. 	jne	.L5
  59. 	xorl	%ecx, %ecx
  60. 	call	*%rsi
  61. 	leaq	.LC0(%rip), %rcx
  62. 	movq	%rax, %rdx
  63. 	subq	%rdi, %rdx
  64. 	call	printf
  65. 	leaq	.LC1(%rip), %rcx
  66. 	movl	%ebx, %edx
  67. 	call	printf
  68. 	xorl	%eax, %eax
  69. 	addq	$32, %rsp
  70. 	popq	%rbx
  71. 	popq	%rsi
  72. 	popq	%rdi
  73. 	ret
  74. 	.seh_endproc
  75. 	.ident	"GCC: (rev1, Built by MinGW-builds project) 4.8.1"
  76. 	.def	printf;	.scl	2;	.type	32;	.endef

Podemos identificar los dos fors aquí:

Código
  1. .L3:
  2. 	movl	%edx, %ecx
  3. 	addq	$1, %rdx
  4. 	andl	$1, %ecx
  5. 	addl	%ecx, %ebx
  6. 	cmpq	%r8, %rdx
  7. 	jne	.L3
Código
  1. .L5:
  2. 	movl	%edx, %ecx
  3. 	addq	$1, %rdx
  4. 	andl	$1, %ecx
  5. 	subl	%ecx, %ebx
  6. 	cmpq	%r8, %rdx
  7. 	jne	.L5

Fijate que el compilador lo ha optimizado haciendo las mismas operaciones en los dos casos. Es curioso que incluso desactivando la optimización del compilador, tenemos las mismas operaciones en el for:

Código
  1. 	.file	"main.cpp"
  2. 	.def	__main;	.scl	2;	.type	32;	.endef
  3. 	.section .rdata,"dr"
  4. .LC0:
  5. 	.ascii "%lu segundos\12\0"
  6. .LC1:
  7. 	.ascii "%d\0"
  8. 	.text
  9. 	.globl	main
  10. 	.def	main;	.scl	2;	.type	32;	.endef
  11. 	.seh_proc	main
  12. main:
  13. .LFB36:
  14. 	pushq	%rbp
  15. 	.seh_pushreg	%rbp
  16. 	movq	%rsp, %rbp
  17. 	.seh_setframe	%rbp, 0
  18. 	subq	$64, %rsp
  19. 	.seh_stackalloc	64
  20. 	.seh_endprologue
  21. 	movl	%ecx, 16(%rbp)
  22. 	movq	%rdx, 24(%rbp)
  23. 	call	__main
  24. 	movl	$0, -12(%rbp)
  25. 	movl	$0, %ecx
  26. 	call	time
  27. 	movq	%rax, -24(%rbp)
  28. 	movq	$0, -8(%rbp)
  29. 	jmp	.L2
  30. .L3:
  31. 	movq	-8(%rbp), %rax
  32. 	andl	$1, %eax
  33. 	addl	%eax, -12(%rbp)
  34. 	addq	$1, -8(%rbp)
  35. .L2:
  36. 	movabsq	$4999999999, %rax
  37. 	cmpq	%rax, -8(%rbp)
  38. 	jbe	.L3
  39. 	movl	$0, %ecx
  40. 	call	time
  41. 	subq	-24(%rbp), %rax
  42. 	movq	%rax, %rdx
  43. 	leaq	.LC0(%rip), %rcx
  44. 	call	printf
  45. 	movl	$0, %ecx
  46. 	call	time
  47. 	movq	%rax, -24(%rbp)
  48. 	movq	$0, -8(%rbp)
  49. 	jmp	.L4
  50. .L5:
  51. 	movq	-8(%rbp), %rax
  52. 	andl	$1, %eax
  53. 	subl	%eax, -12(%rbp)
  54. 	addq	$1, -8(%rbp)
  55. .L4:
  56. 	movabsq	$4999999999, %rax
  57. 	cmpq	%rax, -8(%rbp)
  58. 	jbe	.L5
  59. 	movl	$0, %ecx
  60. 	call	time
  61. 	subq	-24(%rbp), %rax
  62. 	movq	%rax, %rdx
  63. 	leaq	.LC0(%rip), %rcx
  64. 	call	printf
  65. 	movl	-12(%rbp), %eax
  66. 	movl	%eax, %edx
  67. 	leaq	.LC1(%rip), %rcx
  68. 	call	printf
  69. 	movl	$0, %eax
  70. 	addq	$64, %rsp
  71. 	popq	%rbp
  72. 	ret
  73. 	.seh_endproc
  74. 	.ident	"GCC: (rev1, Built by MinGW-builds project) 4.8.1"
  75. 	.def	time;	.scl	2;	.type	32;	.endef
  76. 	.def	printf;	.scl	2;	.type	32;	.endef

Código
  1. 	jmp	.L2
  2. .L3:
  3. 	movq	-8(%rbp), %rax
  4. 	andl	$1, %eax
  5. 	addl	%eax, -12(%rbp)
  6. 	addq	$1, -8(%rbp)
  7. .L2:
  8. 	movabsq	$4999999999, %rax
  9. 	cmpq	%rax, -8(%rbp)
  10. 	jbe	.L3
Código
  1. 	jmp	.L4
  2. .L5:
  3. 	movq	-8(%rbp), %rax
  4. 	andl	$1, %eax
  5. 	subl	%eax, -12(%rbp)
  6. 	addq	$1, -8(%rbp)
  7. .L4:
  8. 	movabsq	$4999999999, %rax
  9. 	cmpq	%rax, -8(%rbp)
  10. 	jbe	.L5

Ergo, no. No hay diferencia entre % y & en un compilador actual.

Título: Re: Sucesion de Fibonacci recursiva optimizada
Publicado por: eferion en 22 Julio 2013, 11:00 am
La pregunta entonces es... ¿ Es aplicable ese resultado a cualquier compilador ?

Creo que habría entonces que hacer una batería de pruebas con diferentes compiladores, porque no creo que todos implementen las mismas optimizaciones...

Eso si... te lo has currado mirándote el código en ensamblador

Título: Re: Sucesion de Fibonacci recursiva optimizada
Publicado por: do-while en 26 Julio 2013, 10:30 am
amchacon, eres un tramposo...  :xD

Deja que los niños jueguen en igualdad de condiciones, que sino se sienten discriminados...  ;D

Código
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <time.h>
  4.  
  5. #define MIN 37
  6. #define MAX 42
  7.  
  8. typedef unsigned long long fibo_t;
  9.  
  10. unsigned long long llamadas_clasico;
  11. unsigned long long llamadas_optimizado;
  12.  
  13. #define MAX_CACHE 33
  14.  
  15. unsigned long long Fibonaci_Cache[MAX_CACHE] = {1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597
  16. ,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269,2178309,31524578};
  17.  
  18. fibo_t fibo_clasico(fibo_t n)
  19. {
  20.     llamadas_clasico++;
  21.  
  22.     if(n < MAX_CACHE)
  23.         return Fibonaci_Cache[n];
  24.  
  25.     return fibo_clasico(n - 1) + fibo_clasico(n - 2);
  26. }
  27.  
  28. fibo_t fibo(fibo_t n)
  29. {
  30.     llamadas_optimizado++;
  31.  
  32.     if(n < MAX_CACHE)
  33.         return Fibonaci_Cache[n];
  34.  
  35.     if(n % 2) //n impar y mayor que 2
  36.     {
  37.         fibo_t k1,k2;
  38.  
  39.         k1 = fibo((n + 1) / 2);
  40.         k2 = fibo((n - 1) / 2);
  41.  
  42.         return k1 * k1 + k2 * k2;
  43.     }
  44.  
  45.     //n par y mayor que 2
  46.     return fibo(n / 2) * (fibo((n / 2) + 1) + fibo((n / 2) - 1));
  47.     //si n == 2 fibo(n / 2) * fibo(n / 2 + 1) = fibo(1) * fibo(2)
  48.     //habria recursion infinita si no se pone n == 2 como caso base
  49. }
  50.  
  51. int main(int argc, char *argv[])
  52. {
  53.     fibo_t i,valor;
  54.     time_t ini;
  55.  
  56.     printf("Fibonacci clasico:\n");
  57.  
  58.     ini = time(NULL);
  59.  
  60.     for(i = MIN ; i < MAX ; i++)
  61.     {
  62.         llamadas_clasico = 0;
  63.         valor = fibo_clasico(i);
  64.  
  65.         printf("  fibo_clasico(%llu) = %llu (%llu llamadas)\n",i,valor,llamadas_clasico);
  66.     }
  67.  
  68.     printf("%llu segundos\n",time(NULL) - ini);
  69.  
  70.     printf("\nFibonacci optimizado:\n");
  71.  
  72.     ini = time(NULL);
  73.  
  74.     for(i = MIN ; i < MAX ; i++)
  75.     {
  76.         llamadas_optimizado = 0;
  77.         valor = fibo(i);
  78.  
  79.         printf("  fibo(%llu) = %llu (%llu llamadas)\n",i,valor,llamadas_optimizado);
  80.     }
  81.  
  82.     printf("%llu segundos\n",time(NULL) - ini);
  83.  
  84.     return 0;
  85. }
  86.  

¡Saludos!

Por cierto, ¿cómo has conseguido el código en ensamblador? Supongo que será alguna opción del compilador, pero nunca me he metido mucho a jugar con el, así que no se que opción has utilizado...

¡Saludos!

Título: Re: Sucesion de Fibonacci recursiva optimizada
Publicado por: amchacon en 26 Julio 2013, 10:49 am
Cita de: eferion en 22 Julio 2013, 11:00 am
La pregunta entonces es... ¿ Es aplicable ese resultado a cualquier compilador ?

Creo que habría entonces que hacer una batería de pruebas con diferentes compiladores, porque no creo que todos implementen las mismas optimizaciones...
Seguramente las implementaciones varien de un compilador a otro, pero lo normal esque hagan estas optimizaciones automáticamente, si no esque estás usando un compilador-patata.

Cita de: do-while en 26 Julio 2013, 10:30 am
amchacon, eres un tramposo...  :xD

Deja que los niños jueguen en igualdad de condiciones, que sino se sienten discriminados...  ;D
En las sucesiones lineales se pueden hacer muchas trampas  :xD

Seguramente en los juegos lo implementarán así, para ganar rendimiento.

Cita de: do-while en 26 Julio 2013, 10:30 am
Por cierto, ¿cómo has conseguido el código en ensamblador? Supongo que será alguna opción del compilador, pero nunca me he metido mucho a jugar con el, así que no se que opción has utilizado...
Hay que pasarle el flag -S al compilador.

Si usas un IDE como Codeblocks, se puede hacer la siguiente chapuzilla:

- Crea un proyecto de consola, pon el código y vete a Project -> build options -> other options. Escribir -S

Dale a reconstruir todo (control+F11). Al final dará un error (porque intentará linkar y verá que no puede  ;D). Vete a la carpeta obj de tu proyecto y abre el archivo con el notepad.

Título: Re: Sucesion de Fibonacci recursiva optimizada
Publicado por: do-while en 26 Julio 2013, 11:43 am
¡Buenas!

Me acabo de dar cuenta de que el último valor del vector está mal. Se te ha colado un 1 entre el 3 y el 5. Te aviso por si vas a utilizar el código para otros programas, no vaya a ser que no te salgan los cálculos y te vuelvas loco buscando el origen de todo mal (a mi me ha pasado  ;D) Aquí te dejo el vector correcto.

Código
  1. unsigned long long Fibonaci_Cache[MAX_CACHE] = {0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597
  2. ,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269,2178309,3524578};
  3.  

¡Saludos!

Título: Re: Sucesion de Fibonacci recursiva optimizada
Publicado por: eferion en 29 Julio 2013, 13:47 pm
Cita de: amchacon en 26 Julio 2013, 10:49 am
Seguramente las implementaciones varien de un compilador a otro, pero lo normal esque hagan estas optimizaciones automáticamente, si no esque estás usando un compilador-patata.

Yo solo me refería la hecho de que las optimizaciones comentadas fuesen equivalentes al menos en los compiladores más utilizados... ya que si alguno de éstos no es capaz de optimizar alguna de las posibilidades propuestas tal vez habría que optar por la opción B.

En cuanto a las optimizaciones automáticas... variarán en función de cómo configures la compilación... compilar con debug = 0 optimizaciones y de ahí hasta lo que te ofrezca el propio compilador... luego también puedes añadir flags para que las optimizaciones vayan en pro de la velocidad o en pro del consumo de memoria...

En fin, que yo creo que es malo generalizar en este tema.


Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines