ビンツ式のN番目のフィボナッチは正確ではない70

Question

ビンツ式でn番目のフィボナッチを実装しようとしていますが、何らかの理由でビネットバージョンの統計値が70フィボナッチ数後の実際の再帰バージョンから逸脱しています。ここで

は

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 

私の推測では、黄金比を保持しているダブル第70数で表示し始め精度を制限していることである出力は次のようになりますコード

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))); 
    } 
} 

です。 .. これは正しいです？または私はここに何かが欠けている？

Answer 1

使用のjava.math.BigDecimalクラス丸め問題を回避するには：

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(); 
}