Finding if a number is Fibonacci or not? In Java

Question

Problem Definition

Given a number tell if its Fibonacci number or not.

Inputs

Number of Test Cases 1<= T <= 10^10.
T lines follow and each line consists of N integer.

Sample Input

3

5

7

8

Sample Output

IsFibo

IsNotFibo

IsFibo

And my code for this problem is given below

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

public static void main(String[] args) throws IOException {
 /* Enter your code here. Read input from STDIN. Print output to STDOUT */   
 BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 int tc = Integer.parseInt(br.readLine());
 for(int i=0;i<tc;i++)
    {
    int n = Integer.parseInt(br.readLine());
    doThis(n);

    }
}
public static void doThis(int n)
{
  double one = Math.sqrt((5*n*n)+4);

  double two = Math.sqrt((5*n*n)-4);
  if(one % 1 == 0 || two % 1 == 0)
    {
    System.out.println("IsFibo");
    }
  else
    {
    System.out.println("IsNotFibo");


    }
}
}

The reason that i use Math.sqrt((5*n*n)-4) or Math.sqrt((5*n*n)+4) is given in this link www.fq.math.ca/Scanned/10-4/advanced10-4.pdf pagenumber 418.

how ever this is not working for all the cases and most of the cases fail which i don't understand why?

"Thus if n is a Fibonacci number, either 5n^2 + 4 or 5n^2 - 4 is a square." Your "is a square" code looks strange — , Dec 30 '14 at 12:25
checkout http://stackoverflow.com/questions/295579/fastest-way-to-determine-if-an-integers-square-root-is-an-integer — , Dec 30 '14 at 12:26
possible duplicate of [nth fibonacci number in sublinear time](http://stackoverflow.com/questions/1525521/nth-fibonacci-number-in-sublinear-time) — Joe, Dec 30 '14 at 12:36
You are using `== 0` with a `double`. That is unlikely to give you the answer you are expecting due to rounding error. Better to recast your tests to avoid `==`. — rossum, Dec 30 '14 at 12:49

peterremec · Answer 1 · 2014-12-30T13:07:15.160

Try @rossum solution:

int one = (int) Math.sqrt((5*n*n)+4);

int two = (int) Math.sqrt((5*n*n)-4);

Never test double values for equality, it fails (almost) everytime. If you declare:

double one = 1.0;
double two = 1.0;

one might be 1.0000000001 and two might be 1.00000000000000001. You can see that the values are not (completely) the same.

In such cases, you should compare like this:

if(Math.abs(one-two)<0.001){
//do something
}

In your case, I think you should cast double to int as @rossum suggested.

score 0 · Answer 2 · answered Dec 30 '14 at 13:01

d % 1 == 0 is not a completely reliable test for any double d, since some minor inaccuracies from, for example, Math.sqrt, might give you d = 2.000000004 or something rather than 2. Instead you should compare with tolerance, for example d % 1 < 0.001 if d is always positive.

score 0 · Answer 3 · edited Dec 30 '14 at 13:56

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class BasicEmployeeService {

    public static void main(String[] args) throws IOException {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT */
        System.out.println("Enter the number");
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tc = Integer.parseInt(br.readLine());
        for (int i = 0; i < tc; i++) {
            int n = Integer.parseInt(br.readLine());
            doThis(n);

        }

    }

    public static void doThis(int n) {
        long square = n * n;
        double one = Math.sqrt((5 * square) + 4);

        double two = Math.sqrt((5 * square) - 4);
        if (one % 1 == 0 || two % 1 == 0) {
            System.out.println("IsFibo");
        } else {
            System.out.println("IsNotFibo");

        }
    }
}

score 0 · Accepted Answer · answered Dec 31 '14 at 11:12

0

The actual answer is to change the int type to double while reading the value as

Double tc = Double.parseDouble(br.readLine());

and pass double to the function doThis

public static void doThis(Double n) {

now it works perfectly fine

answered Dec 31 '14 at 11:12

user2860954

177
2
24

Finding if a number is Fibonacci or not? In Java

4 Answers4