Euler

Leonhard Euler was one of the great mathematicians of all time, and arguably the most prolific. (Only Paul Erdős has published more papers, but Euler published more pages.) Euler's greatest contributions were to number theory, but he also did important work in algebra, calculus, geometry, and probability, as well as in the applied fields of acoustics, artillery, astronomy, finance, mechanics, navigation, and optics.

Euler's influence on the history of mathematics can best be illustrated by a listing of all of the topics in math that bear his name. This article would take me years to write if I were to try to explain all of these topics, and I could hardly do a good job of it. Instead I'd like to write about a few of the things that Euler considered "distractions." As well as being a prolific mathematician, Euler was a prolific puzzle solver and writer (is it any wonder that Project Euler bears his name?). A few of his distractions have had a deeper impact on mathematics than even Euler himself may have predicted they would.

Thirty-six Officers Problem

Arrange 36 officers in a 6x6 square so that one from each of six regiments appears in each row, and one from each of six ranks appears in each column. The problem is equivalent to finding two mutually orthogonal Latin squares of order six.

Euler conjectured that the Thirty-six Officers Problem had no solution when he first proposed it between 1779 and 1782 (accounts vary), but his conjecture wasn't proven until 1901, by Gaston Tarry. The more than century-long search for a proof led to important developments in combinatorics.

Seven Bridges of Königsberg

Perhaps the best known of the puzzles analyzed and solved by Euler, the Seven Bridges of Königsberg Problem was first posed by the curious citizens of Königsberg (now Kaliningrad, Russia). The town of Königsberg featured a pair of islands in the river Pregel. Seven bridges crossed the Pregel, connecting different parts of the town (see the map below).

The problem posed by the citizens of Königsberg was whether or not it was possible to walk across all seven bridges without crossing any bridge more than once. No one had been able to find a path that fit both conditions, but was such a path possible?

In 1736, Euler published a paper titled Solutio problematis ad geometriam situs pertinentis (The solution of a problem relating to the geometry of position) in which he gave a solution to the Seven Bridges of Königsberg. In order for a path traversing each bridge exactly once to exist, Euler said, either one of two conditions must be met. If the path were to begin and end at the same point, each land mass would need to have an even number of bridges connected to it. If the path were allowed to begin at one land mass and end at another, those two land masses could have an odd number of connecting bridges, while all the other land masses must have an even number of connecting bridges. The two paths described in Euler's paper would eventually take the names Eulerian circuit and Eulerian path, respectively.

Since the Königsberg bridges did not meet the criteria outlined by Euler, a walk that involved exactly one crossing of each bridge was impossible. Euler's paper was important not because it satisfied the curiosity of the townfolk of Königsberg, but because it laid the groundwork for the branches of mathematics now known as graph theory and topology.

Publications in Euler's later life, and after his death

When he lost the use of his right eye in 1738, Euler said "Now I will have less distraction." This proved prophetic, as his rate of publication subsequently increased. This productivity gain wasn't an isolated incident, as his rate of publication increased again after he lost sight in his left eye in 1766.

Euler died only moments after calculating the orbit of Uranus on September 18, 1783, at the age of 76. It took another 47 years after his death for all of the math that Leonhard Euler wrote during his lifetime to finally be published.


Notes
For a deeper look into the life of one of history's most fascinating mathematicians, see Euler: The Master of Us All.

This is a programming blog, so I'm assuming if you've read this far you've previously heard of Project Euler. If you haven't, I'm sure you'll have fun there.

I'd like to thank Jeff Moser for influencing my decision to write about Euler in a comment he made to my post on Gauss.

Learn Faster

No, this post isn't about speed reading. In the spirit of speed reading, though, I'll make this post mercifully short.

In my last post on programming languages I said that you should learn one language really well before you start branching out into other languages. Understanding programming concepts at a deep level is more important than learning the syntax of many different languages, but it can also help you learn new languages more quickly too.

Once you're at the point where you're ready to learn a new language, what do you do? Do you pick up a copy of "Learn Blub in 10 Minutes a Day" and slog through 24 boring chapters about the syntax of a new language? Or do you spend an entire year going through SICP, watching the video lectures, and doing the exercises? (I keep meaning to do that.)

No matter which path to enlightenment you choose, I have a quick tip that will help you get through any programming book faster. It allows you to apply concepts from languages you already know to the new language that you're learning. Ready to hear what it is? Here you go:

Do the problems at the end of each chapter first, then go back through and read the chapter. If you can't actually do the problems yet, at least read them and try to understand what they're asking.

This method works for two reasons. First, reading the questions and exercises at the end of the chapter gives you more accurate information about what's important in that chapter than even the title and section headings. If you read a question about while loops, for example, you're going to be paying attention for that topic when you read through the chapter. Second, it tells you what you already know, and can skip over. If you read a question about while loops, for example, you know that you can skim that chapter quickly or skip it altogether because you're already familiar with the concept.

