Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > Fibonnaci

Reply
Thread Tools

Fibonnaci

 
 
MARQUITOS51
Guest
Posts: n/a
 
      12-09-2005
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.

 
Reply With Quote
 
 
 
 
Jordan Abel
Guest
Posts: n/a
 
      12-09-2005
On 2005-12-09, MARQUITOS51 <(E-Mail Removed)> 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]
 
Reply With Quote
 
 
 
 
Richard Heathfield
Guest
Posts: n/a
 
      12-09-2005
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
instead of recursively.

--
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)
 
Reply With Quote
 
Suman
Guest
Posts: n/a
 
      12-09-2005

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
> instead of recursively.


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

 
Reply With Quote
 
Jordan Abel
Guest
Posts: n/a
 
      12-09-2005
On 2005-12-09, Richard Heathfield <(E-Mail Removed)> 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.
 
Reply With Quote
 
buda
Guest
Posts: n/a
 
      12-09-2005
"Jordan Abel" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed)...
> On 2005-12-09, Richard Heathfield <(E-Mail Removed)> 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.


 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off




Advertisments