Help Please Fibonacci Number Program - GameDev.Net Discussion Forums

Add Forum to Favorites | Send Topic To a Friend | View Forum FAQ | Track this topic

Last Thread Next Thread

Help Please Fibonacci Number Program

WildJester Member since: 1/25/2005 From: New York, USA

Posted - 10/9/2006 12:32:27 AM

Hey there. I am programming fibonacci's number program in the c programming language. Here is what I have so far.

/* Jonathan Schechter
Fibbanaci Numbers*/

#include<stdio.h>

int main(void)
{
// Fibbonacci's Number = fibbNUM
int getNUM
int fibbNUM;

printf("Enter the Fibonacci number to calculate.\n");
printf("The number must be between 2 and 46. Enter 1 to quit:%i",getNUM\n);
scanf("%i",&getNUM);

//Check to see if user wants to quit program
if (getNUM == 1)
{
exit(o);
}

//Check to see if user entered a new number to run through fibb sequence
else if ((getNUM >= 2) && (getNUM <= 46))
{
//Since the user chose not to exit, the users input(getNUM) is now set to fibbNUM so that calculations can begin
fibbNUM = getNUM;

while (fibbNUM >=2 && fibbNUM<=46)
{

fibbNUM++

}
}

//If user enters a number other than 1 or 2-46 tell them to enter new number
else
{
printf("Enter the Fibonacci number to calculate.\n");
printf("The number must be between 2 and 46. Enter 1 to quit:%i",quit\n);
}

printf(" Fibonacci Fibonacci\n");
printf(" N number quotient\n");
printf("-------------------------------------\n");

//Fibbonacci's Number Equation

return 0;
}

the goal is to ask user to input a number between 2to46 and then print along with fibonacci's quotient. i am kind of lost with this and i want to know hot i can call the value calculated by fibb formula into the correct place on the table. Okay any help would be great!

User Rating: 899 | Rate This User

Report this Post to a Moderator | Link

WildJester Member since: 1/25/2005 From: New York, USA

Posted - 10/9/2006 4:54:40 AM

OWNED!!!! (lol i got it)

/*
Author: Jonathan Schechter
Program: Fibonacci Numbers
*/

#include <stdio.h>

int getNUM;
int fibbNUMminus1 = 1;
int fibbNUMminus2 = 0;
int fibbNUM;
float fibbQUO;
int setNUM = 2;

int main(void)
{
while(getNUM < 2 || getNUM > 46)
{
/* Fibbonaccis Number is represented by the integer fibbNUM. */
printf("Enter the Fibonacci number to calculate.\n");
printf("The number must be between 2 and 46. Enter 1 to quit:");
scanf("%d",&getNUM);

/*Check to see if user wants to quit program. */
if (getNUM == 1)
{
return 0;
}
}

printf("\n Fibonacci Fibonacci \n");
printf(" N number quotient \n");
printf("------------------------------------- \n");
printf("0 0 N/A \n");
printf("1 1 N/A \n");

/* Check to see if user entered a new number to run through fibb sequence. */
while((setNUM <= getNUM))
{

fibbNUM = fibbNUMminus1 + fibbNUMminus2;
fibbQUO = ( (float)fibbNUM / (fibbNUMminus1) );
printf("%d\t\t%d\t\t%f\n",setNUM,fibbNUM,fibbQUO);
setNUM++;

fibbNUMminus2 = fibbNUMminus1;
fibbNUMminus1 = fibbNUM;

}

return 0;
}

User Rating: 899 | Rate This User

Report this Post to a Moderator | Link

TheAdmiral Member since: 4/15/2004 From: London, United Kingdom

Posted - 10/9/2006 8:50:06 PM

While the iterative identity you are using is kind of characteristic of the Fibonacci sequence, it is far from the quickest way to calculate it. I guess your example is fine for educational purposes (though I would have preferred a recursive function

) but it has devastating complexity. A far better technique works in constant time, making use of golden ratio:

double FibN(const int n) {
    const double PHI = 1.61803398874989 // Upper golden root;
    const double RECP_SQRT_5 = 0.447213595499958 // 1/sqrt(5);

    return (pow(PHI, n) - pow(-PHI, -n)) * RECP_SQRT_5;
}

