斐波那契数计算时间

本文介绍了斐波那契数计算时间的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

有没有递归式的斐波那契数间与循环式的斐波那契数明显计算时间差？我一直使用递归运行斐波那契40的地方，然后用一个循环之后直接。它好像计算时间差只有的学术的

的用C 的

递归解决方案：

INT主（INT ARGC，为const char * argv的[]）{    INT N，I = 0，C;    的printf（请输入一个整数：\\ n）;    scanf函数（％d个，＆安培; N）;    为（C = 1; C＆LT; = N，C ++）    {        的printf（％吕氏春秋，斐波纳契（i）段）;        我++;    }    返回0;    }长期斐波纳契（N久）{    如果（N == 0）        返回0;    否则，如果（N == 1）        返回1;    其他        返回（斐波纳契（N-1）+斐波纳契（N-2））;};

有关循环解决方案：

INT主（INT ARGC，为const char * argv的[]）{INT N，首先= 0，第二= 1，接下来，C;    的printf（请输入一个整数：\\ n）;    scanf函数（％d个，＆安培; N）;    为（C = 0; C＆LT; N，C ++）    {        如果（℃下= 1）            接下来= C;        其他        {            接下来=第一+第二;            第一=第二;            第二=下一个;        }        的printf（％D，下一个）;    }    返回0;};

解决方案

传统的递归方法相比，尾递归迭代版本非常慢。在下面的迭代版本，例如code采用了折叠循环使用达夫设备进入循环。对于32位无符号整数，限制是FIB（47），64位无符号整数，限制是FIB（93）。

时机与Intel 2600K 3.4GHz的，XP X64，64位模式下完成。 XP或XP X64高性能计数器频率相同的CPU时钟，3.4GHz的，但操作系统的开销（如中断），影响时间如果持续时间是很小的。

有关FIB计时（40）：

微秒485468.8 FIBR的（）＃0.2微秒的FIBT（）＃0.2微秒的FIBI（）＃

时序94循环，n = 0至93：微秒7

FIBT（）＃5微秒的FIBI（）＃

举例code：

的typedef无符号长长UI64;UI64 FIBR（UI64 N）{    如果（正2）        返回N;    返回FIBR（N-1）+ FIBR（N-2）;}//与FIBT致电（N，0,1）UI64 FIBT（UI64 N，UI64资源，UI64下一个）{    如果（N == 0）        返回水库;    返回FIBT（N - 1，接下来，RES +下一个）;}UI64 FIBI（UI64 N）{UI64 F0，F1，我;    如果（正2）        返回N;    N - = 2;    F1 = F0 = 1;    I = 0;    开关（N％8）{        做{            F1 + = F0;          案例7：            F0 + = F1;          情况6：            F1 + = F0;          情况5：            F0 + = F1;          情况4：            F1 + = F0;          案例3：            F0 + = F1;          案例2：            F1 + = F0;          情况1：            F0 + = F1;          情况下0：            继续;        }而（N＆GT; =（I + = 8））;    }    返回F0;}

FIBI（）的替代版本，而不在n 2检查。什么F0和F1重新设计的F0最后一笔落得内环路present变化，那么什么F0和F1的初始状态重新present取决于当n为偶数或奇数。如果n是偶数，F0 = FIB（0）= 0中，f1 = FIB（-1）= 1，如果n是奇数，F1 = FIB（0）= 0中，f0 = FIB（-1）= 1。 （如果你很好奇，FIB（-1）= 1，FIB（-2）= - 1，FIB（-3）= 2，FIB（-4）= -3，FIB（-5）= 5， FIB（-6）= -8，...）。

要在这里解释逻辑，对于n为偶数的情况下，FIB（-1）= F1 = 1，FIB（0）= F0 = 0，那么谎（1）=（F1 + = F0），FIB（2 ）=（F0 + = F1），FIB（3）=（F1 + = F0），FIB（4）=（F0 + = F1），...。

