Thread Subject:

Need Help with FIB numbers!

n = input('What Fibonacci number would you like? ');
if (isscalar(n) && isnumeric(n) && n > 2)
% n is valid
n = fix(n); % turn into integer, just to be safe.
f_n_2 = (n - 2); % f(n-2) ... for first case n = 3, so this is f(1)
f_n_1 = n - 1; % f(n-1) ... for first case n = 3, so this is f(2)
fib = 0; % just initializes.
i = 3; % index counter
while i <= n
fib = (f_n_2) + (f_n_1); % f(i) = f(i-2) + f(i-1)
f_n_2 = f_n_1; % Keep track of f(i-1)
f_n_1 = fib; % and f(i), as they are used for f(i+1)
i = 1:120 ; % increment i
end
fprintf('The %.0fth Fibonacci number is %.0f\n', n, fib);
elseif n <= 2
disp('For Fibonacci numbers < 3, use some other program.');
else
disp('Please give me a number ...')
end

"Karandeep Brar" <nyj_jets@yahoo.com> wrote in message <jbbrib$e42$1@newscl01ah.mathworks.com>...
> n = input('What Fibonacci number would you like? ');
> if (isscalar(n) && isnumeric(n) && n > 2)
> % n is valid
> n = fix(n); % turn into integer, just to be safe.
> f_n_2 = (n - 2); % f(n-2) ... for first case n = 3, so this is f(1)
> f_n_1 = n - 1; % f(n-1) ... for first case n = 3, so this is f(2)
> fib = 0; % just initializes.
> i = 3; % index counter
> while i <= n
> fib = (f_n_2) + (f_n_1); % f(i) = f(i-2) + f(i-1)
> f_n_2 = f_n_1; % Keep track of f(i-1)
> f_n_1 = fib; % and f(i), as they are used for f(i+1)
> i = 1:120 ; % increment i
> end
> fprintf('The %.0fth Fibonacci number is %.0f\n', n, fib);
> elseif n <= 2
> disp('For Fibonacci numbers < 3, use some other program.');
> else
> disp('Please give me a number ...')
> end

If you look in my vpi toolbox, you will find the fibonacci
function, a tool that can EFFICIENTLY compute the nth
fibonacci number.


>> fibonacci([1 2 4 8 16 32 64 128])
ans =
 
Columns 1 through 2
                              1 1
 
Columns 3 through 4
                              3 21
 
Columns 5 through 6
                            987 2178309
 
Columns 7 through 8
                 10610209857723 251728825683549488150424261


See that it returns them as VPI numbers, since Fibonacci
numbers grow so rapidly.

>> tic,f = fibonacci(1000000);toc
Elapsed time is 2.958356 seconds.
>> log10(f)
ans =
   2.0899e+05

Yes, the one millionth fibonacci number has 209,000
digits, so this computation did take some work to do fully.

If your intent is to compute the 120th fibonacci number,
you should recognize that it will be too large to represent
as a double precision number, so beware.

>> fibonacci(120)
ans =
    5358359254990966640871840
>> log10(ans)
ans =
       24.729

John

"John D'Errico" <woodchips@rochester.rr.com> wrote in message <jbbsck$ggg$1@newscl01ah.mathworks.com>...
> "Karandeep Brar" <nyj_jets@yahoo.com> wrote in message <jbbrib$e42$1@newscl01ah.mathworks.com>...
> > n = input('What Fibonacci number would you like? ');
> > if (isscalar(n) && isnumeric(n) && n > 2)
> > % n is valid
> > n = fix(n); % turn into integer, just to be safe.
> > f_n_2 = (n - 2); % f(n-2) ... for first case n = 3, so this is f(1)
> > f_n_1 = n - 1; % f(n-1) ... for first case n = 3, so this is f(2)
> > fib = 0; % just initializes.
> > i = 3; % index counter
> > while i <= n
> > fib = (f_n_2) + (f_n_1); % f(i) = f(i-2) + f(i-1)
> > f_n_2 = f_n_1; % Keep track of f(i-1)
> > f_n_1 = fib; % and f(i), as they are used for f(i+1)
> > i = 1:120 ; % increment i
> > end
> > fprintf('The %.0fth Fibonacci number is %.0f\n', n, fib);
> > elseif n <= 2
> > disp('For Fibonacci numbers < 3, use some other program.');
> > else
> > disp('Please give me a number ...')
> > end
>
> If you look in my vpi toolbox, you will find the fibonacci
> function, a tool that can EFFICIENTLY compute the nth
> fibonacci number.
>
>
> >> fibonacci([1 2 4 8 16 32 64 128])
> ans =
>
> Columns 1 through 2
> 1 1
>
> Columns 3 through 4
> 3 21
>
> Columns 5 through 6
> 987 2178309
>
> Columns 7 through 8
> 10610209857723 251728825683549488150424261
>
>
> See that it returns them as VPI numbers, since Fibonacci
> numbers grow so rapidly.
>
> >> tic,f = fibonacci(1000000);toc
> Elapsed time is 2.958356 seconds.
> >> log10(f)
> ans =
> 2.0899e+05
>
> Yes, the one millionth fibonacci number has 209,000
> digits, so this computation did take some work to do fully.
>
> If your intent is to compute the 120th fibonacci number,
> you should recognize that it will be too large to represent
> as a double precision number, so beware.
>
> >> fibonacci(120)
> ans =
> 5358359254990966640871840
> >> log10(ans)
> ans =
> 24.729
>
> John


