Revisiting Radix Economy
I was curious about the IOTA cryptocurrency citing radix economy as a justification for using ternary rather than binary circuits. I wanted to revisit the original assumptions in the computer science folklore that Euler’s number e is the “optimal radix”.
The earliest reference I found on the subject was “High Speed Computing Devices” from 1950. This text talks about selecting a numerical base in the context of computers built from triodes; better known as vacuum tubes.
Triode Ring Counters
High Speed Computing Devices describes using triodes to build ring counters, which are circular shift registers where the position of a bit in the register represents a number. To represent a number R, you would need a ring counter with R triodes. There were also slightly more complex ring counters that could representing up to 2R with R triodes.
This may seem like a naive way to encode numbers. You are essentially encoding each digit in unary, like beads on an abacus. However, I think given the high component costs, the technical limitations, and the relative simplicity of chaining counters or building adders, it was a well-thought decision in the 1950s.
The above image is a 5-triode ring counter. A quinary counter like that may have been used by the IBM 650, which was a vacuum tube, bi-quinary decimal coded computer. A decimal digit would have been represented by a combination of a 2-triode binary and 5-triode quinary ring counters. This is similar to the numbering system on some abaci.
Triodes and Radix Economy
Triode-based ring counters are the origin of the folklore cost function for radix economy, where ‘B’ is a base and ’N’ is some maximum value. The function is just the product of the radix, B, and the width of the representation, log_B(N): E(B, N) = B * log_B(N)
The rationale is that if using ring counters, it costs B vacuum tubes to represent a each digit of a base-B number. If you solve to find B with the minimal radix economy value, the optimal base is e=2.718… . The closest integral value is 3, and as the High Speed Computing Devices text says:
“Under these assumptions, the radix 3, on the average, is the most economical choice, closely followed by radices 2 and 4”
Therefore we should build ternary computers. Case closed.
Except, this was for 1950s vacuum tube computers and nobody bothered to keep reading the next paragraph:
“These assumptions are, of course, only approximately valid, and the choice of 2 as a radix is frequently justified on more complete analysis. It should be noted that, even with the optimistic assumption that 10 triodes will yield a reliable decimal ring, radix 10 leads to about one and one-half times the complexity of radix 2, 3, or 4. This is probably significant despite the shallow nature of the argument used here.”
The original paper that people cite as the source of “e is the optimal radix” was relevant for a vacuum tube architecture. Even for that, it immediately backtracks saying “except when 2 is better”, that its analysis is too shallow, and it falls apart in practice.
Incidentally, IBM’s bi-quinary decimal computers would not have followed radix economy rule since they used mixed bases — it took 7 triodes to represent the number 10, not 10 triodes.
Setun: The Russian Ternary Computer
Several research groups experimented with ternary computers from the 50s-70s. The most well-known was Setun, which was a ternary computer built at Moscow State University in 1958 and led by Nikolai P. Brousentsov.
According to Willis Ware’s RAND report from 1959, Setun was implemented in a base-4 machine. Ware claims they did not have any 3-state electronics to build it from, so encoded ternary values into 2 bits. If Ware’s assessment was accurate, Setun had no performance or economy advantage over binary computers and would have been wasting a large portion of its capacity.
Brousentsov’s own account conflicts with Ware’s. He also claims that a new computing architecture “worked correctly at once without even debugging”, cost 40% as much as competing technology, yet was killed for vague political reasons. Brousentsov continued with his work in the Laboratory for Ternary Informatics and published up to the year of his death in 2014.
While Moscow State was building the Setun in 1958, IBM released the IBM 7070 based on discrete transistors. This was still a decimal computer, but rather than using the bi-quinary decimal encoding, it used a two-out-of-five code in binary. This is the same type of code you’d see on an envelope or barcode.
The most well-known historical ternary computers were at best short-lived experiments or emulated. The IBM 650, which was built on vacuum tubes and should have benefited from using ternary, opted to use bi-quinary encoding. As soon as transistors were available and used commercially, nobody looked back from binary.
Beyond historical computers, I haven’t found a good justification for using ternary in modern computing devices. Arguments about radix economy would only make sense if a more realistic cost function were defined for modern components or empirically measured.