Fibonacci, the Golden Ratio & Memoization

Let’s begin by defining the two key topics which will be explored in this article:

Firstly, the Fibonacci Sequence is a series of numbers where a given number is found by adding up the two numbers preceding it. The sequence reveals something about the deep laws of the universe, and as such it appears in many places in nature, including things like plants and animals and things like the spirals shapes of galaxies. Because it is found in these places, it has become a topic of fascination for physicists, mathematicians, and programmers alike.

Secondly, “Memoization” is term (or word) coined by Donald Michie (a famous British pioneer in the field of Artificial Intelligence), it’s a programming term, and it means storing the results of function calls which might take time or space to run, and returning a cached result when the same inputs occurs on more than one occasion.

In this article I will begin by describing what the Fibonacci Sequence is and where we find it. Secondly I will explore then the Fibonacci sequence and Golden Ratio. Finally, we will look at how Prof. Michie’s Memoization technique can help us to more quickly find the Nth number which occurs in the Fibonacci Sequence. I will conclude with talking about some places where we can use our knowledge of the sequence to understand other things.

Introduction

Fibonacci was an Italian dude, born in the year 1175 and living until 1250, and it’s fair to say he made some important contributions to Western “mathematics” as we now call it. However, he wasn’t by any means the first person to discover the “Fibonacci” sequence, since the knowlege  seemed to be already known in Italian mathematics. Earlier knowledge of the concept was apparently encoded in Sanskrit Prosody and apparently had a well know status in India many years prior to Fibonacci. Indeed Virahaṅka is associated with the first known description of the “Fibonacci” Sequence (Source: E), this 6th century AD Indian mathematician’s analysis of long and short syllables of Sanskrit prosody reflected this natural numerical sequence.

But it was in Fibonacci’s text Liber Abaci (1202) that he in fact described how the growth of a given Rabbit population (in idealized conditions) would conform to this particular natural sequence.

Let’s look at the Fibonacci sequence: This is a sequence of number which Fibonacci noticed recurring throughout nature and he therefore set out to describe. The sequence looks like: 

and so on. Described mathematically like this:

x_n = x_n-1 + x_n-2

The above equation mathematically describes how that the Nth number in the Fibonacci sequence ( x_n ) equals the number one place behind it in the sequence (x_n-1), plus the number two places behind it in the sequence(x_n-2). However, importantly, we also must note that, in the original version as above, if n == 1 or n == 2 then X_n = 1. Furthermore, if using the “modern version” of the sequence and starting from 0, if n == 1 then Xn = 0, if n == 2 then Xn = 1.

N.B.  The modern version of the Fibonacci (which again is really just the same sequence with a different starting point – it starts at 0) will look like this: 

Describing The Fibonacci Sequence in Code

Python

Below is a naive or brute force approach to finding a number in the Fibonacci sequence:

However, the issue with the above method of calculating the fib number for n, is that it will give us problems as its Big-O time-complexity becomes exponential, specifically O(2ⁿ), as n heads towards infinity, this is because it is recursive but doesn’t cache. To understand further what this means see my article on Big-O Notation.

The reason this is a very inefficient approach is that it repeats the same calculations instead of storing or caching those values that have already been calculated.

To make a better solution, we can turn now to the technique of caching previously worked-out stuff (or caching returned values from function calls) which is the technique we referred to in the introduction to this article: namely memoization. This is the technique we should employ to optimize this type of recursive algorithm. 

To use this memoization explicitly we can do something like:

If we have Python3 installed, we can use the pre-written lru_cache from the functools library to do this for us and make our code a bit cleaner:

In Swift we could do something like this using a Dictionary (hash table):

The time-complexity of our Fibonacci algorithm with memoization implemented becomes O(n), since we’re not doing any more calculations for n = 90 then for n = 30 as we have stored or cached the previous values.

How does this relate to the Golden Ratio? Well, to answer that question let’s look at some python code that looks at the fraction we find by dividing a given fibonacci number by it’s previous number in the fibonacci sequence.

 If we run this code, the out will be:

As we can see from the above outputted number will start to head towards the Golden Ratio as the size of n increases, and on a matlab generated graph this looks like this:

The Golden Ratio or Phi Φ

Roughly = 1.618033988749895

Let’s now look at what we call the Golden Ratio: The Golden Ratio is the actually the same as the ratio of one number in the Fibonacci sequence to its predecessor in the sequence. The uses of the ratio have been various: Artists have employed it to make beautiful things (and we see this in the work of Leonardo da Vinci ). We can also look further and explore the topic of so-called Sacred Geometry (a notion which ascribes symbolic and sacred meanings to certain geometric shapes and proportions). We can also see thus the approximate proportions of the Golden Ratio in objects and structures like the Ark of the Covenant, or The Great Pyramid at Giza, or pretty much any major buildings for that matter.  

