-
Notifications
You must be signed in to change notification settings - Fork 0
/
Fibonacci.java
executable file
·212 lines (185 loc) · 6.8 KB
/
Fibonacci.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
public class Fibonacci
{
private static final BigInteger BIGINTTWO = new BigInteger("2");
private static final int NUMRUNS = 1000;
private static final int TINYNUMS = 10;
private static final int SMALLNUMS = 25;
private static final int MEDIUMNUMS = 1000;
private static final int LARGENUMS = 10000;
private static final int HUGENUMS = 100000;
private static final int GINORMNUM = 1000000;
public static void main(String[] args)
{
run(TINYNUMS, NUMRUNS);
run(SMALLNUMS, NUMRUNS);
run(MEDIUMNUMS, NUMRUNS);
run(LARGENUMS, NUMRUNS);
run(HUGENUMS, NUMRUNS);
run(GINORMNUM, NUMRUNS);
}
private static void run(int numSize, int runNums)
{
LinkedList<Long> recursive = new LinkedList<Long>();
LinkedList<Long> memo = new LinkedList<Long>();
LinkedList<Long> lastTwo = new LinkedList<Long>();
LinkedList<Long> doubling = new LinkedList<Long>();
for (int i = 0; i < runNums; i++)
{
long before;
long after;
if (numSize <= SMALLNUMS) // Would take too long otherwise
{
BigInteger number = BigInteger.valueOf(numSize);
before = System.nanoTime();
fibRecursive(number);
after = System.nanoTime();
recursive.add(after-before);
}
if (numSize <= HUGENUMS)
{
before = System.nanoTime();
fibMemo(numSize);
after = System.nanoTime();
memo.add(after-before);
}
before = System.nanoTime();
fibLastTwo(numSize);
after = System.nanoTime();
lastTwo.add(after-before);
before = System.nanoTime();
fibDoubling(numSize);
after = System.nanoTime();
doubling.add(after-before);
}
System.out.println("\n---------------------------------------");
System.out.println("Fibonacci Number Index: " + numSize);
System.out.println("---------------------------------------\n");
System.out.printf("Method\t\t"
+ "Min\t\t"
+ "Max\t\t"
+ "Sum\t\t"
+ "Average (All in milliseconds)\n\n");
if (numSize < SMALLNUMS) // It takes FAR too long otherwise.
{
double minRecursive = (double)Collections.min(recursive) / 1000000.0;
double maxRecursive = (double)Collections.max(recursive) / 1000000.0;
double sumRecursive = 0;
for (long value : recursive)
{
sumRecursive += (double)value / 1000000.0;
}
double averageRecursive = sumRecursive / (double)recursive.size();
System.out.printf("Recursive\t"
+ "%8f\t"
+ "%8f\t"
+ "%8f\t"
+ "%8f\n\n",
minRecursive,
maxRecursive,
sumRecursive,
averageRecursive);
}
if (numSize <= HUGENUMS)
{
double minMemo = (double)Collections.min(memo) / 1000000.0;
double maxMemo = (double)Collections.max(memo) / 1000000.0;
double sumMemo = 0;
for (long value : memo)
{
sumMemo += (double)value / 1000000.0;
}
System.out.printf("Memo\t\t"
+ "%8f\t"
+ "%8f\t"
+ "%8f\t"
+ "%8f\n\n",
minMemo,
maxMemo,
sumMemo,
sumMemo / (double)memo.size());
}
double minLastTwo = (double)Collections.min(lastTwo) / 1000000.0;
double maxLastTwo = (double)Collections.max(lastTwo) / 1000000.0;
double sumLastTwo = 0;
for (long value : lastTwo)
{
sumLastTwo += (double)value / 1000000.0;
}
System.out.printf("LastTwo\t\t"
+ "%8f\t"
+ "%8f\t"
+ "%8f\t"
+ "%8f\n\n",
minLastTwo,
maxLastTwo,
sumLastTwo,
sumLastTwo / (double)lastTwo.size());
double minDoubling = (double)Collections.min(doubling) / 1000000.0;
double maxDoubling = (double)Collections.max(doubling) / 1000000.0;
double sumDoubling = 0;
for (long value : doubling)
{
sumDoubling += (double)value / 1000000.0;
}
System.out.printf("Doubling\t"
+ "%8f\t"
+ "%8f\t"
+ "%8f\t"
+ "%8f\n",
minDoubling,
maxDoubling,
sumDoubling,
sumDoubling / (double)doubling.size());
}
public static BigInteger fibRecursive(BigInteger number)
{
if (number.compareTo(BigInteger.ONE) <= 0)
return number;
return fibRecursive(number.subtract(BigInteger.ONE))
.add(fibRecursive(number
.subtract(BIGINTTWO)));
}
public static BigInteger fibMemo(int number)
{
ArrayList<BigInteger> solutions = new ArrayList<>();
solutions.add(0, BigInteger.ZERO);
solutions.add(1, BigInteger.ONE);
for (int i = 2; i <= number; i++)
{
solutions.add(solutions.get(i-2).add(solutions.get(i-1)));
}
return solutions.get(number);
}
public static BigInteger fibLastTwo(int number)
{
BigInteger fib1 = BigInteger.ZERO;
BigInteger fib2 = BigInteger.ONE;
for (int i = 1; i <= number; i++)
{
BigInteger tmpFib = fib1;
fib1 = fib1.add(fib2);
fib2 = tmpFib;
}
return fib1;
}
public static BigInteger fibDoubling(int number)
{
BigInteger a = BigInteger.ZERO;
BigInteger b = BigInteger.ONE;
for (int i = 31 - Integer.numberOfLeadingZeros(number); i >= 0; i--) {
BigInteger d = a.multiply((b.shiftLeft(1)).subtract(a)); // F(2n)
b = a.multiply(a).add(b.multiply(b)); // F(2n+1)
a = d;
if (((1 << i) & number) != 0) { // advance by one
BigInteger c = a.add(b);
a = b;
b = c;
}
}
return a;
}
}