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

Masih Tabrizi
Jan 6, 2018 · 5 min read

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

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

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

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

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

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.

The Startup

Get smarter at building your thing. Join The Startup’s +724K followers.

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

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