Pythagorean Triples

November 24, 2015

The Pythagorean theorem, linking the sides of a right triangle, is one of the most useful basic mathematical identities. It is also one of the more entertaining. Loomis, in his book The Pythagorean Proposition (1968), gives 370 different proofs of the theorem. However, we’ll more often interested in computing the length of the hypotenuse, or finding triples—three natural numbers that makes the theorem hold—than finding a new proof for it.

There is, of course, the smallest possible triple (defined as involving the smallest possible numbers) 3, 4, 5. But there are infinitely more triples. Let’s see how we can generate them.

Read the rest of this entry »

The Speed of GCD

December 10, 2013

The subject of computing the GCD was brought up a couple of times lately, and we assumed that the straightforward divide-and-remained implementation was the most efficient. But is it?


Before writing this post, I knew of basically two versions, one due to Euclid, invented sometimes in Antiquity of course, and one that used the remainder (that is, modulo) to do basically the same thing (which can be implemented either recursively or iteratively). Turns out that there are other algorithms, for example the so-called binary GCD that tries to somewhat speed up the process by removing multiples of two. But which one is the most efficient?

Read the rest of this entry »

The Sieve of Eratosthenes

September 3, 2013

The Ancient Greeks never fail to amaze me. Sometimes their ideas border the merely superstitious, sometimes you find a guy like Eratosthenes (c. 275 BC – c. 195 BC) that comes up with a truly modern idea. I’m not talking about his invention of geography (in the modern sense of the word) nor about his suspiciously accurate estimate of Earth’s size. No, I’m talking about an algorithm that has a very modern feel to it: the sieve of Eratosthenes


So what is it that I find so modern about this algorithm? Well, it has a computational feel to it, replacing smarts with a simple procedure, regular and repetitive. So, how hard is Eratosthenes’ sieve to implement? Not every: about 10 lines of code is needed in C++ (and possibly quite fewer if we use some other language).

Read the rest of this entry »

Euclid, Primes numbers, and a Bit of Algorithm Analysis

June 25, 2013

Last time we had a look at using the greatest common divisor and Euclid’s algorithm to devise a Las Vegas algorithm for primality testing. We also had a look at how the inclusion exclusion principle helps us determine the proportion of the numbers correctly tested.


However, we finished by asking ourselves if the method is actually efficient compared to, say, simply testing small divisors, one by one. Let us now find out.

Read the rest of this entry »

Euclid, Prime numbers, and the Inclusion-Exclusion Principle

May 28, 2013

The Euclidean algorithm, the algorithm to compute the greatest common divisor, or \gcd, of two numbers, dates back to antiquity (obviously). We can use it to make a fast test for primality, at least up to some confidence—and that’s where the inclusion-exclusion principle comes in.


Let us begin by the Euclidean algorithm. Originally, the algorithm was done by successive subtraction (and becomes quickly tedious as numbers grow), but the modern version, at least the one that I know of, uses divisions and remainders (modulo), and computes the \gcd(a,b) of two numbers a and b in O(\lg\min(a,b)) (counting division as an O(1) operation), which is very fast.

Read the rest of this entry »