Technology & Computing · Software & algorithms
What an algorithm is
An algorithm is a list of steps exact enough for a machine to follow. See how to write one, how to show it always finishes with the right answer, and why the word now covers looser things.

What you will learn
- Explain what makes a list of steps an algorithm rather than a rough instruction
- Use Euclid's method to find the greatest common divisor of two numbers
- Explain why an algorithm must handle every allowed input, including edge cases
- Explain how an invariant and a shrinking quantity show an algorithm is correct and finishes
Lesson 1 of 4 · 4 min
Turning a vague instruction into exact steps
A recipe says "bake until golden." A cook knows what that means. A machine doesn't, because it can't judge golden, so it never knows when to stop.
An algorithm is a list of steps exact enough to follow with no judgment at all. Every step says precisely what to do, and the list always finishes after a limited number of steps.
Donald Knuth, whose textbooks shaped computer science, listed what that takes. An algorithm starts from inputs and produces outputs that relate to them in a stated way. Each step is basic enough to do with pencil and paper.
So "bake until golden" fails, and "bake at 200 degrees for 25 minutes" passes. Anyone who follows the second version does the same thing, and so would a machine.
The greatest common divisor of two numbers is the largest number that divides both with nothing left over. Euclid described a way to find it in his Elements around 300 BC. It's one of the oldest algorithms still in common use.
Divide the larger number by the smaller and keep the remainder. Then divide the smaller number by that remainder. Repeat until the remainder is zero. The last number you divided by is the answer.
Take 1071 and 462. 1071 divided by 462 is 2, remainder 147. 462 divided by 147 is 3, remainder 21. 147 divided by 21 is 7, remainder 0. So the greatest common divisor is 21.
You can picture it as tiling a 1071 by 462 rectangle with the biggest squares that fit. Then you tile the leftover strip the same way. The last square size that fills its strip exactly is 21.
Try to recallUse Euclid's method to find the greatest common divisor of 84 and 36. What are the steps?
84 divided by 36 is 2, remainder 12. 36 divided by 12 is 3, remainder 0. The remainder is zero, so the last number divided by, 12, is the greatest common divisor.
An algorithm is a finite list of exact steps that turns inputs into a stated output. You can now run Euclid's method. Divide, keep the remainder, and repeat until it's zero.
Lessons in this topic
Turning a vague instruction into exact steps
Learn what separates an algorithm from a rough instruction, and use Euclid's 2,300-year-old method to find the largest number that divides two others.
How to know an algorithm is right every time
See why algorithms break on unusual inputs, and how an invariant and a shrinking number prove a method gives the right answer and always finishes.
Solving a big problem by solving smaller copies
See how a method can solve a problem by calling itself on a smaller version, and how splitting a problem in pieces let a student beat a famous mathematician's guess.
From al-Khwarizmi to the feed
Follow the word algorithm from a scholar in ninth-century Baghdad to today's talk of "the algorithm," and see what that newer sense leaves out.
Three quick stories from this topic
The name behind the word
The word algorithm comes from the name of a ninth-century scholar in Baghdad
Muhammad ibn Musa al-Khwarizmi wrote about calculating with Indian digits around 820. A Latin translation opened "Dixit Algorizmi," thus spoke al-Khwarizmi, and readers made his name into a word for calculation.
Two words from one man
His book Al-Jabr, on solving equations, gave English the word algebra as well.
Lost in Arabic
His arithmetic book's Arabic original is lost. It survives through Latin translations made in the 12th century.
Java's nine-year bug
A bug in Java's binary search sat unnoticed for about nine years
One line found the middle of a list by adding two positions and halving the sum. With about a billion items, that sum outgrew the variable holding it. The same line appeared in a textbook version that had been proved correct.
Proved, still broken
The proof treated numbers as if they could grow as large as needed. Real variables have a ceiling, and a huge list hit it.
Trouble at the edges
Methods tend to fail at the limits of what's allowed, such as empty or enormous lists, because their writers pictured typical inputs.
Karatsuba's week
A student found faster multiplication a week after Kolmogorov guessed none existed
At a 1960 Moscow seminar, Andrey Kolmogorov said schoolbook multiplication couldn't be beaten. Anatoly Karatsuba, 23, split each number in half and built the product from three smaller multiplications instead of four.
Savings that compound
The trick repeats on every half. For two 1,024-digit numbers it cuts about a million single-digit multiplications to about 59,000.
First past the old way
Kolmogorov presented the result at the seminar's next meeting. It was the first method shown to beat schoolbook multiplication as numbers grow.
Sources
- Algorithm, Wikipedia
- Algorithm characterizations, Wikipedia
- Euclidean algorithm, Wikipedia
- Muhammad ibn Musa al-Khwarizmi, Wikipedia
- Algorism, Wikipedia
- Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken, Google Research
- Karatsuba algorithm, Wikipedia
- Divide-and-conquer algorithm, Wikipedia