This is the method I use when I need to learn a language in a weekend so I can use it in my project on Monday. It really works, but don't take my word for it. I know you have a Sam's book hidden away somewhere so no one will catch you reading it. Don't be ashamed. Okay, maybe a little shame is in order, but maybe if you get through it fast enough, no one will catch you.

Many Languages or One?

This question comes up all the time: "Should you learn many different programming languages or stick to just one?" Many programmers will jump on this one with a quick answer. Of course you should learn many languages if you want to be a great software developer. We hear this advice so often that it requires no proof or explanation.

The first time I read the "learn many languages" theory it was in The Pragmatic Programmer: From Journeyman to Master:

Learn at least one new language every year. Different languages solve the same problems in different ways. By learning several different approaches, you can help broaden your thinking and avoid getting stuck in a rut. Additionally, learning many languages is far easier now, thanks to the wealth of freely available software on the Internet.

Of course this is good advice if, like the subtitle says, you're a journeyman programmer looking to become a master. Is this the same advice we should give to everyone, though? What about beginning programmers? I'm not so sure.

Generally speaking, beginning programmers fall into two categories:

1. College students
2. Self-taught programmers

For the purpose of this discussion I don't think it really matters which group you fall into (despite what I said before). If you're a college student, you probably don't have much choice but to learn the syntax of 6-8 different programming languages in your first couple of years of school. That shouldn't hurt you, because you won't learn much depth on more than one or two of them. If you're self-taught, you probably have more control over how many languages you learn.

Let's take a look at what you should concentrate on when learning a programming language:

1. Basic syntax (data types, variables, operators, conditionals, loops)
2. String manipulation
3. Compound data types (arrays, linked lists, hash tables)
4. Basic algorithms and libraries
   
5. File input and output
6. Processing files (plain text, HTML, XML)
7. Error handling
   
8. Paradigm-specific details (procedural, object-oriented, functional)
   
9. Managing memory (manual vs. garbage collected)
10. Multi-threading
11. Database access
12. Network communications

The list could go on, but I think it's just about everything you should know about a language before you can claim (for example, on your resume) that you know that language. Most good books on a given programming language will include a chapter or two on most, if not all of these topics. But you can't just read one book from cover to cover and say you know a programming language. You have to do the exercises and write some real code (at least a few projects) before you can make that claim. That takes some time.

Most college courses aren't organized to teach you everything you need to know about a language, either. A 10-15 week college course will either touch lightly on several of the topics in the list above, or it will go very deeply into one or two of them. You might take several courses before you've done enough projects in one programming language to really know that language well. Consequently, it takes a couple of years of college to get a really deep knowledge of any one programming language.

Many supporters of the "one language per year" doctrine will say that learning a new language is good because it forces you to think about problems in a different way. This is just a new way of saying "think outside the box." This is almost always good for experienced programmers. Learning new languages will help stimulate you to find better solutions in your main language.

However, "one language per year" is almost certainly bad advice for a beginning programmer. You don't need to start thinking about new ways of doing things if you don't understand the old ones. Learning your first programming language to the depth necessary to solve many different real-world problems will take you more than one year. It won't help you to learn the basic syntax of two languages if you can't solve problems in either one.

My final advice to beginning programmers is this: You should give your first language 2-3 years to really take hold before you branch out into other languages. If you want to be a good programmer you have to know how to do a lot of different things in the main language you work in. Problem solving skills are certainly important, but you need to be able to implement a solution to a problem. If you spend the first few years of your programming career learning the basic syntax of many different languages, you won't have the depth you need to solve real-world problems in any of them.

Summing a Sequence

In yesterday's post about Karl Gauss, I recounted an anecdote about how Gauss, at the age of 10, found a quick way to sum the numbers from 1 to 100. (It's the second paragraph. I'll wait.) Today I want to compare the solution that Gauss came up with to a seemingly more direct solution to the same problem.

Young Gauss' classmates probably added each number in the sequence to a running total. A programmer might solve the problem in much the same way using a loop.

int total = 0;
for(int n = 1; n <= 100; ++n) {
    total += n;
}

This solution works well for small values of n if you're using a computer, but if you're a young child with a slate and some chalk, young Gauss' solution is clearly superior. Even using a computer this solution won't be very efficient if the value of n gets large enough (what is the sum of the first googol integers, for example), since the time complexity of this solution is linear to the size of the input, or O(n), in more formal terms.

In the sequence sum problem, the "n" in O(n) represents the number of integers the students had to sum. In more abstract terms, we say that n is the size of the input to the function. Another way of looking at it is that the naive algorithm will always take more time to solve when given a larger input, because the number of integers you have to add together increases.

Gauss hit upon a much better algorithm for solving this problem. Many of you probably recognize the triangle numbers from a high-school or college algebra class you took:

1 = 1
1 + 2 = 3
1 + 2 + 3 = 6
1 + 2 + 3 + 4 =10
1 + 2 + 3 + 4 + 5 = 15
1 + 2 + 3 + 4 + 5 + 6 = 21
1 + 2 + 3 + 4 + 5 + 6 + 7 = 28
...

These are exactly the numbers you're calculating when you add up all the integers from 1 to some number. You might also remember that there's a simple formula for calculating the nth triangle number.

