N-th fibonacci with Binets formula not accurate after 70

Question

Trying to implement nth fibonacci with Binets formula, but for some reason binet version stats to deviate from the actual recursive version after 70th fibonacci number.

Here is the code

public class NthFib {

   public static void main(String[] args) {
      for (int i = 0; i < 100; i++) {
         String s1 = toUnsignedString(fib(i));
         String s2 = toUnsignedString(fibGoldenRatio(i));
         System.out.println(i + " : " + s1 + " | " + s2 + (s1.equals(s2)?" ":" not the same"));
      }

   }

   static final Map<Integer, Long> cache = new HashMap<>();

   private static long fib(int n) {

      if (n < 0) {
         return -1;
      }

      if (n == 0) {
         return 0;
      }

      if (n == 1) {
         return 1;
      }

      return cache.computeIfAbsent(n, k -> fib(k - 1) + fib(k - 2));
   }

   static final double GR = (1 + Math.sqrt(5)) / 2;
   static final double NGR = -GR + 1;

   // Binet algorithm
   private static long fibGoldenRatio(int n) {

      if (n < 0) {
         return -1;
      }

      return round(1 / sqrt(5) * (pow(GR, n) - pow(NGR, n)));
   }
}

the output will be as follows

0 : 0 | 0 
1 : 1 | 1 
2 : 1 | 1 
3 : 2 | 2 
4 : 3 | 3 
5 : 5 | 5 
6 : 8 | 8 
7 : 13 | 13 
8 : 21 | 21 
9 : 34 | 34 
10 : 55 | 55 
11 : 89 | 89 
12 : 144 | 144 
13 : 233 | 233 
14 : 377 | 377 
15 : 610 | 610 
16 : 987 | 987 
17 : 1597 | 1597 
18 : 2584 | 2584 
19 : 4181 | 4181 
20 : 6765 | 6765 
21 : 10946 | 10946 
22 : 17711 | 17711 
23 : 28657 | 28657 
24 : 46368 | 46368 
25 : 75025 | 75025 
26 : 121393 | 121393 
27 : 196418 | 196418 
28 : 317811 | 317811 
29 : 514229 | 514229 
30 : 832040 | 832040 
31 : 1346269 | 1346269 
32 : 2178309 | 2178309 
33 : 3524578 | 3524578 
34 : 5702887 | 5702887 
35 : 9227465 | 9227465 
36 : 14930352 | 14930352 
37 : 24157817 | 24157817 
38 : 39088169 | 39088169 
39 : 63245986 | 63245986 
40 : 102334155 | 102334155 
41 : 165580141 | 165580141 
42 : 267914296 | 267914296 
43 : 433494437 | 433494437 
44 : 701408733 | 701408733 
45 : 1134903170 | 1134903170 
46 : 1836311903 | 1836311903 
47 : 2971215073 | 2971215073 
48 : 4807526976 | 4807526976 
49 : 7778742049 | 7778742049 
50 : 12586269025 | 12586269025 
51 : 20365011074 | 20365011074 
52 : 32951280099 | 32951280099 
53 : 53316291173 | 53316291173 
54 : 86267571272 | 86267571272 
55 : 139583862445 | 139583862445 
56 : 225851433717 | 225851433717 
57 : 365435296162 | 365435296162 
58 : 591286729879 | 591286729879 
59 : 956722026041 | 956722026041 
60 : 1548008755920 | 1548008755920 
61 : 2504730781961 | 2504730781961 
62 : 4052739537881 | 4052739537881 
63 : 6557470319842 | 6557470319842 
64 : 10610209857723 | 10610209857723 
65 : 17167680177565 | 17167680177565 
66 : 27777890035288 | 27777890035288 
67 : 44945570212853 | 44945570212853 
68 : 72723460248141 | 72723460248141 
69 : 117669030460994 | 117669030460994 
70 : 190392490709135 | 190392490709135 
71 : 308061521170129 | 308061521170130 not the same
72 : 498454011879264 | 498454011879265 not the same
73 : 806515533049393 | 806515533049395 not the same

My guess is that the double that holds golden ratio has limited accuracy which starts to show up at 70th number... Is this correct? or i'm missing something here?

https://docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.html — stark, Jan 30 '17 at 14:31
See http://stackoverflow.com/questions/15065088/upper-limits-for-fibonnacci — GhostCat, Jan 30 '17 at 14:41

Matthieu Saleta · Accepted Answer · 2017-01-30T14:47:46.467

3

Use java.math.BigDecimal class to avoid rounding problem :

static final BigDecimal SQRT_5 = BigDecimal.valueOf(Math.sqrt(5));
static final BigDecimal GR = (BigDecimal.ONE.add(SQRT_5).divide(BigDecimal.valueOf(2));
static final BigDecimal NGR = GR.negate().add(BigDecimal.ONE);

// Binet algorithm
private static long fibGoldenRatio(int n) {

  if (n < 0) {
     return -1;
  }

  return BigDecimal.ONE.divide(SQRT_5).multiply((GR.pow(n).substract(NGR.pow(n)))).toBigInteger().longValue();
}

edited Jan 30 '17 at 14:47

answered Jan 30 '17 at 14:33

Matthieu Saleta

1,388
1
11
17

i hesitated to do that as i didnt know how to do those math operations with big decimal... there should be some implementation out of standard library i believe. I think i'll just use something like that and if this 70 number goes higher then this assumption was correct... – vach Jan 30 '17 at 14:37
i just wrote it by editing my post. But i haven't used any IDE so it might be unperfect ^^ – Matthieu Saleta Jan 30 '17 at 14:49
it still will fail at 70th number, i think youre loosing precision doing Math.sqrt(5), which is irrational number so computing high precision version of that shouldnt be as simple as that :) Tomorrow I'll try doing high precision sqrt and see if we get more accurate than 70... – vach Jan 30 '17 at 14:59
1

you can pick an algorithme to compute sqrt with BigDecimal here : http://stackoverflow.com/questions/13649703/square-root-of-bigdecimal-in-java – Matthieu Saleta Jan 30 '17 at 15:07

N-th fibonacci with Binets formula not accurate after 70

1 Answers1