There’s a popular urban legend about Carl Gauss, who may have been the greatest mathematician in history, and was probably a little too sassy for his own good. It goes like this:
In Germany, at the cusp of the 19th century, Master Büttner was fed up with his rowdy pupils. In those days, public schools were sober, single-room affairs crammed with students of all ages — a crucible for chatter. In the hopes of peace and quiet, Büttner sentenced his pupils — among them a young Gauss — to a long, mind-numbing task: adding up all the numbers between 1 and 100.
This kind of drone-like calculation is sometimes called ‘number-crunching’ — and it’s frustrating work. What if you forget a number? Or don’t quite add up 47+48 correctly? You might have to start the whole calculation from the top!
If Gauss and his peers had computers, they’d be laughing, because computers are lean mean number-crunching machines. We’re talking over 100,000 MIPS (million instructions per second)!
So if your teacher assigned you the same dull task… you’d do it the smart way.
STEP 1: Open your favourite web browser (Chrome, Firefox, or Internet Explorer) and navigate to http://repl.it
STEP 2: In the ‘Search for a Language’ box, type ‘Python’, and select it. Python is a lightweight, interactive programming language. In other words, you can spend less time worrying about semi-colons and more time doing fun things, like playing soccer or baking cookies.
STEP 3: Enter the following code (ALGORITHM 1):
number = 100 sum = 0 for i in range(number+1): sum += i print(sum)
(PSST: Make sure you use a tab, or four spaces, in line 4 (sum += i). Since Python doesn’t have a lot of syntax, it’s very finicky about whitespace — if you don’t use that tab correctly, the code won’t run.)
Click the ‘Run’ button near the the top of the screen, and the right-hand console should display this:
An ‘algorithm’ is a series of instructions meant to accomplish a specific task, or solve a specific problem. A recipe is a real-life example of an algorithm: mix flour, sugar, milk, and eggs, bake in the oven for a few minutes, and presto! Cookies appear.
In our summation algorithm, sum is the variable that’s keeping track of the addition. Since we want to add each number between 0 and 100, we’re using a ‘for loop’. The variable ‘i’ will start at 0, and at each iteration of the loop, it’s increased by 1.
So during the first iteration:
sum += 0
During the second iteration:
sum += 1
And during the third iteration:
sum +=2
Which is equivalent to saying:
sum = 0 + 1 + 2
So on and so forth. Since the for loop will execute all the way up to “number+1” (in this case, 100+1), at the end we’ll get:
sum = 0 + 1 + 2 + 3 + 4 + … + 98 + 99 + 100
That last line — print(sum) — displays the result in the console.
STEP 4: Test it with small values to see that it works.
Replace the line number = 100 with something like number = 5.
STEP 5: Now test it with very, very large values. How about 10,000,000? (Hint: You have to enter it without the commas — 10000000)
See how it took a few seconds before the answer popped up in the console? Even though computers can do calculations very, very fast, they’re not instantaneous. If we make them do a lot of calculations — say, 10,000,000 calculations — it’ll take a significant amount of time.
If you ask the computer to do 100,000,000 calculations, it could take over a minute. With larger values, it might take days, or weeks, or years before the computer gives you an answer!
Gauss didn’t have a computer. But moments after Master Büttner finished describing his dreary exercise, and the other students where whittling busily away, Gauss sauntered up to the front of the class and deposited his slate on the Master’s desk — the correct answer etched in white chalk.
Gauss, you see, had discovered a trick.
He realized that if you multiplied the two numbers 100 and 101, and then divided this result by 2, it was the same as adding up all the numbers between 1 and 100.
Let’s try it out:
STEP 6: Replace Algorithm 1 with the following piece of code (ALGORITHM 2):
number = 100 sum = (number * (number+1)) / 2 print(sum)
Run your code and check that the two answers match.
STEP 7: Now, try the very big values again — like 100,000,000. Unlike the first algorithm, this one is still fast. How big can you go before you start to notice a slowdown?
While both paths lead to the same answer, Algorithm 1 runs in ‘linear time’; when the number gets bigger, the code takes longer to complete. Algorithm 2, on the other hand, runs in ‘constant time’. No matter how big the number gets, the code is still only performing one addition, one multiplication, and one division. This makes it the more ‘efficient’ algorithm.
When you’re dealing with very large numbers, it’s important to figure out a fast, clever algorithm — like Gauss did.
Take GPS systems. Figuring out the shortest path between two locations is notoriously complex because there’s so many options to consider. If your GPS was badly programmed, you might have to wait a full half hour before its monotone voice informed you to ‘turn left at the next light’. Not to mention the delays if you took a wrong turn…
Algorithm Design is a specialized branch of computer science that deals with making code faster and smarter. Without it, many of our favourite digital activities — high-resolution video games, efficient streaming, intelligent applications — would be too cumbersome and slow to implement in our daily lives.
There’s a trade-off, of course. Maybe faster means less secure. Maybe smarter means more convoluted.
No algorithm is perfect, which is why designers strive day and night to push the boundaries of what’s possible and discover new and exciting algorithms to make our lives even better.
Learn More
Repl.it Links
https://repl.it/Fy2l/1
https://repl.it/Fypg/0
How to Explain Algorithms to Kids
http://www.tynker.com/blog/articles/ideas-and-tips/how-to-explain-algorithms-to-kids/
What is an Algorithm?
https://kidscodecs.com/what-is-an-algorithm/
http://www.bbc.co.uk/guides/z3whpv4 /a>
