Autor
|
Tema: Sucesion de Fibonacci recursiva optimizada (Leído 12,437 veces)
|
eferion
Desconectado
Mensajes: 1.248
|
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.
|
|
|
En línea
|
|
|
|
do-while
Desconectado
Mensajes: 1.276
¿Habra que sacarla de paseo?
|
¡Buenas! Había leido que de las operaciones "elementales" (+, -, * , / y %), las que mas le costaban al procesador eran / y %, la división, y efectivamente: #include <stdio.h> #include <stdlib.h> #include <time.h> #define MAX 10000000000LLU int main(int argc, char *argv[]) { unsigned long long i,x,y; time_t ini; for(i = 0 ; i < MAX ; i++) if(i % 2); for(i = 0 ; i < MAX ; i++) if(i & 1); return 0; }
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!
|
|
|
En línea
|
- Doctor, confundo los números y los colores. - Vaya marrón. - ¿Marrón? ¡Por el culo te la hinco!
|
|
|
eferion
Desconectado
Mensajes: 1.248
|
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.
|
|
|
En línea
|
|
|
|
amchacon
Desconectado
Mensajes: 1.211
|
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: .file "main.cpp" .def __main; .scl 2; .type 32; .endef .section .rdata,"dr" .LC0: .ascii "%lu segundos\12\0" .section .text.startup,"x" .p2align 4,,15 .globl main .def main; .scl 2; .type 32; .endef .seh_proc main main: .LFB49: pushq %rsi .seh_pushreg %rsi pushq %rbx .seh_pushreg %rbx subq $40, %rsp .seh_stackalloc 40 .seh_endprologue call __main movq __imp__time64(%rip), %rbx xorl %ecx, %ecx call *%rbx xorl %ecx, %ecx movq %rax, %rsi call *%rbx leaq .LC0(%rip), %rcx movq %rax, %rdx subq %rsi, %rdx call printf xorl %ecx, %ecx call *%rbx xorl %ecx, %ecx movq %rax, %rsi call *%rbx leaq .LC0(%rip), %rcx movq %rax, %rdx subq %rsi, %rdx call printf xorl %eax, %eax addq $40, %rsp popq %rbx popq %rsi ret .seh_endproc .ident "GCC: (rev1, Built by MinGW-builds project) 4.8.1" .def printf; .scl 2; .type 32; .endef
Lo modifique tal que así: #include <stdio.h> #include <stdlib.h> #include <time.h> #define MAX 5000000000LLU int main(int argc, char *argv[]) { unsigned long long i; unsigned int Contador = 0; time_t ini; ini = time(NULL); for(i = 0 ; i < MAX ; i++) Contador += i% 2; printf("%lu segundos\n", time(NULL) - ini); ini = time(NULL); for(i = 0 ; i < MAX ; i++) Contador -= i&1; printf("%lu segundos\n", time(NULL) - ini); printf("%d",Contador); return 0; }
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: .file "main.cpp" .def __main; .scl 2; .type 32; .endef .section .rdata,"dr" .LC0: .ascii "%lu segundos\12\0" .LC1: .ascii "%d\0" .section .text.startup,"x" .p2align 4,,15 .globl main .def main; .scl 2; .type 32; .endef .seh_proc main main: .LFB49: pushq %rdi .seh_pushreg %rdi pushq %rsi .seh_pushreg %rsi pushq %rbx .seh_pushreg %rbx subq $32, %rsp .seh_stackalloc 32 .seh_endprologue xorl %ebx, %ebx call __main movq __imp__time64(%rip), %rsi xorl %ecx, %ecx call *%rsi xorl %edx, %edx movabsq $5000000000, %r8 movq %rax, %rdi .p2align 4,,10 .L3: movl %edx, %ecx addq $1, %rdx andl $1, %ecx addl %ecx, %ebx cmpq %r8, %rdx jne .L3 xorl %ecx, %ecx call *%rsi leaq .LC0(%rip), %rcx movq %rax, %rdx subq %rdi, %rdx call printf xorl %ecx, %ecx call *%rsi xorl %edx, %edx movabsq $5000000000, %r8 movq %rax, %rdi .p2align 4,,10 .L5: movl %edx, %ecx addq $1, %rdx andl $1, %ecx subl %ecx, %ebx cmpq %r8, %rdx jne .L5 xorl %ecx, %ecx call *%rsi leaq .LC0(%rip), %rcx movq %rax, %rdx subq %rdi, %rdx call printf leaq .LC1(%rip), %rcx movl %ebx, %edx call printf xorl %eax, %eax addq $32, %rsp popq %rbx popq %rsi popq %rdi ret .seh_endproc .ident "GCC: (rev1, Built by MinGW-builds project) 4.8.1" .def printf; .scl 2; .type 32; .endef
Podemos identificar los dos fors aquí: .L3: movl %edx, %ecx addq $1, %rdx andl $1, %ecx addl %ecx, %ebx cmpq %r8, %rdx jne .L3
.L5: movl %edx, %ecx addq $1, %rdx andl $1, %ecx subl %ecx, %ebx cmpq %r8, %rdx 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: .file "main.cpp" .def __main; .scl 2; .type 32; .endef .section .rdata,"dr" .LC0: .ascii "%lu segundos\12\0" .LC1: .ascii "%d\0" .text .globl main .def main; .scl 2; .type 32; .endef .seh_proc main main: .LFB36: pushq %rbp .seh_pushreg %rbp movq %rsp, %rbp .seh_setframe %rbp, 0 subq $64, %rsp .seh_stackalloc 64 .seh_endprologue movl %ecx, 16(%rbp) movq %rdx, 24(%rbp) call __main movl $0, -12(%rbp) movl $0, %ecx call time movq %rax, -24(%rbp) movq $0, -8(%rbp) jmp .L2 .L3: movq -8(%rbp), %rax andl $1, %eax addl %eax, -12(%rbp) addq $1, -8(%rbp) .L2: movabsq $4999999999, %rax cmpq %rax, -8(%rbp) jbe .L3 movl $0, %ecx call time subq -24(%rbp), %rax movq %rax, %rdx leaq .LC0(%rip), %rcx call printf movl $0, %ecx call time movq %rax, -24(%rbp) movq $0, -8(%rbp) jmp .L4 .L5: movq -8(%rbp), %rax andl $1, %eax subl %eax, -12(%rbp) addq $1, -8(%rbp) .L4: movabsq $4999999999, %rax cmpq %rax, -8(%rbp) jbe .L5 movl $0, %ecx call time subq -24(%rbp), %rax movq %rax, %rdx leaq .LC0(%rip), %rcx call printf movl -12(%rbp), %eax movl %eax, %edx leaq .LC1(%rip), %rcx call printf movl $0, %eax addq $64, %rsp popq %rbp ret .seh_endproc .ident "GCC: (rev1, Built by MinGW-builds project) 4.8.1" .def time; .scl 2; .type 32; .endef .def printf; .scl 2; .type 32; .endef
jmp .L2 .L3: movq -8(%rbp), %rax andl $1, %eax addl %eax, -12(%rbp) addq $1, -8(%rbp) .L2: movabsq $4999999999, %rax cmpq %rax, -8(%rbp) jbe .L3
jmp .L4 .L5: movq -8(%rbp), %rax andl $1, %eax subl %eax, -12(%rbp) addq $1, -8(%rbp) .L4: movabsq $4999999999, %rax cmpq %rax, -8(%rbp) jbe .L5
Ergo, no. No hay diferencia entre % y & en un compilador actual.
|
|
|
En línea
|
|
|
|
eferion
Desconectado
Mensajes: 1.248
|
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
|
|
|
En línea
|
|
|
|
do-while
Desconectado
Mensajes: 1.276
¿Habra que sacarla de paseo?
|
amchacon, eres un tramposo... Deja que los niños jueguen en igualdad de condiciones, que sino se sienten discriminados... #include <stdio.h> #include <stdlib.h> #include <time.h> #define MIN 37 #define MAX 42 typedef unsigned long long fibo_t; unsigned long long llamadas_clasico; unsigned long long llamadas_optimizado; #define MAX_CACHE 33 unsigned long long Fibonaci_Cache[MAX_CACHE] = {1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597 ,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269,2178309,31524578}; fibo_t fibo_clasico(fibo_t n) { llamadas_clasico++; if(n < MAX_CACHE) return Fibonaci_Cache[n]; return fibo_clasico(n - 1) + fibo_clasico(n - 2); } fibo_t fibo(fibo_t n) { llamadas_optimizado++; if(n < MAX_CACHE) return Fibonaci_Cache[n]; if(n % 2) //n impar y mayor que 2 { fibo_t k1,k2; k1 = fibo((n + 1) / 2); k2 = fibo((n - 1) / 2); return k1 * k1 + k2 * k2; } //n par y mayor que 2 return fibo(n / 2) * (fibo((n / 2) + 1) + fibo((n / 2) - 1)); //si n == 2 fibo(n / 2) * fibo(n / 2 + 1) = fibo(1) * fibo(2) //habria recursion infinita si no se pone n == 2 como caso base } int main(int argc, char *argv[]) { fibo_t i,valor; time_t ini; printf("Fibonacci clasico:\n"); for(i = MIN ; i < MAX ; i++) { llamadas_clasico = 0; valor = fibo_clasico(i); printf(" fibo_clasico(%llu) = %llu (%llu llamadas)\n",i ,valor ,llamadas_clasico ); } printf("\nFibonacci optimizado:\n"); for(i = MIN ; i < MAX ; i++) { llamadas_optimizado = 0; valor = fibo(i); printf(" fibo(%llu) = %llu (%llu llamadas)\n",i ,valor ,llamadas_optimizado ); } return 0; }
¡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!
|
|
« Última modificación: 26 Julio 2013, 10:32 am por do-while »
|
En línea
|
- Doctor, confundo los números y los colores. - Vaya marrón. - ¿Marrón? ¡Por el culo te la hinco!
|
|
|
amchacon
Desconectado
Mensajes: 1.211
|
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. amchacon, eres un tramposo... Deja que los niños jueguen en igualdad de condiciones, que sino se sienten discriminados... En las sucesiones lineales se pueden hacer muchas trampas Seguramente en los juegos lo implementarán así, para ganar rendimiento. 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 ). Vete a la carpeta obj de tu proyecto y abre el archivo con el notepad.
|
|
« Última modificación: 26 Julio 2013, 10:51 am por amchacon »
|
En línea
|
|
|
|
do-while
Desconectado
Mensajes: 1.276
¿Habra que sacarla de paseo?
|
¡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 ) Aquí te dejo el vector correcto. 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 ,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269,2178309,3524578};
¡Saludos!
|
|
|
En línea
|
- Doctor, confundo los números y los colores. - Vaya marrón. - ¿Marrón? ¡Por el culo te la hinco!
|
|
|
eferion
Desconectado
Mensajes: 1.248
|
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.
|
|
|
En línea
|
|
|
|
|
Mensajes similares |
|
Asunto |
Iniciado por |
Respuestas |
Vistas |
Último mensaje |
|
|
Sucesión Fibonacci [Batch]
« 1 2 »
Scripting
|
leogtz
|
17
|
15,220
|
15 Junio 2009, 17:26 pm
por leogtz
|
|
|
[Código-Ruby]Sucesión Fibonacci - JaAViEr
Scripting
|
0x5d
|
0
|
2,748
|
8 Enero 2012, 08:57 am
por 0x5d
|
|
|
Duda en el código (porgrama sucesión de Fibonacci)
Programación C/C++
|
b_rabbit10
|
2
|
2,611
|
18 Febrero 2013, 22:15 pm
por b_rabbit10
|
|
|
[Perl] Ejemplo de Sucesion Fibonacci
Scripting
|
BigBear
|
0
|
2,647
|
5 Diciembre 2014, 15:04 pm
por BigBear
|
|
|
Cómo conseguir una red inalámbrica optimizada
Noticias
|
wolfbcn
|
0
|
1,098
|
27 Octubre 2016, 14:53 pm
por wolfbcn
|
|