and Revisiting Fibonacci Festival from 2006
I originally wrote about Fibonacci numbers in 2006. Today, along with Sarah Wait Zaranek, we'd like to discuss some of those same ideas, but focus only on execution time. In R2013b, MATLAB includes a new timing function, timeit, one that I mentioned in some earlier posts when it was only available on the MATLAB File Exchange.
To use timeit, you simply pass in a function handle that requires no inputs. If your function requires input values, you can pass them in by creating an anonymous function, where the values are captured from the current workspace. You can learn more about function handles in the MATLAB documentation, and find examples and discussions on this blog.
timeit runs the code several times to ensure that any first-run timing effects do not affect the results - and returns the median time. If you wish to time your function in the situation where it returns more than 0 or 1 output values, you can specify that as one of the inputs to timeit.
In the earlier Fibonacci post, I introduce and times four algorithms. Today we will use the same algorithms, coded as separate programs, in conjunction with timeit. Since we have four algorithms, we will initialize a vector for collecting the timing information.
fibTimes = zeros(1,4);
Let's calculate 102 Fibonacci values (since the first 2 are known already, [1, 1]).
nf = 102; type fibloop
function fibs = fibloop(nf) fibs(1) = 1; fibs(2) = 1; for n = 3:nf fibs(n) = fibs(n-1)+fibs(n-2); end
To use timeit, we simply give it a function handle to the function we wish to time.
fibTimes(1) = timeit(@()fibloop(nf));
You've all heard it before. One reason the former calculation took so much time is at least alleged to be because of growing the array fibf each time through the loop. So now let's use the same loop, but preallocate the output array so it doesn't need to grow during the calculation.
function fibs = fibloopPrealloc(nf) fibs = ones(1,nf); for n = 3:nf fibs(n) = fibs(n-1) + fibs(n-2); end
Now time it.
fibTimes(2) = timeit(@()fibloopPrealloc(nf));
We can use recursion to calculate successive terms, as I showed in that earlier post. Here's the code.
function fibs = fibRecursive(n) if n == 1, fibs = 1; % First element is 1. return; elseif n == 2 fibs = [1 1]; % First two elements are 1. else % Call fibrec with previous result and compute next one from it. fm1 = fibRecursive(n-1); fibs = [fm1 fm1(end)+fm1(end-1)]; end
And now let's use it to calculate the first chunk of Fibonacci numbers.
fibTimes(3) = timeit(@()fibRecursive(nf));
I also explained in the earlier Fibonacci post how to use filter to calculate the sequence as well. Here's the code.
type fibFilter fibTimes(4) = timeit(@()fibFilter(nf));
function fibf = fibFilter(n) x = [1 zeros(1,n-1)]; a = [1 -1 -1]; b = 1; fibf = filter(b, a, x);
It's time to see how quickly the various methods performed. We have multiplied the times by 1000 to make reading the numbers easier.
fprintf('%s\n\n','Compare Times (in milliseconds)') meths = ['loop ',... 'prealloc ',... 'recursive ',... 'filter ']; fprintf('%s\n\n',meths) fprintf('%2.9f ', fibTimes*1000), fprintf('\n')
Compare Times (in milliseconds) loop prealloc recursive filter 0.040766819 0.010003257 0.517234655 0.010549081
Get the MATLAB code
Published with MATLAB® R2013b