Programming Praxis

[ Today’s exercise is a Christmas stocking stuffed with six little exercises. I wish all my readers a Merry Christmas and a Happy New Year! I’ll be taking a few days with family, so the next exercise will appear on January 6, 2015. ]

We tend to think of algorithms as procedures used by computers, but algorithms actually have a long and distinguished history. Today’s exercise discusses six algorithms that pre-date the Christian era, arranged roughly in chronological order. Despite their antiquity, all these algorithms are still in use today.

Peasant Multiplication: This algorithm has been independently invented by most societies as they progress to numeracy, so it is called the Egyptian method, the Ethiopian method, the Russian method, the Ukranian method, and so on for many different peoples; we simply call it the Peasant method. It is known that the Egyptians used this algorithm during the construction of the pyramids.

The algorithm starts by writing the two numbers to be multiplied at the heads of two columns. Then, on successive rows, the number in the left column is halved, discarding any remainder, and the number in the right column is doubled, until the left column is reduced to one. Then the sum of the numbers in the right column that correspond to odd numbers in the left column is the desired product. The ancients use pairs of pebbles to halve numbers and determine parity; we find it simpler to sum the odds as we go along.

function product(left, right)
    prod := 0
    while left > 0
        if left is odd
            prod := prod + right
        left := halve(left)
        right := double(right)
    return prod

In the United States we torment eight-year-old kids with the times tables, but school children in the rest of the world learn this method, which is simpler and, if you’ve ever taught third-grade math, more likely to be done correctly. Additionally, all computers do arithmetic in binary, and use this algorithm deep in the microcode that is stamped into the silicon chip that runs them, shifting bits to perform the halving and doubling operations. The only improvement is that computers nowadays process multiple bits at the same time, instead of just a single bit, reducing the number of steps in the loop.

Babylonian Square Roots: Mathematical historians know that the Babylonians invented a method of calculating square roots because a clay tablet with the calculations etched into it (ancient “scrap paper”) exists, but the method was first described by Hero of Alexandria in the first century after Christ. Hero (his name is sometimes spelled Heron) invented the jet engine (a hollow metal ball filled with water, heated over a fire to convert the water to steam, which exited by two nozzles on opposite sides of the globe; the rotational motion could be captured by gears or belts), the windmill (he used it to power a variety of machines, including a grain grinder), and the vending machine (you dropped a coin into a slot, which caused a balance beam to rise, opening a valve and filling a small vessel with holy water; when the vessel was full, it tipped to deliver the holy water, the coin was tipped into the safe, the balance beam fell, the valve closed, and the machine reset for the next purchase).

Hero observed that if x is an approximation of the square root of n, a better approximation is given by the average of x and n /x; we say x ′ = (x + n /x) / 2. The initial value of x can be anything on the range 1 ≤ x ≤ n, though the process converges more quickly if x is somewhat closer to n. In the version of the function given below, we bound n on the range 1 ≤ n < 4 so we can fix the number of iterations required for double-precision accuracy; an alternative is to iterate until the difference between two successive approximations is less than some desired epsilon.

function sqrt(n)
    if n < 1 return sqrt(n * 4) / 2
    if 4 <= n return sqrt(n / 4) * 2
    x = (n + 1) / 2
    repeat 5 times
        x = (x + n / x) / 2
    return x

The only improvement since the Babylonians is the initialization of x, which nowadays is done by some kind of black magic operating on the internal representation of the number (for integers, it’s generally one less than the number of bits in the binary representation of the number, for floating point it’s generally half the mantissa of the number with the exponent reduced by one), usually reducing the number of iterative steps to two or three.

Pythagorean Triples: Pythagoras, who lived about five centures before Christ, was a mathematician, philosopher and mystic. When he discovered that the square root of 2 could not be expressed as the ratio of two integers (we now say that it is irrational), he thought he had discovered some impossible flaw in the perfection of the World, and swore his followers to secrecy; legend tells us that one of his disciples, Hippasus, was murdered when he divulged the secret (another legend has it that Hippasus, not Pythagoras, who discovered the irrationality of the square root of 2).

Pythagoras proved that for any right triangle the square of the length of the hypotenuse is equal to the sum of the squares of the other two sides. He also discovered that given any coprime m and n, a primitive right triangle (all sides coprime to each other) has sides m² − n², 2m n, m² + n²; for instance, with m = 2 and n = 1, the triangle is 2² − 1² = 2, 2 × 2 × 1 = 4, and 2² + 1² = 5.

function triple(m, n)
    return m*m - n*n, 2*m*n, m*m + n*n

An alternative method is to take any primitive Pythagorean triple {a, b, c} and generate three new primitive Pythagorean triples as {a-2b+2c, 2a–b+2c, 2a-2b+3c}, {a+2b+2c, 2a+b+2c, 2a+2b+3c}, {−a+2b+2c, −2a+2b+3c}; the process starts from {3, 4, 5}. Of course, non-primitive triples can be generated by multiplying all three elements of a primitive triple by some constant k.