Regards
Admiral

User Rating: 1679 | Rate This User

Report this Post to a Moderator | Link

Kelly G Member since: 7/6/2004 From: Athens, GA, United States

Posted - 10/10/2006 12:07:59 AM

Smooth. I hadn't thought of that method but it makes sense.

User Rating: 1146 | Rate This User

Report this Post to a Moderator | Link

Zahlman Moderator - Game Programming Member since: 1/9/2004 From: Toronto, Canada

Posted - 10/10/2006 1:33:00 AM

Quote:
Original post by TheAdmiral
While the iterative identity you are using is kind of characteristic of the Fibonacci sequence, it is far from the quickest way to calculate it. I guess your example is fine for educational purposes (though I would have preferred a recursive function ) but it has devastating complexity. A far better technique works in constant time, making use of golden ratio:

*** Source Snippet Removed ***
Regards
Admiral

For values of N where fib(N) fits into a 32-bit integer, I would expect the iteration to take less time than all the floating-point arithmetic. Besides, the guy apparently wants to output stats about the ratio at each point in the calculation.

WildJester:
1) Put your source code snippets in [code][/code] (short) or [source][/source] (long) tags appropriately. This stuff is in the FAQ and you really have no excuse.

2) We don't really need to see your real name.

As a general rule, if you post in For Beginners and your code contains the word 'char', you have a bug. std::string roxors teh big one one one one.
"OMG! I'm so happy! I have "1 Friends"!!!" -- coldacid
"Basically whenever you invoke the dread ellipses construct you leave the happy world of type safety." -- SiCrane
"I mean, if you had sex for every time O'Reilly used the word Patriotism you'd be almost as awesome as Chuck Norris." -- tthibault

<triforce101> uh im not a noob i finished the game

User Rating: 1992 | Rate This User

Report this Post to a Moderator | Link

TheAdmiral Member since: 4/15/2004 From: London, United Kingdom

Posted - 10/10/2006 10:23:47 AM

Quote:
Original post by Zahlman
For values of N where fib(N) fits into a 32-bit integer, I would expect the iteration to take less time than all the floating-point arithmetic.

I didn't believe this when I first read it. However, I was surprised to find that fib(46) is the greatest Fibonacci number that fits in a 32 bit integer. Being myself, I further wrote some code to profile it, and proved Zahlman right in the process

.
However, it wasn't completely one-sided. The iterative function is linear, as expected, and it makes a mockery of the floating point function for small values. But the difference tails off as the index reaches 60, and the story changes after 70:

Anyway, I guess it's time for me to let go. The floating method is undeniably better for arbitrarily large indices, but iterative wins the 32-bit battle, particularly when generating the entire sequence.

Regards
Admiral

User Rating: 1679 | Rate This User

Report this Post to a Moderator | Link

Zahlman Moderator - Game Programming Member since: 1/9/2004 From: Toronto, Canada

Posted - 10/10/2006 1:26:03 PM

I'm impressed, actually - you felt compelled to do the research, while I was completely guessing ;)

Seems to me like the pow() operation, and therefore the full FP implementation, should be O(lg N), since it can take advantage of iterative squaring and caching of old values - and the graph does seem to bear that out.

User Rating: 1992 | Rate This User

Report this Post to a Moderator | Link

TheAdmiral Member since: 4/15/2004 From: London, United Kingdom

Posted - 10/10/2006 3:01:02 PM

Quote:
Original post by Zahlman
Seems to me like the pow() operation, and therefore the full FP implementation, should be O(lg N).

I see now. It didn't occur to me at all that pow() could be anything other than O(1). That was a little stupid.
After some research, it seems that pow() is implemented using base-2 exp() and log() (with the logarithm law you'd expect), which are both lg-time operations. So now I also have to retract the claim that my Fib implementation runs in constant time

. Well... at least O(lg n) beats O(n).

Regards
Admiral

User Rating: 1679 | Rate This User

Report this Post to a Moderator | Link

All times are ET (US)

Last Thread Next Thread

Forum Rules:

You may not post new threads
You may post replies
You may not edit your posts
You may not use HTML in your posts

Jump To: