CODEWITHSUNDEEP
java
Vled
Vled

Reputation: 95

Java double to int convertion changes sign of result

I tried to calculate a series of the N first fibonacci numbers using Binets Formula.

Every result i get is correct until F47 where the result is NEGATIVE.

This is my result : -1323752223
And heres the expected result : 2971215073

I really think the problem occures during the double to int conversion

Source Code:

 import java.lang.Math;

class fibonacci{
  public static int NthFibonacci(int n){
    double fi = 1.61803398875;
    int fb = (int)Math.round((Math.pow(fi,n) - Math.pow(1-fi,n))/Math.sqrt(5));
    return fb;
  }

  public static void FibonacciSeries(Integer n){
    for(int i = 0; i < n; i++){
      System.out.println(NthFibonacci(i) + " ");
    }
  }  
  public static void main(String[] args) {
    FibonacciSeries(50);
  }
}

Upvotes: 0

Views: 103

Answers (4)

Stephen C
Stephen C

Reputation: 718906

The real explanation for the behavior of the version in your question giving a negative number is a bit subtle.

At F47, this expression

(Math.pow(fi, n) - Math.pow(1 - fi, n)) / Math.sqrt(5)

will give you 2.971215073009069E9 ... which is close to the desired 2971215073.

The problem arises when you call Math.round(2.971215073009069E9). This returns a long - 2971215073L. But then you cast the result of the round call to an int, and it all goes pear-shaped.

Casting a long to an int will just lop off the top 32 bits ... and that results in a meaningless number.

If we modify fibonacci to return a long instead of an int, we get correct results up to F55. F56 and F57 are off by 1. F58 is off by 2.

What is happening now is that we are running into the problem that double (64-bit IEEE floating point) has only about 13.5 decimal digits of precision. The rounding error incurred in the computation of the intermediate floating point value for F56 larger that 0.5 ... so the rounded value is then incorrect.

The computed fibonacci numbers continue to get increasingly inaccurate until you get to F93, where the (modified) fibonacci method returns Long.MAX_VALUE.

To get correct values for very large Fibonacci numbers:

  • we need to use BigInteger to represent the numbers,
  • we need to do the computations using BigDecimal with sufficient precision, and (maybe)
  • we need to use a more accurate value for phi.

Or we need to use the recurrence relationship to compute the numbers.

The 2 take-aways from all of this are:

  • casting a long to an int is a lossy conversion, and
  • floating point arithmetic is inexact and ... tricky.

Upvotes: 2

Vled
Vled

Reputation: 95

Ok so i found a decent fix.

I used a Geometrical version of Binets rule which you can find here : Binets Geometrical Rule

I also used long instead of int so now I can accurately calculate up to F70. F71 is wrong by a digit and after that it just builds up.

New Source Code :

import java.lang.Math;

class fibonacci{
  public static long NthFibonacci(int n){
    double a = (1/Math.sqrt(5))*Math.pow(2, n);
   
    double radians1 = Math.toRadians(36.0);
    double radians2 = Math.toRadians(108.0);
    
    double b = Math.pow(Math.cos(radians1), n) - Math.pow(Math.cos(radians2), n);

    long fb = (long) Math.round(a*b);
    return fb;
  }

  public static void FibonacciSeries(int n){
    for(int i = 0; i < n; i++){
      System.out.println( i + " : " +  NthFibonacci(i));
    }
  }  
  public static void main(String[] args) {
    FibonacciSeries(100);

  }
}

Upvotes: 0

Louis Wasserman
Louis Wasserman

Reputation: 198133

2971215073 is too big to be represented as an int at all. The maximum value of an int -- Integer.MAX_VALUE -- is 2^31 - 1, or 2147483647.

Upvotes: 1

John
John

Reputation: 136

I think that the problem does not have something to do with the double conversion.

int can store numbers that can be represented by 32 bits. This means the highest number integer can represents is 2.147.483.647.

The F47 is breaking this limit and results in an bit-overflow, so it starts at -2.147.483.68 and adds the rest of your 2971215073 - 2147483647 to it. -1323752223 is the outcome.

Use a long (64bit) instead of an int and you should be good :)

Upvotes: 1

Related Questions