$T_n = n(n + 1) / 2$

Testing the formula out on a case we already know, we get

$T_{100} = 100 \times 101 / 2 = 5050$

Like magic it works!

Actually, it's not magic at all. I haven't really proven anything by showing that the formula works for one value, but you can read the proof by induction to see why it will work for all natural numbers.

This is exactly the same formula that Gauss had hit upon. Remember he had

$50 \times 101 = 5050$

which, for n = 100 is nothing more than our triangle number formula, slightly rearranged.

$(n / 2)(n + 1) = T_n$

The time complexity of calculating T(n) using the formula is constant, or O(1). No matter how big a number you insert for n, you still have to do one addition (an increment, really), one division, and one multiplication. The amount of time it takes to calculate $T_{10}$ is the same as the amount of time it takes to calculate $T_{10,000,000,000}$.

So what can we learn from all of this? The first thing you should learn (if you're a programmer) is that loops are always suspect. I'm not saying anything outrageous here, like "all loops are bad," but I will say that if you have a simple loop in your code that does something very predictable with a numerical sequence, there might be a way to replace it with a much simpler formula. Second, it's surprising how much you can learn from a 10 year old kid. Of course, it helps an awful lot if that 10 year old is Karl Friedrich Gauss.

Note: I'd like to thank Tim Kington for proofreading an initial draft of this post. Any technical errors are all his fault.

Gauss

Karl Friedrich Gauss was a German mathematician whose career spanned the 18th and 19th centuries. He was well known in his time as the "Prince of Mathematics" and as the "greatest mathematician since antiquity," but he's largely unknown today (except by mathematicians, both professional and amateur).

Maybe the most well-known anecdote about Gauss is one that happened when he was just a boy. When Gauss was in school at age 10, his teacher, perhaps needing a quiet half hour, gave his class the problem of adding all the integers from 1 to 100. Gauss immediately wrote down the answer on his slate (this would have been in the year 1787). He had quickly noticed that the sum (1 + 2 + 3 + ... + 100) could be rearranged to form the pairs (1 + 100) + (2 + 99) + (3 + 98) + ... + (50 + 51), and that there were 50 pairs each equaling 101. This reduced the problem to the simple product 50 x 101 = 5050.

The fact that Gauss isn't as well-known as scientific giants, such as Archimedes, Newton, Einstein, and Hawking, is curious, since his accomplishments equal (some might say surpass) even those great scientific minds. Consider the following accomplishments:

• In 1796, at the age of 19, Gauss proved the constructability of a heptadecagon (a regular polygon with 17 sides) using only a straghtedge and a compass. Greek philosophers had believed this construction was possible, but a proof escaped them. Note that Guass proved the construction was possible without actually providing the steps necessary. The first explicit construction of a heptadecagon wasn't given until 1800, by Johannes Erchinger. Gauss was so proud of the proof of the construction that he requested the shape be placed on his tombstone. The stonemason refused, stating that the shape would have been indistinguishable from a circle.

• In 1799, in his doctoral dissertation, Gauss provided a proof for what is now known as the Fundamental Theorem of Algebra, which states that every polynomial has at least one root that is a complex number. Gauss would go on to provide four separate proofs of this theorem throughout his career.

• In 1801, Gauss had an Annus Mirabilis of his own. In that year, proved the Fundamental Theorem of Arithmetic (that any positive integer greater than 1 can be represented as the product of prime numbers in exactly one way), systematized the study of number theory with the publication of Disquisitiones Arithmeticae, and proved that every number is the sum of at most three triangle numbers. In the same year, he developed the method of least squares fitting and used it to calculate an accurate orbit of the asteroid Ceres (now classified as a dwarf planet) from only three data points.

• In 1809, Gauss published Theoria Motus, his massive treatise on celestial mechanics, which is still in print today. In writing Theoria Motus, Gauss analyzed astronomical data using normal distributions, which are also referred to as Gaussian distributions after Gauss' definition of their probability density function.

• In 1818, Gauss invented the heliotrope, an instrument that uses a mirror to reflect sunlight over great distances. Gauss used the device to aid him in the land survey of the Kingdom of Hanover.

• In 1833, together with Wilhelm Weber, Gauss built the first electromagnetic telegraph used for regular communication, in Göttingen, Germany. This accomplishment is often attributed (by many Americans) to Samuel Morse, who independently developed and patented an electrical telegraph in the U.S. in 1837.

• Gauss lived and worked by the personal motto "pauca sed matura," or "few but ripe." Consequently, he published only a small fraction of his work. Years after his death, publication of his diary and letters confirmed that Gauss was the earliest pioneer of non-Euclidean Geometry, which is normally (and rightly) attributed to Bolyai and Lobachevsky (the two men developed non-Euclidean geometry independently from Gauss, and one another).

Taken individually, any of these accomplishments would have secured Gauss a spot in history, some of them just a footnote, but many of them a full chapter. Take them together, and you can see why Gauss is considered by many to be one of the true giants of scientific thought.