I know what u mean but I have to make this program and I can't ge tit to funciton properly.

You can use a recursive function.

The FIB numbers is :
F(0) = 0
F(1)= 1
F(n) = F(n - 1) + F(n - 2)

**********************************************************************
function F = FIB(n)
if (n == 0)
F = 0;
elseif(n == 1)
F = 1;
else
F = FIB(n - 1) + ??------- that will be ur assignment(obvious) -(fill the ??)
end
***********************************************************************

to run the function:
FIB(15)
will give u 610
etc

"ade77 " <ade100a@gmail.com> wrote in message <jbc1c0$de$1@newscl01ah.mathworks.com>...
> You can use a recursive function.
>
> The FIB numbers is :
> F(0) = 0
> F(1)= 1
> F(n) = F(n - 1) + F(n - 2)
>
> **********************************************************************
> function F = FIB(n)
> if (n == 0)
> F = 0;
> elseif(n == 1)
> F = 1;
> else
> F = FIB(n - 1) + ??------- that will be ur assignment(obvious) -(fill the ??)
> end
> ***********************************************************************
>
> to run the function:
> FIB(15)
> will give u 610
> etc

Recursion is a TERRIBLE thing to do to a fibonacci number.

Computation of the nth fibonacci number using recursion
will take exponentially many recursive calls, and a vast
amount of time. For example, computing fib(2) requires
calls to fib(0) and fib(1). But fib(3) will call fib(2) and
fib(1). But that call to fib(2) calls fib(1) and fib(0). See
that there will be very many multiple calls to the lower order
fibonacci numbers. This will grow to a huge number of calls
for only a small value of n.

Don't do it. At least not unless you learn what the term
memoization means.

John

"John D'Errico" <woodchips@rochester.rr.com> wrote in message <jbc2hg$3l5$1@newscl01ah.mathworks.com>...
> "ade77 " <ade100a@gmail.com> wrote in message <jbc1c0$de$1@newscl01ah.mathworks.com>...
> > You can use a recursive function.
> >
> > The FIB numbers is :
> > F(0) = 0
> > F(1)= 1
> > F(n) = F(n - 1) + F(n - 2)
> >
> > **********************************************************************
> > function F = FIB(n)
> > if (n == 0)
> > F = 0;
> > elseif(n == 1)
> > F = 1;
> > else
> > F = FIB(n - 1) + ??------- that will be ur assignment(obvious) -(fill the ??)
> > end
> > ***********************************************************************
> >
> > to run the function:
> > FIB(15)
> > will give u 610
> > etc
>
> Recursion is a TERRIBLE thing to do to a fibonacci number.
>
> Computation of the nth fibonacci number using recursion
> will take exponentially many recursive calls, and a vast
> amount of time. For example, computing fib(2) requires
> calls to fib(0) and fib(1). But fib(3) will call fib(2) and
> fib(1). But that call to fib(2) calls fib(1) and fib(0). See
> that there will be very many multiple calls to the lower order
> fibonacci numbers. This will grow to a huge number of calls
> for only a small value of n.
>
> Don't do it. At least not unless you learn what the term
> memoization means.
>
> John

The code should be basically correct i just don't know where my error is cause it works when i do for loop but for while

