fibonacci

[josh2two]

Does anyone know the code on how to test a number to see if it is a fibonacci number?

I figured out how to find fibonacci positions like the 10th fibonacci number is 55.

But I cannot figure out how to test a number that a user enters to see if it is a fibonacci number.

Anyone want to help me with this code!

I'm using Dev C++!!!

[redhead]

Show us what you've got, and might I suggest reading up on fibonacci numbers in Aspects of Combinatorics - A wide-ranging introduction by Victor Bryant, it's pages 109, 113 and 121.
On page 109 theres even the formula for calculating F(n) when n > 1, since this dosn't support math, I'll try and rewrite it in C code

#include <stdio.h>
#include <math.h>

int show_fibonacci_sequence(int max)
{
  int i;
  if(max < 0)
    return -1; /* unable to have fibonacci of negative values */
  printf("[0%s", max >0? ", 1": "");
  for(i=2; i <= max; ++i)
    printf("%s %d", (!(i%10) && i < max)? ",\n":",",
              (int)floor(1.0/sqrt(5.0)
			      *(pow((1.0 + sqrt(5.0))/2.0, i) 
				- pow((1.0 - sqrt(5.0))/2.0, i)
				)
			      )
	   );
  printf("]\n");
  return 0;
}

int main(){
  show_fibonacci_sequence(8);
  return 0;
}

[josh2two]

not sure what the difference is between c and c++, but i'm using c++ code so i'm not sure how to convert that into c++

[josh2two]

see what i need is a program that a user puts a number in (ex. 55) and it tells them if it is fibonacci or not. i think i need to use a bool function.

[Valmont]

You'd better be good in math then.

The first and natural way is to use the properties of Binet's formula.
So you need to find out about the binet formula or ask your teacher to explain. If you truly understand it then the algorithm for your original assignment is a piece of cake!!!

Second method:
If the number is a Gessel product, then it is also a fibonacci number.
So you need to find out how to test for a Gessel product.
Ask your teacher what a Gessel product is if you don't know what it means. Otherwise you're going to have a difficult time. I've just finished writing an algorithm but first you need to prove you studied. Otherwise I'm just an anwering machine and I don't like that .

[redhead]

If you considder my code segment and modify it a bit, you'd get what you want, something like:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

/* fibonacci(num)
 *        return:
 *           -1 : num unfitted for fibonacci
 *            1 : num is a fibonacci number
 *            0 : num is not a fibonacci number
 */  
int fibonacci(int num)
{
  int fib=0, i;
  if(num < 0)
    return -1; /* unable to have fibonacci of negative values */
  if(!num || num == 1)
    return 1;
  for(i=2;fib < num; ++i)
    {
      fib = (int)floor(1.0/sqrt(5.0)
		       *(pow((1.0 + sqrt(5.0))/2.0, i) 
			 - pow((1.0 - sqrt(5.0))/2.0, i)
			 )
		       );
      if(fib == num)
	return 1;
    }
  return 0;
}

int main(int argc, char** argv){
  int j, f;
  if(argc < 2)
    printf("Usage: %s [x y z ...]\n", argv[0]);
  for(j=1; j < argc; ++j){
    f = fibonacci(atoi(argv[j]));
    if(f < 0)
      printf("Error %s can't be a fibonacci number\n", argv[j]);
    else
      if(f)
	printf("%s is a fibonacci number\n", argv[j]);
      else
	printf("%s is NOT a fibonacci number\n", argv[j]);
  }
  return 0;
}

But else, use what Valmont suggested, read up on your math in this area, the teacher is bound to have some good references when they put an assignment together like this one.

But true, if you don't understand the math involved here, then this is a tricky assigment and you're bound to miss vital parts in it, so please please read up on your math, else whatever we throw at you will be lost.

[josh2two]

ok first this is the code for the switch statement, the fibonacci is the 3rd case in my program

case 3:
     {               
     cin.ignore(255,'\n');
     system("cls");
              
     cout << "Test to see if a number is a fibonacci number."
         << "\n\nPlease enter an integer:  ";
     cin  >> n;

               while (!cin)// for bad data
               { cout << "Invalid response idiot, you entered " << n << ", try again.";
               cin.clear();
               cin.ignore(255,'\n');
               system ("pause");
               cout <<"\n\n\nPlease enter an integer:   ";
               cin  >> n;
               } // end of error checking

    fibonacci_print(n);
    
    
    system ("PAUSE");
    system ("CLS");
    break;
    }


Then in my seperate file that defines the fibonacci function:

