By Arnold Kasselar
Whenever one hears the word ‘algorithm’, there may be visions of modern Artificial Intelligence which is poised to conquer humanity.
Remember this?
Thankfully, the reality is much more benign, and our lives have, in fact, vastly improved by countless algorithms.
Since good old ancient history days, humanity has grappled with recognising underlying patterns and reoccurring events in the chaotic world.
The human mind is singularly well suited for establishing relationships, and it pulls together strands from seemingly disjointed and unrelated events, and weaves them into a tapestry of experience.
This opaque world, through patient observation, has slowly revealed itself to be a series of discrete, causal steps. Combining an elementary series of repeatable steps allowed our ancestors to survive against overwhelming odds.
Recipes and processes for sowing, harvesting, cooking, and making medicines were diligently passed down from generation to generation, becoming increasingly refined and complex with each permutation.
From these fragile beginnings, the recipes slowly evolved through the Babylonian and Egyptian civilisations.
For example, methods for factorisation and the calculation of square root became invaluable to early construction and taxation. Through conquest and assimilation, the Greeks added a unique blend of mystical and mathematical recipes.
Pythagoras was not only known for his famous theorems on geometry and harmony; he even had certain eccentric views eating beans!
The famous theorem of Pythagoras was later proven by Euclid, who also introduced the greatest common divisor.
The birth of algorithms
In the 9th century, the Persian mathematician Al-Khwarizmi’s writings introduced the western world to linear and quadratic equations and his Latinised name Algoritmi became the origin to what we recognise today as Algorithms.
Thinkers such as Gaus and Newton introduced differentiation and integration which eventually formalised into the modern notion of an algorithm by Alan Turing, known for the Turing machine, the logical forerunner of the computer.
The current definition of an algorithm is a sequence of steps which allow you to solve a particular task. The formal definition adds the following constraints:
- It should be finite. (Solutions which require an approximation due to number of steps involved are known as heuristics)
- It should have well-defined instructions (It should be unambiguous)
- It should be effective (It solve the task at hand)
Our modern lives are permeated with algorithms. Much like how a recipe tells you how to bake a cake and the ingredients required, an algorithm helps you search, sort, browse, and buy them on GoMart. And a driver partner is assigned to deliver the ingredients to your house — Again, an algorithm finds the driver partner.
Remembering one of the many things that help us build our #SuperApp
We at Gojek are geeks for ancient theorems and algorithms we use in our daily life. And the Sieve of Eratosthenes is a famous ancient algorithm used for finding all prime numbers up to any given limit. Let’s just say, it’s one of the many historically significant algorithms that make Gojek’s existence easier.
Prime numbers play an important role in computing and have several applications such as:
- Public key cryptography (Here’s an example)
- Hash tables
- Pseudorandom number generators
- Check digits
To find all the prime numbers less than or equal to a given integer ‘n’ by Eratosthenes’ method:
- Create a list of consecutive integers from 2 through n: (2, 3, 4,.…, n)
- Initially, let p equal to 2, the smallest prime number
- Enumerate the multiples of p by counting to n from 2p in increments of p, and mark them in the list (these will be 2p, 3p, 4p, etc; the p itself should not be marked). The rationale is that all multiples are not prime numbers and therefore can be safely eliminated from the list
- Find the first number greater than p in the list that is not marked. If there was no such number, stop. Otherwise, let p now equal this new number (which is the next prime), and repeat from step 3.
When the algorithm terminates, the numbers remaining not marked in the list are all the primes below n.
See the Pen Sieve of Eratosthenes by Arnold Kesselaar (@arnold-kesselaar) on CodePen.
Stay tuned to know more on algorithms that are both a part of history books and an app’s codebase. 🖖
Looking for blogs on how we build our #SuperApp? Check out our blogs.
View open positions here.
