Fibonacci numbers have a lot of applications. There have been a lot of interesting researches regarding Fibonacci numbers since 800 years ago. Mathematically they are the numbers from a sequence, which is defined as 
.
Experiment and Result
Fibonacci numbers can be derived from either the original definition that is a typical example of recursion, or a mathematically simplified form that is called closed-from expression. In SAS, a user-defined
Fib1 function in PROC FCMP can realize the recursion expression, and another Fib2 function is created to express the closed-form expression. I insert both functions to a loop from 10 to 40 with step size of 5 and record the real time costed. According to the figure above, both algorithms have no actually difference while N is relative small. When N becomes 30 or bigger, the recursion expression function spends a lot of system time. When N is even greater than 40, SAS enters a freezing status and I have to break from the command manually. Thus, the curve for the recursion expression seems to fit an exponential relationship fairly well. On the contrary, the algorithm of closed-from expression takes almost constant time for the execution,
Complexity
Recursion expression
, which may imply
.
Closed-form expression
The equation is fairly straightforward and described as. Here
is the well-known golden ratio. Its complexity is a constant, which suggests
.
Conclusion
Mathematics sometimes significantly decreases the complexity of the computation, in this case, from )
to )
. It is also useful for us to estimate how much resources are needed for specific purpose.
****(1) Bulid user-defined functions *****************;
proc fcmp outlib = work.test.fibonacci;
* Create the 1st function based on recursion;
function fib1(n);
if n<0 then return(0);
else if n = 1 or n = 2 then return(1);
else return(fib1(n-1) + fib1(n-2));
endsub;
* Create the 2nd function based on closed form;
function fib2(n);
phi = (1 + sqrt(5))/2;
return(round((phi**n - (1-phi)**n) / sqrt(5)));
endsub;
quit;
****(2) Run the tests sequentially********************;
options cmplib = work.test fullstimer;
%macro test();
* Create datasets for verification
%do j = 10 %to 40 %by 5;
data _fib1_&j;
do i = 1 to &j;
x = fib1(i);
output;
end;
%put Recursion method at &j;
run;
data _fib2_&j;
do i = 1 to &j;
x = fib2(i);
output;
end;
%put Closed form method at &j;
run;
%end;
%mend;
* Output SAS log to text file;
proc printto log = "c:\tmp\test.log" new;
run;
%test()
proc printto;
run;
****(3) Display the results***************************;
proc datasets nolist;
delete _:;
quit;
data one;
infile "c:\tmp\test.log" truncover;
input @1 line $80.;
if index(line, 'real') > 0;
run;
data two;
set one;
length method $20.;
retain number 5;
* Ignore the time used by PROC PRINTTO;
if _n_ > 1;
if mod(_n_ , 2) = 0 then do;
method = "Recursion";
number + 5;
end;
else method = "Closed form";
time = input(substr(line, 21, 5), 5.2);
run;
proc sgplot data = two;
series x = number y = time / group = method;
yaxis label = "Time elapsed by seconds" grid;
run;