unsigned int fibonacci(int x) 
{
    double phi=(1+sqrt(5))/2;
    double n=(pow(phi,x+1)-pow(1-phi,x+1))/sqrt(5);
	return static_cast<unsigned int>(n);
}



// Function fibonacci_print prints out n'th Fibonacci number
void fibonacci_print(int n) 
{
    cout << n << "th Fibonacci number is " << fibonacci(n) << endl;
}

[josh2two]

ok first this is the code for the switch statement, the fibonacci is the 3rd case in my program

[case 3:
{
cin.ignore(255,'\n');
system("cls");

cout << "Test to see if a number is a fibonacci number."
<< "\n\nPlease enter an integer: ";
cin >> n;

while (!cin)// for bad data
{ cout << "Invalid response idiot, you entered " << n << ", try again.";
cin.clear();
cin.ignore(255,'\n');
system ("pause");
cout <<"\n\n\nPlease enter an integer: ";
cin >> n;
} // end of error checking

fibonacci_print(n);


system ("PAUSE");
system ("CLS");
break;
}]


Then in my seperate file that defines the fibonacci function:

[unsigned int fibonacci(int x)
{
double phi=(1+sqrt(5))/2;
double n=(pow(phi,x+1)-pow(1-phi,x+1))/sqrt(5);
return static_cast<unsigned int>(n);
}



// Function fibonacci_print prints out n'th Fibonacci number
void fibonacci_print(int n)
{
cout << n << "th Fibonacci number is " << fibonacci(n) << endl;
}]

[Valmont]

Here is your hint to check whether "n" is a fibonacci number:

- Write the inverse fibonacci function (logarithms!).
- Write the normal fibonacci function.
- If n == fibonacci(inverse_fibonacci(n)) then we have prove that "n" is a fibonacci number.

Cool huh? All you need to do is to learn you logarithms and properties of powers obviously. Can you do that?

[josh2two]

ok i think i made this assignment way harder than it really is. Since we know that the fibonacci sequence is 0 1 1 2 3 5 8 13 ......... , can't i just use a while loop and a bool function and make a counter that uses i and j. Since the fibonacci sequence is just the sum of the previous 2 numbers.

[DJMaze]

int n = 5032443; // fibonacci number ?

int no1 = 0, no2 = 1;
int i = no1+no2;
while (n < i) {
    no1 = no2;
    no2 = i;
    i = no1+no2;
}
bool fibonacci = (n == i);

[Valmont]

Not a single loop is needed if you used my hint on Binet (inverse Fibonacci):

Let the inverse fibonacci be defined as (invfib):
int(round((log(n) + log(5)/2) / log(phi)))
then the test for fibonacci can be expressed in this term plus a fibonacci algorithm:
fibonacci(invfib(n))

Looking back, it wasn't that hard was it? This takes only 15 minutes of study if you payed attention during the algebra classes. Any college student can do it. Next time try to do it yourself when I give a hint. The spinoffs go way beyond coding!

Good luck !

[redhead]

fibonacci(invfib(n))

I dont quite follow the logic here, if you have a number thats not a fibonacci number and run the inverse on it, you'll end up with a value thats a double and feed that to the fibonacci function will result in the orriginal number, unless you strive to have both the inverse and fibonacci function return values of type int's, every given number will eventualy prove to be a fibonacci number, when given this approach.

[Valmont]

You obviously need to include the tests. I only showed what is relevant math wise.
So the test should be

iif (n == fibonacci(invfib(n)))
{
   //n is a fibonacci number
}
else
{
   //n never was a fibonacci number
}

a) And obviously n needs to be bigger then 1 when running this test.

[redhead]

Then considder this, we have a sequence L: [4, 5] we want to test if a number N is in L, thus we create a function to result with numbers within L ie

int make_number(int x){ return (int)sqrt(x);}

as our testing function we create an inverse function ie:

int inv_number(int x){ return (int)pow(x, 2);}

When we want to test if number N is within L we see by your logic in this fasion:

if(N == make_number(inv_number(N)))
    return true;
else
    return false;

Do you see why this would fail ?
If I were to have N=3 it would take the squareroot of (3 by the power of 2), which is 3, which is our N thus by your logic it should be within our L, yet L only contains 4 and 5.
Simply because the operations performed in the orriginal function to create numbers within L, will be counterbalanced by the inverse operations provided by our inverse function. Thus leaving us with the orriginal number which then proves to be within the desired quantity nomatter what the number we test for is.

I know this might sound a bit out there, but thats what following the simple laws of mathmatics tells me this will result in, I would like to see some prof that it is different in your case.