Greatest Common Divisor: Euclid was either a Greek mathematician of the third century before Christ or, as some historians suggest, the conglomerate name of several mathematicians. Euclid wrote Elements, a textbook of geometry and number theory which has been in continuous publication since it was written, which is famous for its method of starting with five axioms and deriving all of geometry from them.

Euclid’s Elements, Book VII, Proposition 2, gives an algorithm for computing the greatest common divisor of two integers. Euclid’s algorithm works by repeatedly subtracting the smaller number from the larger, which reduces the magnitude of the numbers, thus guaranteeing termination of the algorithm, without affecting the greatest common divisor, since both the smaller number and the difference between the two numbers must be multiples of the greatest common divisor.

function gcd(m, n) # ancient
    if m < n return gcd(m, n-m)
    if n < m return gcd(m-n, n)
    return m

function gcd(m, n) # modern
    if n == 0 return m
    return gcd(n, m % n)

Euclid used repeated subtraction; nowadays we use modular arithmetic. Knuth calls this the “grand-daddy” of all algorithms, even though it isn’t the oldest, because it was the first to be written in rigorous form.

Approximation of Pi: Archimedes of Syracuse (on the island of Sicily) was a famous inventor of the third century before Christ: the screw pump, block-and-tackle pulley, odometer (it dropped a ball every time the wheel completed a turn), and numerous devices of war were among his inventions. He didn’t invent the lever, but was the first to explain how it worked, and he famously stated “Give me a lever and a place to stand, and I can move the world.” His most famous discovery was that objects float when they weigh less than the water they displace, which he used to prove that the king’s crown, thought to be pure gold, was actually an amalgam with silver; it is said that he discovered the principle while bathing, whereupon he ran naked through the street shouting “Eureka!”

The ratio of the circumference of a circle to its diameter is the mathematical constant known as π, which is approximately 3.141592654. Archimedes bounded the value of π in the range ²²³/₇₁ < π < ²²/₇ by calculating the perimeters of two hexagons, one inscribed inside a circle and one circumscribing it, then successively doubling the number of sides of the inscribed and circumscribed regular polygons through the series 6, 12, 24, 48, and 96.

function pi(n) # archimedes used 6
    outer := 3 * sqrt(3)
    inner := outer / 2
    for i from 1 to n
        outer = 2 / (1/outer + 1/inner)
        inner = sqrt(outer * inner)
    return inner, outer

Archimedes’ approximation ²²/₇ is still frequently used today, but his method of computing the approximation has been replaced by a series expansion due to Srinivasa Ramanujan, or some similar series expansion, which converges in just a few steps; by contrast, Archimedes’ algorithm requires 27 steps for double-precision accuracy.

Prime Numbers: Eratosthenes, who measured the circumference of Earth, the distance from Earth to Sun, and the tilt of Earth’s axis, devised a system of latitude and longitude and was third chief librarian of the great library at Alexandria, succeeding Ptolemy and Apollonius, invented a method of enumerating prime numbers about 200BC; his writing has been lost, but we know of his invention through the writings of Nicomachus two centuries later.

The Sieve of Eratosthenes identifies primes by striking out multiples and keeping what’s left; the image is that composites fall through the sieve but primes remain. Initialize a list of numbers, from 2 to the desired limit n all marked as prime, then consider each number in turn; if it has not been marked as composite, report it as prime, then mark all its multiples as composite, starting from the square of the prime (since all smaller multiples will have already been marked composite by smaller primes).

function primes(n)
    sieve := makeArray(2..n, True)
    for p from 2 to n
        if sieve[p]
            output p
            for i from p*p to n step p
                sieve[i] = False

Modern mathematicians have optimized the basic Sieve of Eratosthenes shown above by eliminating the small primes that, because they have so many multiples, take most of the time; eliminating multiples of 2 is easy, and “wheels” can be used to eliminate multiples of 3, 5, 7, and so on, though increasingly large wheels quickly become cumbersome to operate. Still, an optimized Sieve of Eratosthenes is faster than any of its many modern alternatives.

Your task it to translate these seven programs into your favorite programming language. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

[ Today’s exercise comes from the blog of long-time reader Ben Simon, after he declined my offer to guest-author the exercise and told me to steal it. The code and most of the text is his, so he gets the credit, not me. ]

It’s been a while since we had an exercise from our cryptography topic. Today’s exercise is the Diana Cryptosystem, also known as the trigraph cipher, which was used militarily by US forces during the Vietnam War and is theoretically unbreakable when used properly.

There are two pieces to the system: the trigraph itself, which is pictured at right, and a one-time pad, like this:

WHTVI AUCFU RETFK OMSAL
MYMNE ZIEGP UKVTF WZHOK
GORWY WETFR COYET OOWHY
ZPDDA CMMXT VYTJI RRQGU

To use the cipher, a section of the one-time pad is chosen and the two five-character groups that begin the section are transmitted unchanged. Thereafter, the key character is looked up on the trigraph, the next plaintext character is on the top row, and the corresponding ciphertext character is read off the bottom row. Decryption is the inverse operation. For instance, the message ATTACK AT DAWN is encoded like this, starting from the third group on the second row of the one-time pad:

UKVTF WZHOK GORWY WETFR COYET
            ATTAC KATDA WNXYZ
