Sign in to follow this  
WildJester

Help Please Fibonacci Number Program

Recommended Posts

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!

Share this post


Link to post
Share on other sites
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;
}

Share this post


Link to post
Share on other sites
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 [wink]) 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

Share this post


Link to post
Share on other sites
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 [wink]) 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.

Share this post


Link to post
Share on other sites
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 [rolleyes].
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

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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 [sad]. Well... at least O(lg n) beats O(n).

Regards
Admiral

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this