Fibonacci Swift playground
Suppose you are standing in front of a staircase which has n stairs. You are allowed to go up either one or two stairs at a time. What will be the total number of distinct ways you can reach to the top?
If we knew the number of ways to get to the both n-1 and n-2 , then the total ways to get to the point n would be just sum these two values. This is actually same as calculating the nth number of the fibonacci series. Here I tried to present different approaches to fibonacci problem which includes algorithm comparison, and discussion around time and space complexity.
Recursive approach
We can start with recursive approach. Let’s say we already know what all previous numbers are, so it goes without saying that the current number is sum of last two (the top down approach).
func fib(_ n: Int) -> Int {
guard n > 1 else { return n }
return fib(n-1) + fib(n-2)
}Time Complexity: O(2^n)
Space Complexity: O(2^n)
The problem with this solution is we keep recomputing the same subproblems over and over again. In other words, our algorithm does a lot of repeated work. This algorithm grows exponentially, it takes a lot of effort especially when n is large.
Iterative approach
This approach comes from the same idea but with small tweak. If we store all the values in an array for future use, we avoid the redundancy work. The function is directly returning the result from the memo array whenever the function is called again.
func fib(_ n: Int) -> Int {
var fibs: [Int] = [1, 1]
(2...n).forEach { i in
fibs.append(fibs[i - 1] + fibs[i - 2])
}
return fibs.last!
}Time Complexity: O(n)
Space Complexity: O(n)
With this little change to the algorithm, we made a huge optimization. As an example for n = 45 it takes 90 steps (whereas over a billion with our recursive approach), roughly 10 million times faster.
Iterative approach — Optimized
We don’t really need to store the whole array. All we need to have is the last two values:
func fib(_ n: Int) -> Int {
var a = 1
var b = 1
guard n > 1 else { return a }
(2...n).forEach { _ in
(a, b) = (a + b, a)
}
return a
}Time Complexity: O(n)
Space Complexity: O(1)
Inside the for loop, we are assigning (beauty of the tuples) the new values to both a and b. If you noticed the equation (a, b) = (a + b, a) is the exact definition of the golden ratio.
Power of Matrix approach
Let’s assume matrix M as:
In order to have the nth Fibonacci number, the matrix M has to be multiplied to itself n-1 times, and form the n-1th power:
Let’s say we have an awesome method multiply that multiplies two matrixes and returns a resultant matrix, the algorithm will be as simple as this:
func fib(_ n: Int) -> Int {
guard n > 2 else { return n }
let M = [[1, 1], [1, 0]]
var result: [[Int]] = M
(1..<n).forEach { _ in result = multiply(result, M) }
return result[0][0]
}Time Complexity: O(n)
Space Complexity: O(1)
Power of Matrix approach — Optimized
In order to form the nth power of the matrix M, we don’t need to multiply it to itself n times. Here is the idea, let’s say you want to compute 5⁸, the primitive approach is to multiply 5 to itself 8 times. The better approach is to repeatedly square and doubles the exponent:
5² = 25
25² = 5⁴ = 625
625² = 5⁸ = 390,625
As you see this squaring approach uses many fewer multiplications than the primitive approach (three vs. eight, in other word reduced logarithmic). The same idea works for matrices:
func fib(_ n: Int) -> Int {
var M = [[1, 1], [1, 0]]
guard n > 2 else { return n }
power(&M, n)
return M[0][0]
}func power(_ matrix: inout [[Int]], _ n: Int) {
guard n > 1 else { return }
power(&matrix, n/2)
matrix = multiply(matrix, matrix)
if n % 2 != 0 {
let M = [[1, 1], [1, 0]]
matrix = multiply(matrix, M)
}
}
Time Complexity: O(log n)
Space Complexity: O(log n) , because of recursion stack
In the code snippet above the power function tries to compute the nth power of M by squaring the(n/2)th power. However if n is odd, rounding down n/2 and squaring that power of M results in the (n-1)th power, which multiplying one more factor of M will makes up that single factor. This is for sure the fastest and most optimized algorithm we can use to get the nth fibonacci number.
You might be asking about inout keyword or & sign, these are not really playing any significant role in our algorithm. They just let us pass the matrix reference through the recursion stack for the performance purposes. If you are interested to learn more, check out Value Types vs. Reference Types in Swift.
If you have any suggestions, please let me know, and feel free to leave your comment. You can find all the code for this post here.
This post is to Alex Smirnoff who is always motivating
This story is published in The Startup, Medium’s largest entrepreneurship publication followed by 281,454+ people.
Subscribe to receive our top stories here.
