Fibonnaci

Discussion in 'C Programming' started by MARQUITOS51, Dec 9, 2005.

1. MARQUITOS51Guest

Im trying to find any code in C developed to calculate the fibonnacci
series with or without functions. I need a code example so I can
studied and see how it works.

MARQUITOS51, Dec 9, 2005

2. Jordan AbelGuest

On 2005-12-09, MARQUITOS51 <> wrote:
> Im trying to find any code in C developed to calculate the fibonnacci
> series with or without functions. I need a code example so I can
> studied and see how it works.

If you're cheating on homework, ask for something less obvious than code
examples.

#include <math.h>

double fibon(double n) {
return (
pow(1.6180339887498948482045868343656381177203L,n)
-
pow(-.6180339887498948482045868343656381177203L,n)
)/2.2360679774997896964091736687312762354406L;
}

Good luck explaining to your instructor how this works.

[If you're not, you'll need to give people more to work with to show
that you understand the problem and also give your best effort and show
what code you've tried that doesn't work]

Jordan Abel, Dec 9, 2005

3. Richard HeathfieldGuest

MARQUITOS51 said:

> Im trying to find any code in C developed to calculate the fibonnacci
> series with or without functions. I need a code example so I can
> studied and see how it works.

The Fibonacci series can be defined as f(0) = 0, f(1) = 1, and f(n) = f(n -
1) + f(n - 2) for n > 1.

So it goes like this: 0, 1, 1, 2, 3, 5, 8, 13, etc.

Think about how you would implement this recursively. Hint: look at the
above definition.

Write it. See how slow it is? Find out why. Hint: use printf.

Now think about how you could make it a lot faster. Hint: think about
arrays.

Now see if you can avoid the need for an array by writing this iteratively

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)

Richard Heathfield, Dec 9, 2005
4. SumanGuest

Richard Heathfield wrote:
> MARQUITOS51 said:
>
> > Im trying to find any code in C developed to calculate the fibonnacci
> > series with or without functions. I need a code example so I can
> > studied and see how it works.

>

[...]
> Now see if you can avoid the need for an array by writing this iteratively

Do you mean Q-Matrix? If not, that's one more thing the OP might want
to check
out.

Suman, Dec 9, 2005
5. Jordan AbelGuest

On 2005-12-09, Richard Heathfield <> wrote:
> Write it. See how slow it is? Find out why. Hint: use printf.
>
> Now think about how you could make it a lot faster. Hint: think about
> arrays.

All that's needed to change the worst-case performance to linear is a
two-element cache.

Jordan Abel, Dec 9, 2005
6. budaGuest

"Jordan Abel" <> wrote in message
news:...
> On 2005-12-09, Richard Heathfield <> wrote:
>> Write it. See how slow it is? Find out why. Hint: use printf.
>>
>> Now think about how you could make it a lot faster. Hint: think about
>> arrays.

>
> All that's needed to change the worst-case performance to linear is a
> two-element cache.

I think Richard tryed to explain the process... how to move from a top down,
recursion-based solution to a memoized recursion, and then to a bottom-up
solution (building that same array that was used for memoization from 0 to
n). This is infact the best you can do if you need to keep all of the first
n Fibonacci numbers - it is unclear if the OP needs this, or he just wants
to write them out. Also, your comment is covered in the last "idea" Richard
gives.

buda, Dec 9, 2005