konstantin konstantin - 7 months ago 17
Java Question

Fibonacci in java

I am trying to code in java fibonacci algorithm. I am trying to face the problems with the integer and long size. My simply code is the following which works until a limit for n:

public static long f(int n) {
if (n == 1 || n == 2)
return 1;
else {
long value = f(n-2) + f(n-1);
return value;
}
}


If in my main I ll give 50 for example my code will be crushed, I am guessing due to the size of the outcome. I ve got also another approach which I am struggle to understand it, which is the following:

private static long[] cache = new long[60];

public static long f(int n) {
if (n == 1 || n == 2)
return 1;
else if (cache[n] > 0)
return cache[n];
else {
long value = f(n-2) + f(n-1);
cache[n] = value;
return value;
}
}


With this approach everything works fine whatever is the n, my issue is that I cannot get the difference.

Answer

By "crushed" you mean that the computation runs very long. The reason is that the same call is made many times. If you add this to your method:

static long count;
public static long f(int n) {
    count++;
    ...

you'll see how many times the method is executed. For f(50), it is actually calling the method 25,172,538,049 times, which runs in 41 seconds in my machine.

When you cache the result of previous invocations, called memoization, you eliminate all the redundant calls, e.g. f(40) = f(39) + f(38), but f(39) = f(38) + f(37), so f(38) is called twice. Remembering the result of f(38) means that subsequent invocation has the answer immediately, without having to redo the recursion.

Without memoization, I get this:

 n           f(n)           count       time(ns)
== ============== =============== ==============
 1              1               1          6,273
 2              1               1            571
 3              2               3            855
 4              3               5          1,141
 5              5               9          1,425
 6              8              15          1,140
 7             13              25          1,996
 8             21              41          2,851
 9             34              67          7,413
10             55             109         16,536
11             89             177          8,839
12            144             287         19,103
13            233             465         21,098
14            377             753         11,405
15            610           1,219          5,703
16            987           1,973          9,979
17          1,597           3,193         21,099
18          2,584           5,167         32,788
19          4,181           8,361         35,639
20          6,765          13,529         57,307
21         10,946          21,891         91,521
22         17,711          35,421        147,687
23         28,657          57,313        237,496
24         46,368          92,735        283,970
25         75,025         150,049        331,583
26        121,393         242,785        401,720
27        196,418         392,835        650,052
28        317,811         635,621      1,053,483
29        514,229       1,028,457      1,702,679
30        832,040       1,664,079      2,750,745
31      1,346,269       2,692,537      4,455,137
32      2,178,309       4,356,617     12,706,520
33      3,524,578       7,049,155     11,714,051
34      5,702,887      11,405,773     19,571,980
35      9,227,465      18,454,929     30,605,757
36     14,930,352      29,860,703     51,298,507
37     24,157,817      48,315,633     84,473,965
38     39,088,169      78,176,337    127,818,746
39     63,245,986     126,491,971    208,727,118
40    102,334,155     204,668,309    336,785,071
41    165,580,141     331,160,281    543,006,638
42    267,914,296     535,828,591    875,782,771
43    433,494,437     866,988,873  1,429,555,753
44    701,408,733   1,402,817,465  2,301,577,345
45  1,134,903,170   2,269,806,339  3,724,691,882
46  1,836,311,903   3,672,623,805  6,010,675,962
47  2,971,215,073   5,942,430,145  9,706,561,705
48  4,807,526,976   9,615,053,951 15,715,064,841
49  7,778,742,049  15,557,484,097 25,427,015,418
50 12,586,269,025  25,172,538,049 41,126,559,697
Comments