"John D'Errico" <woodchips@rochester.rr.com> wrote in message <jbc2hg$3l5$1@newscl01ah.mathworks.com>...
> "ade77 " <ade100a@gmail.com> wrote in message <jbc1c0$de$1@newscl01ah.mathworks.com>...
> > You can use a recursive function.
> >
> > The FIB numbers is :
> > F(0) = 0
> > F(1)= 1
> > F(n) = F(n - 1) + F(n - 2)
> >
> > **********************************************************************
> > function F = FIB(n)
> > if (n == 0)
> > F = 0;
> > elseif(n == 1)
> > F = 1;
> > else
> > F = FIB(n - 1) + ??------- that will be ur assignment(obvious) -(fill the ??)
> > end
> > ***********************************************************************
> >
> > to run the function:
> > FIB(15)
> > will give u 610
> > etc
>
> Recursion is a TERRIBLE thing to do to a fibonacci number.
>
> Computation of the nth fibonacci number using recursion
> will take exponentially many recursive calls, and a vast
> amount of time. For example, computing fib(2) requires
> calls to fib(0) and fib(1). But fib(3) will call fib(2) and
> fib(1). But that call to fib(2) calls fib(1) and fib(0). See
> that there will be very many multiple calls to the lower order
> fibonacci numbers. This will grow to a huge number of calls
> for only a small value of n.
>
> Don't do it. At least not unless you learn what the term
> memoization means.
>
> John

Sometimes , some of you regulars fail to decipher what is a school project and what u will do in a company. In cases like this, the assignment is meant for them to demonstrate the use of recursive functions or something similar, and not some optimal code performance. Having gone through years of school work myself within the last decade, the whole objective of this kind of project is to build their programming skills, then,, when they are good enough, they can start worring about memory.... and they can decipher what is good and bad, as thier programming skills improve.

As someone who programs in C++, while the use of recursive functions in most cases is not a good idea, it is still a must know for us, and as your programming skills grows, u will be able to decipher if you should use it or not.

"ade77 " <ade100a@gmail.com> wrote in message <jbc8mc$kic$1@newscl01ah.mathworks.com>...
> "John D'Errico" <woodchips@rochester.rr.com> wrote in message <jbc2hg$3l5$1@newscl01ah.mathworks.com>...
> > "ade77 " <ade100a@gmail.com> wrote in message <jbc1c0$de$1@newscl01ah.mathworks.com>...
> > > You can use a recursive function.
> > >
> > > The FIB numbers is :
> > > F(0) = 0
> > > F(1)= 1
> > > F(n) = F(n - 1) + F(n - 2)
> > >
> > > **********************************************************************
> > > function F = FIB(n)
> > > if (n == 0)
> > > F = 0;
> > > elseif(n == 1)
> > > F = 1;
> > > else
> > > F = FIB(n - 1) + ??------- that will be ur assignment(obvious) -(fill the ??)
> > > end
> > > ***********************************************************************
> > >
> > > to run the function:
> > > FIB(15)
> > > will give u 610
> > > etc
> >
> > Recursion is a TERRIBLE thing to do to a fibonacci number.
> >
> > Computation of the nth fibonacci number using recursion
> > will take exponentially many recursive calls, and a vast
> > amount of time. For example, computing fib(2) requires
> > calls to fib(0) and fib(1). But fib(3) will call fib(2) and
> > fib(1). But that call to fib(2) calls fib(1) and fib(0). See
> > that there will be very many multiple calls to the lower order
> > fibonacci numbers. This will grow to a huge number of calls
> > for only a small value of n.
> >
> > Don't do it. At least not unless you learn what the term
> > memoization means.
> >
> > John
>
> Sometimes , some of you regulars fail to decipher what is a school project and what u will do in a company. In cases like this, the assignment is meant for them to demonstrate the use of recursive functions or something similar, and not some optimal code performance. Having gone through years of school work myself within the last decade, the whole objective of this kind of project is to build their programming skills, then,, when they are good enough, they can start worring about memory.... and they can decipher what is good and bad, as thier programming skills improve.
>
> As someone who programs in C++, while the use of recursive functions in most cases is not a good idea, it is still a must know for us, and as your programming skills grows, u will be able to decipher if you should use it or not.

I have a FOR loop I'm struggling with the WHILE loop =/

