# Help Please Fibonacci Number Program

This topic is 4153 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## 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 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 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

##### Share on other sites
Smooth. I hadn't thought of that method but it makes sense.

##### Share on other sites
Quote:
 Original post by TheAdmiralWhile 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 ***RegardsAdmiral

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 on other sites
Quote:
 Original post by ZahlmanFor 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

##### 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 on other sites
Quote:
 Original post by ZahlmanSeems 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