Path: news.mathworks.com!not-for-mail
From: "John D'Errico" <woodchips@rochester.rr.com>
Newsgroups: comp.soft-sys.matlab
Subject: Re: Fibonacci
Date: Sun, 11 Apr 2010 09:24:03 +0000 (UTC)
Organization: John D'Errico (1-3LEW5R)
Lines: 42
Message-ID: <hps4fj$qok$1@fred.mathworks.com>
References: <hprijn$3bl$1@fred.mathworks.com> <hprohm$l1n$1@fred.mathworks.com>
Reply-To: "John D'Errico" <woodchips@rochester.rr.com>
NNTP-Posting-Host: webapp-05-blr.mathworks.com
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
X-Trace: fred.mathworks.com 1270977843 27412 172.30.248.35 (11 Apr 2010 09:24:03 GMT)
X-Complaints-To: news@mathworks.com
NNTP-Posting-Date: Sun, 11 Apr 2010 09:24:03 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 869215
Xref: news.mathworks.com comp.soft-sys.matlab:625474

"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message <hprohm$l1n$1@fred.mathworks.com>...
> "Jake " <nathan.a2000@googlemail.com> wrote in message <hprijn$3bl$1@fred.mathworks.com>...
> > function fib(n)
> > int n;
> > if(n==0 ) return;
> > else return n * fib(n-1);  // line 7
> > .......
> -------------------------
>   Besides the serious flaws pointed out by James and Matt, there are other difficulties with what you have written here, Jake.  First of all, you seem to confuse the Fibonacci series with factorials.  Where did you ever get such a strange notion?  They are by no means the same entity.
> 
>   Secondly, if you eventually do manage to write a correct version using recursion, as you attempted to do with your present version, you will find that because the iteration involved with fibonacci numbers requires looking up two previous fibonacci numbers, then for a large number of terms out, the number of recursive calls will grow exponentially.  The tenth term will need the ninth and eighth terms.  These in turn will need the eighth and seventh and again the seventh and sixth.  This goes on all the way back to the first two terms.  For terms very far out in the series the number of these repeated calls for the same previous term becomes very large indeed.  That is not an efficient way to do mathematics.  The fibonacci series is not a good candidate for recursion and you should use a different method.
> 
> Roger Stafford

As Roger points out, this is a terrible way to compute
the Fibonacci series. However, there are good ways
to do so, using a technique called memoization. In
fact there are some very pretty tricks that one can
use. I teach about many of them in a File Exchange
submission:

http://www.mathworks.com/matlabcentral/fileexchange/24022-fibonacci-and-lucas-numbers

Basically, I show that simple recursion to compute the
n'th Fibonacci number requires O(2^n) computations,
whereas with some thought, one can reduce that to
something like O(n^2) floating point operations. It
actually only requires the computations of O(log(n)) 
memoized recursive Fibonacci evaluations. But since
the n'th Fibonacci number will rapidly have thousands
or even millions of digits, I end up at roughly O(n^2).

A quick test, computing the 1 million'th Fibonacci
number, takes only

tic,F = fibonacci(1000000);toc
Elapsed time is 16.575102 seconds.

Since F has over 200,000 digits, this seems eminently
reasonable to me.

John