logic fails for a big number of finding fibonocci number

Question

I am trying to find whether a given number is fibonocci or not.The logic i am using id 5*n^2+4 or 5*n^2-4 will be a perfect square .The code is as follows

import java.util.*;
import java.math.*;

public class Solution {

public static void main(String [] args){
    Scanner input=new Scanner(System.in);
    int number=input.nextInt();
    int holder[]=new int[number];
    for(int i=0;i<number;i++){
        holder[i]=input.nextInt();
        checkFib(holder[i]);
    }

}

private static void checkFib(int i) {
    // TODO Auto-generated method stub
    long fivePlus=(long) (5*Math.pow(i, 2)+4);
    long fiveMinus=(long)(5*Math.pow(i, 2)-4);
    boolean check=checkSquare(fivePlus,fiveMinus);
    if(check==true){
        System.out.println("IsFibo");
    }else{
        System.out.println("IsNotFibo");
    }

}

private static boolean checkSquare(long fivePlus, long fiveMinus) {
    // TODO Auto-generated method stub
    boolean ret1,ret2;
    if(Math.sqrt(fivePlus)==Math.floor((Math.sqrt(fivePlus)))){
        ret1=true;
    }else{
        ret1=false;
    }
    if(Math.sqrt(fiveMinus)==Math.floor((Math.sqrt(fiveMinus)))){
        ret2=true;
    }else{
        ret2=false;
    }

    return (ret1||ret2);

 }

}

The input format will be 2 // for two test case 5 //5 and 6 representing test data 6 ps:Even though the answers regarding using BigInteger is appreciable ,but i am not looking at big integer as my test data is in the range of long .

http://stackoverflow.com/questions/11878871/determine-whether-n-is-fibonacci-or-not-if-not-find-the-largest-fibonacci-numbe — Vamsi Pavan Mahesh, Jan 18 '14 at 17:38
I don't really see a problem ... I tried with 102334155 and the output was "IsFibo" ... What's the error you are seeing? — Neeraj Krishna, Jan 18 '14 at 17:53

JVMATL · Answer 1 · 2014-01-18T18:04:22.357

1

Java int and long types have size limits. For really huge numbers, look into the BigDecimal class.

Another possibility is you are losing precision because of the conversion to double when using the Math.pow() function. Keep this all integer math by squaring numbers the old-fashioned-way: multiply. (i.e. just do 5*i*i-4)

..and yet another problem is with checkSquare doing the floating point math sand then testing for equality with ==. Find a pure-integer way to verify the square. (or, say, do the square root with the sqrt() function, round to an int, and then square it to see if you get back the original number. (Search stack overflow for 'float' and '==' to see why)

edited Jan 18 '14 at 18:04

answered Jan 18 '14 at 17:30

JVMATL

2,064
15
25

next possibility is your conversion to Double (see edit) – JVMATL Jan 18 '14 at 17:41
`BigInteger` more appropriate when dealing with whole numbers. – Hollis Waite Jan 18 '14 at 17:44
hey, wait If you find power of an integer value the output of it will be a double value with 0 as mantissa . For example if you power an integer number lets say 5, the output will be 5.0 or 25.0 or 125.0 and so on . here mantissa(decimal part) is always 0 . So, I feel It does not loose procession. – Vamsi Pavan Mahesh Jan 18 '14 at 17:53
that's only true until you exceed the number of digits of precision in the mantissa, but it may be true for the range you are working in. The more I think about it, the more I think the problem is with the == comparison in check squares().. – JVMATL Jan 18 '14 at 18:05
The first solution you have mentioned is showing MisMatch error – Vamsi Pavan Mahesh Jan 18 '14 at 18:26
I don't know what you mean: what, precisely is showing a MisMatch error? Can you show the exact line of code and the exect compiler error? (you can edit your question or put it at the bottom..) – JVMATL Jan 18 '14 at 19:02

score 0 · Answer 2 · edited May 23 '17 at 12:14

Recognizing Fibonacci numbers: You need to be able to recognize square numbers quickly and accurately. There's extensive literature on the topic. See, e.g., here: Fastest way to determine if an integer's square root is an integer. However, you have an advantage: you already know the ballpark, i.e., integers near sqrt(5)n. You also know odd or even. You should be able to test in one or two squaring operations.

logic fails for a big number of finding fibonocci number

2 Answers2