UI64 FIBI（UI64 N）{UI64 F0，F1，我;    F0 = N＆安培; 1; //如果n为偶数，F0 = 0，F1 = 1    F1 = 1 - F0; //否则F1 = 0，F0 = 1    I = 0;    开关（N％8）{        做{            F1 + = F0;          案例7：            F0 + = F1;          情况6：            F1 + = F0;          情况5：            F0 + = F1;          情况4：            F1 + = F0;          案例3：            F0 + = F1;          案例2：            F1 + = F0;          情况1：            F0 + = F1;          情况下0：            继续;        }而（N＆GT; =（I + = 8））;    }    返回F0;}

Is there a noticeable computation time difference between recursion-style Fibonacci vs. loop-style Fibonacci? I keep running Fibonacci to 40 places using recursion and then using a loop directly afterwards. It seems as though the computation time difference is only academic.

Written in C

Recursive solution:

int main(int argc, const char * argv[]) { int n, i = 0, c; printf("Please enter an integer:\n"); scanf("%d", &n); for ( c = 1 ; c <= n ; c++ ) { printf("%lu ", fibonacci(i)); i++; } return 0; } long fibonacci(long n) { if ( n == 0 ) return 0; else if ( n == 1 ) return 1; else return ( fibonacci(n-1) + fibonacci(n-2) ); };

For-loop solution:

int main(int argc, const char * argv[]) { int n, first = 0, second = 1, next, c; printf("Please enter an integer:\n"); scanf("%d", &n); for ( c = 0 ; c < n ; c++ ) { if ( c <= 1 ) next = c; else { next = first + second; first = second; second = next; } printf("%d ",next); } return 0; };

解决方案

The conventional recursion method is extremely slow compared to the tail recursive and iterative versions. In the example code below for the iteration version uses an unfolded loop along with Duff's Device to enter the loop. For 32 bit unsigned integers, the limit is fib(47), for 64 bit unsigned integers, the limit is fib(93).

Timing was done with Intel 2600K 3.4ghz, XP X64, 64 bit mode. XP or XP X64 high performance counter frequency is the same as the cpu clock, 3.4ghz, but operating system overhead (like interrupts), affects the timing if the duration is small.

Timings for fib(40):

fibr() # of microseconds 485468.8 fibt() # of microseconds 0.2 fibi() # of microseconds 0.2

Timing for 94 loops, n = 0 to 93:

fibt() # of microseconds 7 fibi() # of microseconds 5

Example code:

typedef unsigned long long UI64; UI64 fibr(UI64 n) { if(n < 2) return n; return fibr(n-1) + fibr(n-2); } // call with fibt(n, 0, 1) UI64 fibt(UI64 n, UI64 res, UI64 next) { if (n == 0) return res; return fibt(n - 1, next, res + next); } UI64 fibi(UI64 n) { UI64 f0, f1, i; if(n < 2) return n; n -= 2; f1 = f0 = 1; i = 0; switch(n%8){ do{ f1 += f0; case 7: f0 += f1; case 6: f1 += f0; case 5: f0 += f1; case 4: f1 += f0; case 3: f0 += f1; case 2: f1 += f0; case 1: f0 += f1; case 0: continue; }while(n >= (i += 8)); } return f0; }

Alternate version of fibi(), without the n<2 check. What f0 and f1 represent changes within the loop designed to end up with the final sum in f0, so the initial state of what f0 and f1 represent depends if n is even or odd. If n is even, f0 = fib(0) = 0, f1 = fib(-1) = 1, if n is odd, f1 = fib(0) = 0, f0 = fib(-1) = 1 . (In case you're curious, fib(-1) = 1, fib(-2) = -1, fib(-3) = 2, fib(-4) = -3, fib(-5) = 5, fib(-6) = -8, ... ).

To explain the logic here, for the n even case, fib(-1) = f1 = 1, fib(0) = f0 = 0, then fib(1) = (f1 += f0), fib(2) = (f0 += f1), fib(3) = (f1 += f0), fib(4) = (f0 += f1), ... .

UI64 fibi(UI64 n) { UI64 f0, f1, i; f0 = n & 1; // if n even, f0=0, f1=1 f1 = 1 - f0; // else f1=0, f0=1 i = 0; switch(n%8){ do{ f1 += f0; case 7: f0 += f1; case 6: f1 += f0; case 5: f0 += f1; case 4: f1 += f0; case 3: f0 += f1; case 2: f1 += f0; case 1: f0 += f1; case 0: continue; }while(n >= (i += 8)); } return f0; }