How Base 3 Computing Beats Binary
Robert Neubecker for Quanta Magazine
Three, as Schoolhouse Rock! told children of the 1970s, is a magic number. Three little pigs; three beds, bowls and bears for Goldilocks; three Star Wars trilogies. You need at least three legs for a stool to stand on its own, and at least three points to define a triangle.
The number 3 also suggests a different way of counting. Our familiar base 10 decimal system uses the 10 digits from zero to 9. Binary, our digital lingua franca, represents numbers using only the two digits zero and 1.
But mathematicians have long explored counting in threes. Consider, for example, base 3, or ternary, which uses three digits. The standard convention is to use the digits zero, 1 and 2.
Mark Belan for Quanta Magazine
Mark Belan for Quanta Magazine
The hallmark feature of ternary notation is that it’s ruthlessly efficient. With two binary bits, you can represent four numbers. Two “trits” — each with three different states — allow you to represent nine different numbers. A number that requires 42 bits would need only 27 trits.
If a three-state system is so efficient, you might imagine that a four-state or five-state system would be even more so. But the more digits you require, the more space you’ll need. It turns out that ternary is the most economical of all possible integer bases for representing big numbers.
To see why, consider an important metric that tallies up how much room a system will need to store data. You start with the base of the number system, which is called the radix, and multiply it by the number of digits needed to represent some large number in that radix. For example, the number 100,000 in base 10 requires six digits. Its “radix economy” is therefore 10 × 6 = 60. In base 2, the same number requires 17 digits, so its radix economy is 2 × 17 = 34. And in base 3, it requires 11 digits, so its radix economy is 3 × 11 = 33. For large numbers, base 3 has a lower radix economy than any other integer base. (Surprisingly, if you allow a base to be any real number, and not just an integer, then the most efficient computational base is the irrational number e.)
In addition to its numerical efficiency, base 3 offers computational advantages. It suggests a way to reduce the number of queries needed to answer questions with more than two possible answers. A binary logic system can only answer “yes” or “no.” So if you’re comparing two numbers, x and y, to find out which is larger, you might first ask the computer “Is x less than y?” If the answer is no, you need a second query: “Is x equal to y?” If the answer is yes, then they’re equal; if the answer is no, then y is less than x.
A system using ternary logic can give one of three answers. Because of this, it requires only one query: “Is x less than, equal to, or greater than y?”
Despite its natural advantages, base 3 computing never took off, even though many mathematicians marveled at its efficiency. In 1840, an English printer, inventor, banker and self-taught mathematician named Thomas Fowler invented a ternary computing machine to calculate weighted values of taxes and interest. “After that, very little was done for years,” said Bertrand Cambou, an applied physicist at Northern Arizona University.
In 1950, at the dawn of the digital age, a book-length report on the computing technology of the time suggested a computing advantage for ternary. And in the fall of 1958, visitors to the Soviet Union reported that engineers there had been developing a ternary computer called Setun — the first modern computer based on ternary logic and hardware. Soviet scientists built dozens of Setun computers.
Why didn’t ternary computing catch on? The primary reason was convention. Even though Soviet scientists were building ternary devices, the rest of the world focused on developing hardware and software based on switching circuits — the foundation of binary computing. Binary was easier to implement.
But the past few years have brought flashes of progress. Engineers have proposed ways to build ternary logical systems even on binary-based hardware. And Cambou, with the support of the U.S. military, has been developing cybersecurity systems that use base 3 computing. In papers published in 2018 and 2019, he and his collaborators rigorously described a ternary-based system that could replace the existing public key infrastructure, which includes the digital keys needed to encrypt or decrypt cybercommunications. Switching from bits to trits, he said, significantly reduces the error rate, because ternary states better manage erratic information.
Schoolhouse Rock! turned out to be prophetic. “The past and the present and the future,” the cartoon characters sang. “You get three as a magic number.”