The below diagram shows how the Golden Ratio can be represented graphically.

As artists and architects learned about the ratio, they came up with tools to help them use this sacred geometry in their work. An example of such a tool is seen in the rudimentary wooden object or tool pictured below: that artist may use the ratio when drawing, or crafting things on paper or parchment. You can also use the tool below to go about the world and discover the presence of the ratio in the objects we encounter everyday, all around us in the world, and in the universe as a whole. Adjacent to the picture of the tool is a picture of a Parthenon with a graphical overlay showing how it uses the ratio.

Binet’s Formula

Because we know that the ratio of Fibonacci numbers to the previous number in the sequence will start to approach the Golden Ratio, we can actually reverse-engineer a given Fibonacci number just by looking at the number that sit around it in the sequence. For this we can use the Binet Formula.

It’s worth noting however from a coding perspective that although using this method in a programming language can be inaccurate due to rounding errors with floating point approximations of the irrational number square-root-of-5 (Ref#: H). To get closer to accuracy we need to use arbitrary-precision floating-point arithmetic in our code. 

[math]
$$
F_{n} = \frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^{n}
-\left(\frac{1-\sqrt{5}}{2}\right)^{n}\right]
$$
[/math]

OR EQUIVALENTLY:

In Swift this approach would look like this (limited only to the capacity of the Int datatype):

Uses for The Fibonacci Sequence and the Golden Ratio

What can we do with our knowledge of the Fibonacci Sequence and the Golden Ratio? Well, besides being interesting, we can see these patterns emerging in things like markets, where knowing these patterns, and other patterns can help us predict trends in the numbers. Specifically we can look at Levels of Support and Resistance for a particular stock, Trend Changes and Price Targets (Ref#: F). There is also something called, Elliott Wave Theory which is an idea about how human psychology can influence stocks in wave like pattens. Pattens which are strongly linked to Fibonacci patterns where apparently “practitioners commonly use this ratio and related ratios to establish support and resistance levels for market waves”, although it’s far from clear what the exact effectiveness of this technique can be (Ref#: F).

In the world of software development, a often cited example is the use of the Fibonacci Scale in estimating the size of “user stories” in terms of point within Agile methodologies. In these uses each member of the development team will provide their own estimate for each user story, and one manifestation of this type of approach is Planning Poker where the cards come in a fib sequence and each card given one such number.

Indeed, there are actually many more occurrences and applications of the sequence and ratio, but two many to cover in the context of this post, such as the many ways the ratio ties into so many constants and structure of the universe, and its binary nature (Ref#: J).

Conclusion

In conclusion, in this article we have explored the Fibonacci Sequence, we have seen how it is found encoded into the fundamental laws of our universe. We have explored how it is easy to write a basic computer program to find the Nth number in the Fibonacci sequence, but how the use of memoization is key for good algorithmic efficiency here. In addition, we understood that the Golden Ratio can be calculated by dividing numbers in the Fibonacci sequence by their preceding number in the sequence. We also discovered from this that there is a formulaic way of obtaining a Fibonacci number for n using Binet’s formula which can be a good alternative to other methods since it is considered to be a valid way of finding the Nth fibonacci number (although this method can be inaccurate due to rounding errors with floating point logical approximations of the irrational number equal to the square-root-of-5). 

 

References

A: Socratica. (2018). Recursion, the Fibonacci Sequence and Memoization || Python Tutorial || Learn Python Programming . Retrieved from: https://www.youtube.com/watch?v=Qk0zUZW-U_M [Accessed 27 Feb. 2018].

B: “https://www.youtube.com/watch?v=dREpRHgkjsg”

C: https://medium.com/@mvxlr/swift-memoize-walk-through-c5224a558194

D: https://marcosantadev.com/implement-cache-lru-swift/

E: Singh (1985). The So-Called Fibonacci Numbers in Ancient and Medieval India. Historia Mathematica, 12(3), p. 229-244.

F: http://math.bu.edu/people/kost/teaching/MA341/Brendan.pdf

G: https://artofproblemsolving.com/wiki/index.php?title=Binet%27s_Formula

H: https://www.youtube.com/watch?v=Es4Tk0nU1OQ

E: https://www.goldennumber.net/leonardo-da-vinci-golden-ratio-art/

F: https://www.stocktrader.com/2009/05/26/fibonacci-numbers-investors-sequence-elliot-wave-theory/

G: https://proofwiki.org/wiki/Euler-Binet_Formula

H: https://gist.github.com/topher6345/001d11fdf21b5f2f969e

I: http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/lucasNbs.html

J: Quantum Gravity: A New Theory Of Everything. Video retrieved from: https://www.youtube.com/watch?v=_v9eTvlLi-s

K: https://www.youtube.com/watch?v=o3QBgkQi_HA

Originally Published (on wordpress.com): February 27th, 2018

Updated: 11th Feb 2020