{"id":37,"date":"2006-05-17T10:50:44","date_gmt":"2006-05-17T15:50:44","guid":{"rendered":"https:\/\/blogs.mathworks.com\/loren\/?p=37"},"modified":"2017-05-01T19:23:43","modified_gmt":"2017-05-02T00:23:43","slug":"fibonacci-and-filter","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/loren\/2006\/05\/17\/fibonacci-and-filter\/","title":{"rendered":"Fibonacci and filter"},"content":{"rendered":"<div xmlns:mwsh=\"https:\/\/www.mathworks.com\/namespace\/mcode\/v1\/syntaxhighlight.dtd\" class=\"content\">\r\n   <introduction>\r\n      <p>Over the years, people have posted many versions of code for calculating Fibonacci numbers.  I thought I'd collect a few of\r\n         the ideas here and start a discussion on the merits of the different versions.\r\n      <\/p>\r\n   <\/introduction>\r\n   <h3>Contents<\/h3>\r\n   <div>\r\n      <ul>\r\n         <li><a href=\"#1\">Fibonacci Numbers<\/a><\/li>\r\n         <li><a href=\"#2\">Straightforward for-loop<\/a><\/li>\r\n         <li><a href=\"#4\">for-loop with Preallocation<\/a><\/li>\r\n         <li><a href=\"#5\">Recursive Function<\/a><\/li>\r\n         <li><a href=\"#7\">Use filter to Calculate the Sequence<\/a><\/li>\r\n         <li><a href=\"#11\">isequal Tip<\/a><\/li>\r\n         <li><a href=\"#12\">Compare Computation Times<\/a><\/li>\r\n         <li><a href=\"#13\">filter is Useful for Vectorization<\/a><\/li>\r\n      <\/ul>\r\n   <\/div>\r\n   <h3>Fibonacci Numbers<a name=\"1\"><\/a><\/h3>\r\n   <p><a href=\"http:\/\/en.wikipedia.org\/wiki\/Fibonacci\">Here<\/a>'s a place to get some history about the man and his work. Over the centuries, people have that these numbers seem to come\r\n      up in the natural world.  Try searching for Fibonacci and sunflower; I just got 31,600 hits.  Fibonacci numbers are a sequence\r\n      of numbers that can be derived via a recurrence relationship. Start the sequence with two |1|s.  Then, each subsequent number\r\n      in the sequence is found by adding the two most recent numbers.  Mathematically stated:\r\n   <\/p>\r\n   <p><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/images\/loren\/37\/fibfest_eq1506.png\"> <\/p>\r\n   <p><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/images\/loren\/37\/fibfest_eq1507.png\"> <\/p>\r\n   <p><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/images\/loren\/37\/fibfest_eq10940.png\"> <\/p>\r\n   <h3>Straightforward for-loop<a name=\"2\"><\/a><\/h3>\r\n   <p>Let's calculate a reasonable chunk of the sequence through the straightforward method suggested by the formula above.<\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">clear\r\nnf = 102;\r\ntic\r\nfibf(1) = 1;\r\nfibf(2) = 1;\r\n<span style=\"color: #0000FF\">for<\/span> n = 3:nf\r\n    fibf(n) = fibf(n-1)+fibf(n-2);\r\n<span style=\"color: #0000FF\">end<\/span>\r\nftimes(1) = toc;  <span style=\"color: #228B22\">% Collect tic-toc times.<\/span><\/pre><p>And now let's look at the first few numbers to be sure we're getting the expected answers.<\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">fibf(1:10)<\/pre><pre style=\"font-style:oblique\">ans =\r\n     1     1     2     3     5     8    13    21    34    55\r\n<\/pre><h3>for-loop with Preallocation<a name=\"4\"><\/a><\/h3>\r\n   <p>You've all heard it before.  One reason the former calculation took so much time is at least alleged to be because of growing\r\n      the array <tt>fibf<\/tt> 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\r\n      during the calculation.  We'll compare all the computation times later on in this post.\r\n   <\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">tic\r\nfibp = ones(1,nf);\r\n<span style=\"color: #0000FF\">for<\/span> n = 3:nf\r\n    fibp(n) = fibp(n-1) + fibp(n-2);\r\n<span style=\"color: #0000FF\">end<\/span>\r\nftimes(end+1) = toc;<\/pre><h3>Recursive Function<a name=\"5\"><\/a><\/h3>\r\n   <p>The mathematical formula above suggests that we could write a Fibonacci sequence algorithm using a recursive function, i.e.,\r\n      one that calls itself.  Here's what I came up with.  Note that this version grows an array each time.  I might have been able\r\n      to be clever about this.  I doubt the code would be as clear, however.  Feel free to post a version to prove me wrong!\r\n   <\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">type <span style=\"color: #A020F0\">fibrec<\/span><\/pre><pre style=\"font-style:oblique\">\r\nfunction f = fibrec(n)\r\n%FIBREC Recursive function for n Fibonacci numbers.\r\n\r\n% Minimize the error checking so we don't bog down in it. I have included it\r\n%in comments instead.\r\n% if ~isscalar(n) | ~isreal(n) | n&lt;0 | fix(n)~=n\r\n%    error('ArtBlog:fibrec:MBRealPosInt','N must be a real positive integer')\r\n% end\r\nif n == 1,\r\n    f = 1;   % First element is 1.\r\n    return;\r\nelseif n == 2\r\n    f = [1 1];  % First two elements are 1.\r\nelse\r\n    % Call fibrec with previous result and compute next one from it.\r\n    fm1 = fibrec(n-1); \r\n    f = [fm1 fm1(end)+fm1(end-1)];\r\nend\r\n<\/pre><p>And now let's use it to calculate the first chunk of Fibonacci numbers.<\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">tic\r\nfibr = fibrec(nf);\r\nftimes(end+1) = toc;<\/pre><h3>Use filter to Calculate the Sequence<a name=\"7\"><\/a><\/h3>\r\n   <p>I have one other idea now, to use the function <a href=\"https:\/\/www.mathworks.com\/help\/matlab\/ref\/filter.html\"><tt>filter<\/tt><\/a>. Looking at the help,\r\n   <\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">help <span style=\"color: #A020F0\">filter<\/span><\/pre><pre style=\"font-style:oblique\"> FILTER One-dimensional digital filter.\r\n    Y = FILTER(B,A,X) filters the data in vector X with the\r\n    filter described by vectors A and B to create the filtered\r\n    data Y.  The filter is a \"Direct Form II Transposed\"\r\n    implementation of the standard difference equation:\r\n \r\n    a(1)*y(n) = b(1)*x(n) + b(2)*x(n-1) + ... + b(nb+1)*x(n-nb)\r\n                          - a(2)*y(n-1) - ... - a(na+1)*y(n-na)\r\n \r\n    If a(1) is not equal to 1, FILTER normalizes the filter\r\n    coefficients by a(1). \r\n \r\n    FILTER always operates along the first non-singleton dimension,\r\n    namely dimension 1 for column vectors and non-trivial matrices,\r\n    and dimension 2 for row vectors.\r\n \r\n    [Y,Zf] = FILTER(B,A,X,Zi) gives access to initial and final\r\n    conditions, Zi and Zf, of the delays.  Zi is a vector of length\r\n    MAX(LENGTH(A),LENGTH(B))-1, or an array with the leading dimension \r\n    of size MAX(LENGTH(A),LENGTH(B))-1 and with remaining dimensions \r\n    matching those of X.\r\n \r\n    FILTER(B,A,X,[],DIM) or FILTER(B,A,X,Zi,DIM) operates along the\r\n    dimension DIM.\r\n \r\n    See also FILTER2 and, in the Signal Processing Toolbox, FILTFILT.\r\n\r\n    Overloaded functions or methods (ones with the same name in other directories)\r\n       help timeseries\/filter.m\r\n\r\n\r\n    Reference page in Help browser\r\n       doc filter\r\n\r\n<\/pre><p>I see that it could be helpful since prior output values within the filtered array can be used to calculate subsequent ones.\r\n       I want the latest one to add together the previous two outputs.  My input, <tt>x<\/tt> is the array <tt>[1 1 0 0 ... 0]<\/tt>.  And for each output, I need only consider the current input, assuming I pad my original starting value of 1 with zeros.\r\n       Therefore, for this case, <tt>b = 1<\/tt>.  The leading coefficient, multiplying the last output, is 1. And then I want to add the two previous outputs, but in the\r\n      equation, these appear with <tt>-a(k)<\/tt>, so the <tt>a<\/tt> portion of the filter is <tt>[1 -1 -1]<\/tt>.\r\n   <\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">tic\r\nx = [1 zeros(1,nf-1)];\r\na = [1 -1 -1];\r\nb = 1;\r\nfibfil = filter(b, a, x);\r\nftimes(end+1) = toc;<\/pre><p>Let's be sure I got the right answer.<\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">isequal(fibf, fibp, fibr, fibfil)<\/pre><pre style=\"font-style:oblique\">ans =\r\n     1\r\n<\/pre><h3>isequal Tip<a name=\"11\"><\/a><\/h3>\r\n   <p>Did you know <tt>isequal<\/tt> could take more than two inputs?  If you store your items to compare in a cell array, <tt>C<\/tt>, you can then do this: <tt>passfail = isequal(C{:}):<\/tt>, taking advantage of the comma-separated list notation.)\r\n   <\/p>\r\n   <h3>Compare Computation Times<a name=\"12\"><\/a><\/h3>\r\n   <p>It's time to see how quickly the various methods performed. I have multiplied the times by 1000 to make reading the numbers\r\n      easier.\r\n   <\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">fprintf(<span style=\"color: #A020F0\">'%s\\n\\n'<\/span>,<span style=\"color: #A020F0\">'Compare Times (in milliseconds)'<\/span>)\r\nmeths = [<span style=\"color: #A020F0\">'loop           '<\/span>,<span style=\"color: #0000FF\">...<\/span>\r\n         <span style=\"color: #A020F0\">'prealloc       '<\/span>,<span style=\"color: #0000FF\">...<\/span>\r\n         <span style=\"color: #A020F0\">'recursive      '<\/span>,<span style=\"color: #0000FF\">...<\/span>\r\n         <span style=\"color: #A020F0\">'filter         '<\/span>];\r\nfprintf(<span style=\"color: #A020F0\">'%s\\n\\n'<\/span>,meths)\r\nfprintf(<span style=\"color: #A020F0\">'%2.9f    '<\/span>, ftimes*1000), fprintf(<span style=\"color: #A020F0\">'\\n'<\/span>)<\/pre><pre style=\"font-style:oblique\">Compare Times (in milliseconds)\r\n\r\nloop           prealloc       recursive      filter         \r\n\r\n0.329650836    0.243606380    2.244419333    0.058666674    \r\n<\/pre><h3>filter is Useful for Vectorization<a name=\"13\"><\/a><\/h3>\r\n   <p>I've shown one example here in which <tt>filter<\/tt> was useful for vectorizing code and make it perform well.  Another one I know about is <a title=\"https:\/\/www.mathworks.com\/matlabcentral\/fileexchange\/loadFile.do?objectId=9428 (link no longer works)\">code<\/a> from John D'Errico for calculating a moving window standard deviation. There are probably others. Do you know of other good\r\n      uses for <tt>filter<\/tt>, besides straightforward applications for filtering and convolving signals? Let me know.\r\n   <\/p>\r\n   <p style=\"text-align: right; font-size: xx-small; font-weight:lighter;   font-style: italic; color: gray\"><br>\r\n      Published with MATLAB&reg; 7.2<br><\/p>\r\n<\/div>\r\n<!--\r\n##### SOURCE BEGIN #####\r\n%% Fibonacci Festival\r\n% Over the years, people have posted many versions of code for calculating\r\n% Fibonacci numbers.  I thought I'd collect a few of the ideas here and\r\n% start a discussion on the merits of the different versions.\r\n%% Fibonacci Numbers\r\n% <http:\/\/en.wikipedia.org\/wiki\/Fibonacci Here>'s a place to get some\r\n% history about the man and his work. Over the centuries, people have that\r\n% these numbers seem to come up in the natural world.  Try searching for\r\n% Fibonacci and sunflower; I just got 31,600 hits.  Fibonacci numbers are a\r\n% sequence of numbers that can be derived via a recurrence relationship.\r\n% Start the sequence with two |1|s.  Then, each subsequent number in the\r\n% sequence is found by adding the two most recent numbers.  Mathematically\r\n% stated:\r\n% \r\n% $$ F_1 = 1 $$\r\n%\r\n% $$ F_2 = 1 $$\r\n%\r\n% $$ F_n = F_{n-1} + F_{n-2} $$\r\n\r\n%% Straightforward for-loop\r\n% Let's calculate a reasonable chunk of the sequence through the\r\n% straightforward method suggested by the formula above.\r\nclear\r\nnf = 102;\r\ntic\r\nfibf(1) = 1;\r\nfibf(2) = 1;\r\nfor n = 3:nf\r\n    fibf(n) = fibf(n-1)+fibf(n-2);\r\nend\r\nftimes(1) = toc;  % Collect tic-toc times.\r\n%%\r\n% And now let's look at the first few numbers to be sure we're getting the\r\n% expected answers.\r\nfibf(1:10)\r\n\r\n%% for-loop with Preallocation\r\n% You've all heard it before.  One reason the former calculation took so\r\n% much time is at least alleged to be because of growing the array |fibf|\r\n% each time through the loop.  So now let's use the same loop, but\r\n% preallocate the output array so it doesn't need to grow during the\r\n% calculation.  We'll compare all the computation times later on in this\r\n% post.\r\ntic\r\nfibp = ones(1,nf);\r\nfor n = 3:nf\r\n    fibp(n) = fibp(n-1) + fibp(n-2);\r\nend\r\nftimes(end+1) = toc;\r\n%% Recursive Function\r\n% The mathematical formula above suggests that we could write a Fibonacci\r\n% sequence algorithm using a recursive function, i.e., one that calls\r\n% itself.  Here's what I came up with.  Note that this version grows an\r\n% array each time.  I might have been able to be clever about this.  I\r\n% doubt the code would be as clear, however.  Feel free to\r\n% <http:?p37\/Respond post> a version to prove me wrong!\r\ntype fibrec\r\n%%\r\n% And now let's use it to calculate the first chunk of Fibonacci numbers.\r\ntic\r\nfibr = fibrec(nf);\r\nftimes(end+1) = toc;\r\n\r\n%% Use filter to Calculate the Sequence\r\n% I have one other idea now, to use the function\r\n% <https:\/\/www.mathworks.com\/help\/matlab\/ref\/filter.html |filter|>.\r\n% Looking at the help,\r\nhelp filter\r\n%%\r\n% I see that it could be helpful since prior output values within the\r\n% filtered array can be used to calculate subsequent ones.  I want the\r\n% latest one to add together the previous two outputs.  My input, |x| is\r\n% the array |[1 1 0 0 ... 0]|.  And for each output, I need only consider\r\n% the current input, assuming I pad my original starting values of [1 1]\r\n% with zeros.  Therefore, for this case, |b = 1|.  The leading coefficient, multiplying the last output, is 1.\r\n% And then I want to add the two previous outputs, but\r\n% in the equation, these appear with |-a(k)|, so the |a| portion of the\r\n% filter is |[1 -1 -1]|.\r\n%%\r\n%\r\ntic\r\nx = [1 zeros(1,nf-1)];\r\na = [1 -1 -1];\r\nb = 1;\r\nfibfil = filter(b, a, x);\r\nftimes(end+1) = toc;\r\n%%\r\n% Let's be sure I got the right answer.  \r\nisequal(fibf, fibp, fibr, fibfil)\r\n%% isequal Tip\r\n% Did you know |isequal| could take\r\n% more than two inputs?  If you store your items to compare in a cell\r\n% array, |C|, you can then do this: |passfail = isequal(C{:}):|, taking\r\n% advantage of the comma-separated list notation.)\r\n%% Compare Computation Times\r\n% It's time to see how quickly the various methods performed.\r\n% I have multiplied the times by 1000 to make reading the numbers easier.\r\nfprintf('%s\\n\\n','Compare Times (in milliseconds)')\r\nmeths = ['loop           ',...\r\n         'prealloc       ',...\r\n         'recursive      ',...\r\n         'filter         '];\r\nfprintf('%s\\n\\n',meths)\r\nfprintf('%2.9f    ', ftimes*1000), fprintf('\\n')\r\n%% filter is Useful for Vectorization\r\n% I've shown one example here in which |filter| was useful for vectorizing\r\n% code and make it perform well.  Another one I know about is \r\n% <https:\/\/www.mathworks.com\/matlabcentral\/fileexchange\/loadFile.do?objectId=9428 code>\r\n% from John D'Errico for calculating a moving window standard deviation.\r\n% There are problably others. Do you know of other good uses for |filter|,\r\n% besides straightforward applications for filtering and convolving\r\n% signals? <http:?p=37\/Respond Let me know>.\r\n\r\n##### SOURCE END #####\r\n-->","protected":false},"excerpt":{"rendered":"<p>\r\n   \r\n      Over the years, people have posted many versions of code for calculating Fibonacci numbers.  I thought I'd collect a few of\r\n         the ideas here and start a discussion on the merits... <a class=\"read-more\" href=\"https:\/\/blogs.mathworks.com\/loren\/2006\/05\/17\/fibonacci-and-filter\/\">read more >><\/a><\/p>","protected":false},"author":39,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":[],"categories":[10,15],"tags":[],"_links":{"self":[{"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/posts\/37"}],"collection":[{"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/users\/39"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/comments?post=37"}],"version-history":[{"count":2,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/posts\/37\/revisions"}],"predecessor-version":[{"id":2326,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/posts\/37\/revisions\/2326"}],"wp:attachment":[{"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/media?parent=37"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/categories?post=37"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/tags?post=37"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}