"ade77 " <ade100a@gmail.com> wrote in message <jbc8mc$kic$1@newscl01ah.mathworks.com>...
> "John D'Errico" <woodchips@rochester.rr.com> wrote in message <jbc2hg$3l5$1@newscl01ah.mathworks.com>...
> > "ade77 " <ade100a@gmail.com> wrote in message <jbc1c0$de$1@newscl01ah.mathworks.com>...
> > > You can use a recursive function.
> > >
> > > The FIB numbers is :
> > > F(0) = 0
> > > F(1)= 1
> > > F(n) = F(n - 1) + F(n - 2)
> > >
> > > **********************************************************************
> > > function F = FIB(n)
> > > if (n == 0)
> > > F = 0;
> > > elseif(n == 1)
> > > F = 1;
> > > else
> > > F = FIB(n - 1) + ??------- that will be ur assignment(obvious) -(fill the ??)
> > > end
> > > ***********************************************************************
> > >
> > > to run the function:
> > > FIB(15)
> > > will give u 610
> > > etc
> >
> > Recursion is a TERRIBLE thing to do to a fibonacci number.
> >
> > Computation of the nth fibonacci number using recursion
> > will take exponentially many recursive calls, and a vast
> > amount of time. For example, computing fib(2) requires
> > calls to fib(0) and fib(1). But fib(3) will call fib(2) and
> > fib(1). But that call to fib(2) calls fib(1) and fib(0). See
> > that there will be very many multiple calls to the lower order
> > fibonacci numbers. This will grow to a huge number of calls
> > for only a small value of n.
> >
> > Don't do it. At least not unless you learn what the term
> > memoization means.
> >
> > John
>
> Sometimes , some of you regulars fail to decipher what is a school project and what u will do in a company. In cases like this, the assignment is meant for them to demonstrate the use of recursive functions or something similar, and not some optimal code performance. Having gone through years of school work myself within the last decade, the whole objective of this kind of project is to build their programming skills, then,, when they are good enough, they can start worring about memory.... and they can decipher what is good and bad, as thier programming skills improve.
>
> As someone who programs in C++, while the use of recursive functions in most cases is not a good idea, it is still a must know for us, and as your programming skills grows, u will be able to decipher if you should use it or not.

It is quite obvious this is a school project. As obviously,
I'm trying to tell the person that doing it recursively is a
terrible idea, that a recursive code to compute 120
Fibonacci numbers is a terrible idea, if that is what 1:120
was intended to mean.

Computation of the 120th Fibonacci number in MATLAB,
or in C will fail, period, if you use double precision anyway.
The number of recursive calls grows exponentially. In fact,
you can probably show that the number of calls is itself a
Fibonacci number, which grows exponentially!

As I said, it IS possible to use techniques such as
memoization to do the above computations well, in a way
that is recursive, yet does not require massive numbers of
function calls. Simply store the numbers you have already
computed.

Of course, no matter what you do, you cannot store such
a result in a double anyway. If you intend to do that, you
might as well use Binet's formula for the fibs, and be done
with it all.

This is what I was saying. Read my lips. Even better, read
my words.

John

"Karandeep Brar" <nyj_jets@yahoo.com> wrote in message <jbc9m8$n2h$1@newscl01ah.mathworks.com>...

> > Sometimes , some of you regulars fail to decipher what is a school project and what u will do in a company. In cases like this, the assignment is meant for them to demonstrate the use of recursive functions or something similar, and not some optimal code performance.

Perhaps I can explain this better.

There are many textbooks out there, written by people
who read other textbooks, by people who took courses
from some fool who had no idea of what they were
doing with recursion. After all, all they wanted to do
was to teach a simple concept about recursion, so they
picked out one of the easiest examples of a recurrence
relation they could think of: Fibonacci numbers.

What happens is the homework assignment ends, the
student learns this is recursion. Fine. But then, there
is no followup, telling the student why this was a poor
choice of problem to solve with simple recursion in the
first place! What happens is that student grows up, then
writes a textbook of their own, or teaches a course. They
use the same trivial and terrible example for their students
and readers. It propagates, but nobody ever learns the
one thing they should have learned in the first place -
that recursion can be a terrible thing to do to a good
sequence of numbers. Nobody ever learns when such
a thing is a bad idea, and they never learn how to
improve upon the concept, by using schemes like
memoization to trade off some memory for millions of
recursive calls.

This is my point, that the student should take something
from the homework assignment, beyond the simple
mechanics of recursion, learning when it is a bad idea
in the first place. For example, what is the difference
between use of recursion to compute factorials and the
use in a Fibonacci sequence? Next, why is a simple,
trivial loop more efficient in both cases? And as far as
the Fibonacci numbers are concerned, there are better
schemes out there, even compared to that simple loop.

It is quite easy to show that computation of the n'th
Fibonacci number F(n) using the simple recurrence
formula takes O(F(n)) recurrent calls. Thus we can
infer that the computation time will be O(phi^n),
where phi = (1+sqrt(5))/2.

Compare this to the time required for a loop for the
same process, which is clearly O(n). Even better,
there exists a scheme which requires only O(log2(n))
computations for the same job. Note that when n
is at all large, these three schemes are wildly divergent
in the amount of work required.

John