How computers think

Inside a computer, very simple parts and methods are stacked many layers deep. Here are four. Each idea can be grasped in minutes, but the road to it was long.

Logic Gates (the site’s “Logic Gates”)

AND gives 1 only when both inputs are 1. OR gives 1 when either is 1. NOT swaps 0 and 1. XOR gives 1 only when the inputs differ. Adding two single bits (0 or 1) works if XOR makes the ones digit and AND makes the carry. This circuit is called a half adder. This site’s program checked the tables of the four gates and that the half adder computes 0+0, 0+1, 1+0 and 1+1 correctly (logic-gates/engine.test.ts).

Add the carry from the previous digit too and you get a full adder. By the way, it is known that NAND (AND with its result flipped) alone is enough to build every other gate.

Boole and Shannon

In his 1854 book An Investigation of the Laws of Thought, George Boole treated logic as an algebra of 0 and 1. But nobody in Boole’s day thought of electrical circuits. It is not that Boole built logic circuits; he made an algebra that was later used to design them.

Claude Shannon, in a master’s thesis at MIT around 1937, is said to have shown that Boolean algebra can be used to design relay circuits (circuits of electric switches). Sources give 1936 to 1938 for the year. The Japanese engineer Akira Nakashima also wrote about switching circuits in 1935–36, and some accounts treat his work as a predecessor. So it cannot be said that Shannon was the sole beginning.

Sorting Race (the site’s “Sorting Race”)

There are many ways to sort. This site races five of them, Bubble, Insertion, Selection, Quick and Merge, on the same row of bars. On 16 bars, this site’s program checked the following (sorting-race/engine.test.ts).

• Selection always makes exactly 120 comparisons (16 × 15 ÷ 2), whatever the order.
• Merge always makes exactly 64 writes (16 × 4), whatever the order.
• Bubble and Insertion make 120 comparisons on a reversed row and 15 on an already sorted one.
• The number of swaps in Bubble and Insertion equals the number of pairs that are out of order.
• On a nearly sorted row, Insertion needs the fewest operations of the simple ones.

Each method has its good and bad inputs. There is no method that is always the fastest.

Some history

A routine that John von Neumann wrote in 1945 for the EDVAC computer, to merge two sorted lists, is known as one of the earliest merge sort programs, it is said. That does not make him the inventor of merge sort, though.

Quicksort came from C. A. R. Hoare in 1959, while he was studying in Moscow. He needed to sort Russian words for machine translation. The paper appeared in the July 1961 issue of Communications of the ACM.

It is mathematically proven that a sort that only compares items has a lower limit on how many comparisons it needs, however clever it is. Methods that do not compare, such as radix sort, which uses the numbers themselves, sit outside this limit (when the keys are, for example, integers).

Caesar Cipher (the site’s “Caesar Cipher”)

Every letter is moved by the same number of steps. The ancient Roman biographer Suetonius, in his life of Julius Caesar, writes that Caesar shifted letters three places in secret letters (A became D). Suetonius wrote about 150 years after Caesar’s death. The name “Caesar cipher” also comes from later times.

There are few possible shifts, so trying them all breaks it. A smarter way is frequency analysis. In ordinary writing, some letters are common and some rare. Shifting the letters moves this pattern sideways without changing its shape, so the position of the peaks gives the shift. This site’s program checked that shifting moves the peaks by exactly the shift, and that the solver finds the secret shift of every puzzle and recovers the original text (caesar-cipher/engine.test.ts).

The oldest known write-up of frequency analysis is said to be a text by al-Kindi, a scholar in ninth-century Baghdad. The manuscript was long lost and is said to have been rediscovered in 1987. How he came to notice letter frequencies is not clear in the sources, so “said to be the oldest” is the safe way to put it.

Halving Search (the site’s “Halving Search”)

To find a number from 1 to 100, guess the middle: the possibilities are cut exactly in half. This site’s program checked the following (binary-search/engine.test.ts).

• Every number from 1 to 100 is found within 7 guesses. Six guesses can tell apart only 63 numbers, so six are not enough.
• Every number from 1 to 1,000,000 is found within 20 guesses.
• For 1 to 100, the numbers found in 1, 2, 3, 4, 5, 6 and 7 guesses are 1, 2, 4, 8, 16, 32 and 37 in number.
• For 37, for example, the guesses are 50, 25 and 37: three guesses.

Make the range 10,000 times bigger and the count only rises from 7 to 20. This is binary search (it needs the data to be in order).

Simple to explain, hard to write

Binary search is said to have been first published in 1946. But the first published version that works correctly for lists of any length came in 1962. Jon Bentley is said to have reported that, when programmers were asked to write it, about nine in ten made a mistake. Sources describe the conditions of that experiment differently, so treat the figure as a rough guide.

In June 2006, Joshua Bloch announced on the Google Research Blog that the binary search in a well-known book, and in Java’s standard library, had a bug. The calculation of the middle, (low + high) / 2, can overflow an integer when the data is very long (2 to the 30th power items or more). Merge sort and similar methods can have the same kind of mistake. The idea takes minutes to grasp, but writing it correctly took care for decades.

What the four share

• Small parts, stacked: XOR and AND alone can add.
• It depends on the input: no sort is always the best.
• Lopsidedness is a clue: a cipher can be broken by letter counts.
• The power of halving: even a million items take 20 guesses.

The diagrams here are all simplified teaching models. Real computers have many details we leave out.