The Startup
Published in

The Startup

Golden Ratio: two quantities are in the golden ratio if their ratio is the same as the ratio of their sum to the larger of the two quantities

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.

Recursion tree for fib(4)

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:

Fibonacci closed-form expression, Binet’s formula

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.



Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store