Perfect square in fibonacci sequence?

Question

Create a program to find out the first perfect square greater than 1 that occurs in the Fibonacci sequence and display it to the console.

I have no output when I enter an input.

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

int PerfectSquare(int n);
int Fibonacci(int n);

main()
{
    int i;
    int number=0;

    int fibNumber=0;
    int psNumber=0;


    printf("Enter fibonacci number:");
    scanf("%i",&number);


    fibNumber = Fibonacci(number);

    psNumber = PerfectSquare(fibNumber);

    if(psNumber != 0){
        printf("%i\n",psNumber);
    }
}



int PerfectSquare(int n)
{

    float root = sqrt(n);
    if (n == ((int) root)*((int) root))
        return root;
    else
        return 0;
}

int Fibonacci(int n){
    if (n==0) return 0;
    if (n==1) return 1;
    return( Fibonacci(n-1)+Fibonacci(n-2) );
}

Answer 1

Luke is right. If your input is n, then the Fibonacci(n) returns the (n+1)th Fibonacci number. Your program check whether (number +1)th is perfect square or not actually.

If you enter 12, then there is output. Because the 13th Fibonacci number is 144. And it is perfect square. PS: print fibNumber instead of psNumber.

        printf("%i\n", fibNumber);

Answer 2

Right now you're only calculating one Fibonacci number and then testing whether it's a perfect square. To do this correctly you'll have to use a loop.

Answer 3

First suggestion is to get rid of the recursion to create fib numbers. You can use 2 variables and continually track the last 2 fib numbers. They get added something like:

fib1=0;fib2=1;
for(i=3;i<MAXTOCHECK;i++)
{
    if(fib1<fib2)
        fib1+=fib2;
    else
        fib2+=fib1;
}

What is nice about this method is that first you can change you seeds to anything you want. This is nice to find fib like sequences. For example Lucas numbers are seeded with 2 and 1. Second, you can put your check for square inline and not completely recalculate the sequence each time.

NOTE: As previously mentioned, your index may be off. There is some arbitrariness of indexing fib numbers from how it is initially seeded. This can seen if you reseed with 1 and 1. You get the same sequence shifted by 1 index. So be sure that you use a consistent definition for indexing the sequence.