'Making Fibonacci faster [duplicate]
I was required to write a simple implementation of Fibonacci's algorithm and then to make it faster.
Here is my initial implementation
public class Fibonacci {
public static long getFibonacciOf(long n) {
if (n== 0) {
return 0;
} else if (n == 1) {
return 1;
} else {
return getFibonacciOf(n-2) + getFibonacciOf(n-1);
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner (System.in);
while (true) {
System.out.println("Enter n :");
long n = scanner.nextLong();
if (n >= 0) {
long beginTime = System.currentTimeMillis();
long fibo = getFibonacciOf(n);
long endTime = System.currentTimeMillis();
long delta = endTime - beginTime;
System.out.println("F(" + n + ") = " + fibo + " ... computed in " + delta + " milliseconds");
} else {
break;
}
}
}
}
As you can see I am using System.currentTimeMillis() to get a simple measure of the time elapsed while computed Fibonacci.
This implementation get rapidly kind of exponentially slow as you can see on the following picture
So I've got a simple optimisation idea. To put previous values in a HashMap and instead of re-computing them each time, to simply take them back from the HashMap if they exist. If they don't exist, we then put them in the HashMap.
Here is the new version of the code
public class FasterFibonacci {
private static Map<Long, Long> previousValuesHolder;
static {
previousValuesHolder = new HashMap<Long, Long>();
previousValuesHolder.put(Long.valueOf(0), Long.valueOf(0));
previousValuesHolder.put(Long.valueOf(1), Long.valueOf(1));
}
public static long getFibonacciOf(long n) {
if (n== 0) {
return 0;
} else if (n == 1) {
return 1;
} else {
if (previousValuesHolder.containsKey(Long.valueOf(n))) {
return previousValuesHolder.get(n);
} {
long newValue = getFibonacciOf(n-2) + getFibonacciOf(n-1);
previousValuesHolder.put(Long.valueOf(n), Long.valueOf(newValue));
return newValue;
}
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner (System.in);
while (true) {
System.out.println("Enter n :");
long n = scanner.nextLong();
if (n >= 0) {
long beginTime = System.currentTimeMillis();
long fibo = getFibonacciOf(n);
long endTime = System.currentTimeMillis();
long delta = endTime - beginTime;
System.out.println("F(" + n + ") = " + fibo + " ... computed in " + delta + " milliseconds");
} else {
break;
}
}
}
This change makes the computing extremely fast. I computes all the values from 2 to 103 in no time at all and I get a long overflow at F(104) (Gives me F(104) = -7076989329685730859, which is wrong). I find it so fast that **I wonder if there is any mistakes in my code (Thank your checking and let me know please) **. Please take a look at the second picture:
Is my faster fibonacci's algorithm's implementation correct (It seems it is to me because it gets the same values as the first version, but since the first version was too slow I could not compute bigger values with it such as F(75))? What other way can I use to make it faster? Or is there a better way to make it faster? Also how can I compute Fibonacci for greater values (such as 150, 200) without getting a **long overflow**? Though it seems fast I would like to push it to the limits. I remember Mr Abrash saying 'The best optimiser is between your two ears', so I believe it can still be improved. Thank you for helping
[Edition Note:] Though this question adresses one of the main point in my question, you can see from above that I have additionnal issues.
Solution 1:[1]
If you need to compute n th fibonacci numbers very frequently I suggest using amalsom's answer.
But if you want to compute a very big fibonacci number, you will run out of memory because you are storing all smaller fibonacci numbers. The following pseudocode only keeps the last two fibonacci numbers in memory, i.e. it requires much less memory:
fibonacci(n) {
if n = 0: return 0;
if n = 1: return 1;
a = 0;
b = 1;
for i from 2 to n: {
sum = a + b;
a = b;
b = sum;
}
return b;
}
Analysis
This can compute very high fibonacci numbers with quite low memory consumption: We have O(n) time as the loop repeats n-1 times. The space complexity is interesting as well: The nth fibonacci number has a length of O(n), which can easily be shown:
Fn <= 2 * Fn-1
Which means that the nth fibonacci number is at most twice as big as its predecessor. Doubling a number in binary is equivalent with a single left-shift, which increases the number of necessary bits by one. So representing the nth fibonacci number takes at most O(n) space. We have at most three successive fibonacci numbers in memory which makes O(n) + O(n-1) + O(n-2) = O(n) total space consumption. In contrast to this the memoization algorithm always keeps the first n fibonacci numbers in memory, which makes O(n) + O(n-1) + O(n-2) + ... + O(1) = O(n^2) space consumption.
So which way should one use?
The only reason to keep all lower fibonacci numbers in memory is if you need fibonacci numbers very frequently. It is a question of balancing time with memory consumption.
Solution 2:[2]
Get away from the Fibonacci recursion and use the identities
(F(2n), F(2n-1)) = (F(n)^2 + 2 F(n) F(n-1), F(n)^2+F(n-1)^2)
(F(2n+1), F(2n)) = (F(n+1)^2+F(n)^2, 2 F(n+1) F(n) - F(n)^2)
This allows you to compute (F(m+1), F(m)) in terms of (F(k+1), F(k)) for k half the size of m. Written iteratively with some bit shifting for division by 2, this should give you the theoretical O(log n) speed of exponentiation by squaring while staying entirely within integer arithmetic. (Well, O(log n) arithmetic operations. Since you will be working with numbers with roughly n bits, it won't be O(log n) time once you are forced to switch to a large integer library. After F(50), you will overflow the integer data type, which only goes up to 2^(31).)
(Apologies for not remembering Java well enough to implement this in Java; anyone who wants to is free to edit it in.)
Solution 3:[3]
- Fibonacci(0) = 0
- Fibonacci(1) = 1
- Fibonacci(n) = Fibonacci(n - 1) + Fibonacci(n - 2), when n >= 2
Usually there are 2 ways to calculate Fibonacci number:
Recursion:
public long getFibonacci(long n) { if(n <= 1) { return n; } else { return getFibonacci(n - 1) + getFibonacci(n - 2); } }This way is intuitive and easy to understand, while because it does not reuse calculated Fibonacci number, the time complexity is about
O(2^n), but it does not store calculated result, so it saves space a lot, actually the space complexity isO(1).Dynamic Programming:
public long getFibonacci(long n) { long[] f = new long[(int)(n + 1)]; f[0] = 0; f[1] = 1; for(int i=2;i<=n;i++) { f[i] = f[i - 1] + f[i - 2]; } return f[(int)n]; }This Memoization way calculated Fibonacci numbers and reuse them when calculate next one. The time complexity is pretty good, which is
O(n), while space complexity isO(n). Let's investigate whether the space complexity can be optimized... Sincef(i)only requiresf(i - 1)andf(i - 2), there is not necessary to store all calculated Fibonacci numbers.The more efficient implementation is:
public long getFibonacci(long n) { if(n <= 1) { return n; } long x = 0, y = 1; long ans; for(int i=2;i<=n;i++) { ans = x + y; x = y; y = ans; } return ans; }With time complexity
O(n), and space complexityO(1).
Added: Since Fibonacci number increase amazing fast, long can only handle less than 100 Fibonacci numbers. In Java, we can use BigInteger to store more Fibonacci numbers.
Solution 4:[4]
Precompute a large number of fib(n) results, and store them as a lookup table inside your algorithm. Bam, free "speed"
Now if you need to compute fib(101) and you already have fibs 0 to 100 stored, this is just like trying to compute fib(1).
Chances are this isn't what this homework is looking for, but it's a completely legit strategy and basically the idea of caching extracted further away from running the algorithm. If you know you're likely to be computing the first 100 fibs often and you need to do it really really fast, there's nothing faster than O(1). So compute those values entirely out of band and store them so they can be looked up later.
Of course, cache values as you compute them too :) Duplicated computation is waste.
Solution 5:[5]
Here is a snippet of code with an iterative approach instead of recursion.
Output example:
Enter n: 5
F(5) = 5 ... computed in 1 milliseconds
Enter n: 50
F(50) = 12586269025 ... computed in 0 milliseconds
Enter n: 500
F(500) = ...4125 ... computed in 2 milliseconds
Enter n: 500
F(500) = ...4125 ... computed in 0 milliseconds
Enter n: 500000
F(500000) = 2955561408 ... computed in 4,476 ms
Enter n: 500000
F(500000) = 2955561408 ... computed in 0 ms
Enter n: 1000000
F(1000000) = 1953282128 ... computed in 15,853 ms
Enter n: 1000000
F(1000000) = 1953282128 ... computed in 0 ms
Some pieces of results are omitted with ... for a better view.
Code snippet:
public class CachedFibonacci {
private static Map<BigDecimal, BigDecimal> previousValuesHolder;
static {
previousValuesHolder = new HashMap<>();
previousValuesHolder.put(BigDecimal.ZERO, BigDecimal.ZERO);
previousValuesHolder.put(BigDecimal.ONE, BigDecimal.ONE);
}
public static BigDecimal getFibonacciOf(long number) {
if (0 == number) {
return BigDecimal.ZERO;
} else if (1 == number) {
return BigDecimal.ONE;
} else {
if (previousValuesHolder.containsKey(BigDecimal.valueOf(number))) {
return previousValuesHolder.get(BigDecimal.valueOf(number));
} else {
BigDecimal olderValue = BigDecimal.ONE,
oldValue = BigDecimal.ONE,
newValue = BigDecimal.ONE;
for (int i = 3; i <= number; i++) {
newValue = oldValue.add(olderValue);
olderValue = oldValue;
oldValue = newValue;
}
previousValuesHolder.put(BigDecimal.valueOf(number), newValue);
return newValue;
}
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
while (true) {
System.out.print("Enter n: ");
long inputNumber = scanner.nextLong();
if (inputNumber >= 0) {
long beginTime = System.currentTimeMillis();
BigDecimal fibo = getFibonacciOf(inputNumber);
long endTime = System.currentTimeMillis();
long delta = endTime - beginTime;
System.out.printf("F(%d) = %.0f ... computed in %,d milliseconds\n", inputNumber, fibo, delta);
} else {
System.err.println("You must enter number > 0");
System.out.println("try, enter number again, please:");
break;
}
}
}
}
This approach runs much faster than the recursive version.
In such a situation, the iterative solution tends to be a bit faster, because each recursive method call takes a certain amount of processor time. In principle, it is possible for a smart compiler to avoid recursive method calls if they follow simple patterns, but most compilers don’t do that. From that point of view, an iterative solution is preferable.
UPDATE:
After Java 8 releases and Stream API is available one more way is available for calculating Fibonacci.
Checked with JDK 17.0.2.
Code:
public static BigInteger streamFibonacci(long n) {
return Stream.iterate(new BigInteger[]{BigInteger.ONE, BigInteger.ONE},
p -> new BigInteger[]{p[1], p[0].add(p[1])})
.limit(n)
.reduce((a, b) -> b)
.get()[0];
}
Test output:
Enter n (q for quit): 5
F(5) = 5 ... computed in 2 ms
Enter n (q for quit): 50
F(50) = 1258626902 ... computed in 0 ms
Enter n (q for quit): 500
F(500) = 1394232245 ... computed in 3 ms
Enter n (q for quit): 500000
F(500000) = 2955561408 ... computed in 4,343 ms
Enter n (q for quit): 1000000
F(1000000) = 1953282128 ... computed in 19,280 ms
The results are pretty good.
Keep in mind that ... just cuts all following digits of the real numbers.
Solution 6:[6]
Having followed a similar approach some time ago, I've just realized there's another optimization you can make.
If you know two large consecutive answers, you can use this as a starting point. For example, if you know F(100) and F(101), then calculating F(104) is approximately as difficult (*) as calculating F(4) based on F(0) and F(1).
Calculating iteratively up is as efficient calculation-wise as doing the same using cached-recursion, but uses less memory.
Having done some sums, I have also realized that, for any given z < n:
F(n)=F(z) * F(n-z) + F(z-1) * F(n-z-1)
If n is odd, and you choose z=(n+1)/2, then this is reduced to
F(n)=F(z)^2+F(z-1)^2
It seems to me that you should be able to use this by a method I have yet to find, that you should be able use the above info to find F(n) in the number of operations equal to:
the number of bits in n doublings (as per above) + the number of 1 bits in n addings; in the case of 104, this would be (7 bits, 3 '1' bits) = 14 multiplications (squarings), 10 additions.
(*) assuming adding two numbers takes the same time, irrelevant of the size of the two numbers.
Solution 7:[7]
Here's a way of provably doing it in O(log n) (as the loop runs log n times):
/*
* Fast doubling method
* F(2n) = F(n) * (2*F(n+1) - F(n)).
* F(2n+1) = F(n+1)^2 + F(n)^2.
* Adapted from:
* https://www.nayuki.io/page/fast-fibonacci-algorithms
*/
private static long getFibonacci(int n) {
long a = 0;
long b = 1;
for (int i = 31 - Integer.numberOfLeadingZeros(n); i >= 0; i--) {
long d = a * ((b<<1) - a);
long e = (a*a) + (b*b);
a = d;
b = e;
if (((n >>> i) & 1) != 0) {
long c = a+b;
a = b;
b = c;
}
}
return a;
}
I am assuming here (as is conventional) that one multiply / add / whatever operation is constant time irrespective of number of bits, i.e. that a fixed-length data type will be used.
This page explains several methods of which this is the fastest. I simply translated it away from using BigInteger for readability. Here's the BigInteger version:
/*
* Fast doubling method.
* F(2n) = F(n) * (2*F(n+1) - F(n)).
* F(2n+1) = F(n+1)^2 + F(n)^2.
* Adapted from:
* http://www.nayuki.io/page/fast-fibonacci-algorithms
*/
private static BigInteger getFibonacci(int n) {
BigInteger a = BigInteger.ZERO;
BigInteger b = BigInteger.ONE;
for (int i = 31 - Integer.numberOfLeadingZeros(n); i >= 0; i--) {
BigInteger d = a.multiply(b.shiftLeft(1).subtract(a));
BigInteger e = a.multiply(a).add(b.multiply(b));
a = d;
b = e;
if (((n >>> i) & 1) != 0) {
BigInteger c = a.add(b);
a = b;
b = c;
}
}
return a;
}
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|---|
| Solution 1 | |
| Solution 2 | abligh |
| Solution 3 | |
| Solution 4 | MushinNoShin |
| Solution 5 | |
| Solution 6 | |
| Solution 7 |