UKVTF WZHOK TSPDZ TVNRI BYEXH

Then UKVTF WZHOK TSPDZ TVNRI BYEXH is transmitted by Morse code. The recipient looks up the first two groups on the one-time pad then decrypts as follows:

UKVTF WZHOK GORWY WETFR COYET
UKVTF WZHOK TSPDZ TVNRI BYEXH
            ATTAC KATDA WNXYZ

The cipher is unbreakable without the one-time pad.

We said earlier that the cipher was used militarily. Ben points to this description of its use:

Special Forces were one of (if not the only) units in Vietnam to utilize Morse code on a regular basis. We used a method of encryption called the Diana Cryptosystem.

The basis of these “One-Time Pads”, is that there were only two matching pads in existence, and they would only be used one time. They were booklets that contained randomly generated groups of 5-letter “words;” 30 words to a page. The person sending a message would first write the letters to the message, over these random groups of words. Included in the front of each one-time pad was a one-page encryption table. If I wanted to send the letter “P”, and the letter under the “P” was an “A”, then I would send a “K”. The person listening on the frequency at the other end, would have the other matching pad. They would write the letter they received (a “K”) over the letter in their one-time pad (an “A”), and decipher it based on the table, yielding the original letter “P”.

Each communication site in Vietnam (we had over 100 A-Camps along the Cambodian / Laotian border, and some 20 B-detachment sites spread over the country) had a different pad, depending on the location they were having the commo-check with. It obviously was very important that both people were using the appropriate matching pads, or the deciphered messages would not make any sense.

After a while, most of us became so proficient with the system, that we actually learned the deciphering matrix by heart. No matter what pads anyone had, the combinations always were the same. i.e. Any 3 letters always went together, regardless of the order; “BKO”/”KOB”/”OBK”/”BOK”. After listening to thousands and thousands of transmissions, it really got quite simple. If I was listening to code, and a letter “B” was sent (now remember, we usually sent around 20-25 “words” (5 letters per word) a minute, hence the importance of the “speed” keys!), and the letter it was associated with was an “O”, most of us would decipher as we heard it, and just write the “K”. That may sound like quite a yarn, but it is absolutely true.

Your task is to write a program that implements the trigraph cipher. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

I saw this question at a popular interview-question site and got mad at the suggested answer:

You are given two lists containing identical sets of integers except that the first list contains two additional integers not present in the second set. For instance, with a = {1 4 9 2 7 3} and b = {9 7 4 1}, the two additional integers are 2 and 3. Write a program to find the two additional integers.

Your task is to write the requested program. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

Magic squares are an arrangement of consecutive counting numbers starting from 1 into rows and columns in which every row, column and the two main diagonals all sum to the same number. Magic squares are an important element of recreational mathematics, and have been known since antiquity; this magic square of order 3, with magic sum 15, was published in China in 650BC:

That magic square was constructed by the “start bottom, move down and right, else up” rule: Starting from either of the center cells on the bottom row, enter a 1, then move to the next square diagonally down and right (wrapping around the sides of the square if necessary), then enter the next number in sequence, 2, and so on. However, if the next square is occupied, move instead to the next square up from the current square, then continue the sequence. Various rules like “start left, move down and right, else up” and “start top, move up and right, else down” also work, but rules like “start top, move down and left, else up” don’t; I’ll let you have the pleasure of figuring out which rules work and which don’t. This method works only for odd orders; there are other methods for even orders, which we may examine at some other time.

In the example square, the starting cell is the center cell on the bottom edge, where you see 1. Moving down and right and wrapping to the top of the next column, enter 2. Then moving down and right and wrapping to the left of the next row, enter 3. The next cell down and right already contains 1, so instead move up from the current cell and enter 4. Then moving down and right, enter 5. Then moving down and right, enter 6. The next cell down and right, wrapping both the row and column, already contains 4, so instead move up from the current cell and enter 7. Then moving down and right and wrapping to the left of the next row, enter 8. Finally, moving down and right and wrapping to the top of the next column, enter 9.

Your task is to write a program that takes an odd order n, one of the four starting cells and a rule and generates the indicated magic square. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

When I saw this web page a few days ago, I knew it would make a great exercise, simple but fascinating. Starting with x = 1, every fraction in lowest terms is generated by x ′ = 1 / (n − y + 1), where n = ⌊ x ⌋ and y = x − n. The underlying math is known as the Stern-Brocot tree, and has been known since the ancient Greeks, who used terms of the Stern-Brocot tree to design the gear ratios in the Antikythera mechanism.

Your task is to write a program that generates the fractions in lowest terms. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

We have a very practical task today: Given the set of busy-time intervals of two people, as in a calendar, find the free-time intervals of both people so they can arrange a meeting.

Your task is to write a program to find free time. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the
comments below.

Pages: 1 2

Our exercise today is based on Gray code sequences, where each number in the sequence differs from its predecessor in only one bit. We studied Gray code sequences in a previous exercise. Here is an interview question base on Gray code sequences:

Given two integers, determine if they are two consecutive numbers in a Gray code sequence.

Your task is to write a program that determines if two numbers appear consecutively in a Gray code sequence. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2