Ternary, trinary or trit logic: of bricks and trytes (and bytes and bits)

http://www.mortati.com/glusker/fowler/
    The ternary calculating machine of Thomas Fowler

[In a word: e (2.71828...) would be the most efficient base for storing digital information. Not two, i.e. the bits. Storing on three-unit devices (trits) would be the best practical information base. Ternary arithmetic rulez]

This short post is inspired by Igor Carron's The 2-bit Aggie weather station. Igor proposes us the three-valued (bbl) system for assessing weather conditions, with a brick put outside: brown, bright, left:

• If brick is dark brown, it's a sure sign that it's raining outside. 
• If the brick is bright, then it's sunny outside. 
• If the brick is not there anymore, it's a tornado.

The weird ternary calculing machine machine on the right is not a brick (althhough the color is similar), and is better described in The ternary calculating machine of Thomas Fowler, IEEE Annals of the History of Computing, 2005, by Glusker, Hogan, and Vass.

Bender: Ahhh, what an awful dream. Ones and zeroes everywhere... and I thought I saw a two.
Fry: Don't worry, Bender: there's no such thing ...
Futurama

Among the very few scientific results i can grasp, a very few simple ones jump to my mind and keep me amazed:

• the fact that the Wiles-Fermat theorem is almost trivial in polynomial ring (see Mason-Stothers ABC theorem, based on Wronskians  for complex coefficients, showing that max(deg(A(a),deg(B(x),deg(C(x))) + 1 <= # roots (A(x)B(x)C(x))
• Cantor's diagonal argument
• statistical Stein's lemma and paradox, and some of it's signal processing applications (pdf)
• the most beautiful Euler god-existing formula, involving constants pi, e, i, 1 and 0 (from utmost to least translucency): e(i*pi)+1=0:

• van der Corput Lemma for oscillatory integrals
• Pick's theorem relating inside, border points and area in lattice polygons
• and, of course, a pair of others

The most radical one, pertaining to signal acquisition and representation, lies between the binary and the ternary systems: from bits to trits, from bytes to trytes. It states that the "most efficient" storing system is "e", from Euler's number, not to confuse with Mascheroni-Euler constant, gamma, (the one from the natural logarithm). I am quite surprised the binary system pervades so  much the present digital world that this "fact" is quite often ignored. Indeed, when i try to gather some information on that topic, i generally do not remember where to start from. Which keywords (trit for "ternary digits" similar to bits for "binary digits", or "tryte" versus "byte" for the "words" themselves, trinary or ternary), what sources?

The basic idea is that, when trying to represent a number in concise or sparse form on d-digits (or number byte-width), one could choose the biggest b-base (or bit-depth, the number of symbols per "digit") for representation. In a similar way for signal or image processing, the sparsest base or frame for a specific signal or image has this signal or image data as a vector. The simplest idea comes from minimizing the product width x depth, or e(d,b) = db, considered as a loss function.Let us compute it for all numbers from 0 to decimal N = 999999, in different numeral systems?

• Decimal: b = 10, d = 6 = ceil(log(N+1)/log(b)), db = 60,
• Binary: b = 2, d = 20, db = 40,
• Ternary: b = 3, d = 13,  db = 39,
• Quaternary: b = 4, d = 10,  db = 40.

Here we have a very local minimum at b = 3. More generaly, the objective minimizes the loss function e(b) = b/log(b) (at WolframAlpha). The non-negative real minimum is "e". The two potential contenders for practical arithmetics, or even physics, are the 2 (binary) or the 3 (ternary), the two closest integers. It is easy to note that e(2) = 2.885... while e(3) = 2.731... and e(4) = 5.771 (compare to 2.718...). This confirms the preceding decimal/binary/ternary/quaternary local minimum at 3, 2 becoming second, the ternary numeral system, is closer to the absolute minimum. So we need to add 2 and 3 and propose a "Generalized"-) Euler formula:

and, more interesting, 3 should be more compact, even for three-valued logic in computer systems. The chapter Ternary computers: the setun and the setun 70, by N. P. Brusentov and J. R. Alvarez from Moscow state university (at Google books), indicates that this is an old story:

"It is known that the ternary arithmetic has essential advantages as compared with the binary one that is used in present-day computers. In connection with this Donald Knuth assumed that the replacement of "flip-flop" for "flip-flap-flop" one a "good" day will nevertheless happen [1]. Now, when the binary computers predominate, it is hard to believe in a reality of such assumption, but if it would happen not only the computer arithmetic, but the informatics on the whole would become most simple and most perfect. The third value (Aristotle named it snmbebhkoV – attendant) what is very actual but hidden in binary logic, will become obvious and direct manipulated. Ternary logic has better accordance with the Nature and human informal thinking [2]. Unfortunately, the modern researches of the multivalued (non-binary) logic are formal and are not associated with practical requests.A remarkable exclusion is the experience of creating the ternary computers "Setun" and "Setun 70" at Moscow State University [3,4,5,6]. This experience convincingly confirms practical preferences of ternary digital technique.

The design of small digital machine "Setun" (Setun is the little river which flows into the river "Moscow" near the University) was initiated by member of the academy of Sciences S. L. Sobolev at 1956. It was assumed to create small, inexpensive computer, simple in use and service for schools, research laboratories, design offices and for manufacture control. For such goal at the computer center of the University there was formed a group of young men (4 MS and 5 BA). The joint seminar for engineers and programmers was organized and S. L. Sobolev, K. A. Semendjev, M. R. Shura-Bura, I. S. Berezin were its permanent participants. The problems of optimization of computer architecture and technical realization were examined and the variants of future computer were discussed."

I especially like the flip-flap-flop mnemonic. "Perhaps the prettiest number system of all," writes Donald E. Knuth in The Art of Computer Programming, "is the balanced ternary notation."This reminds of the first derivatives of position. Velocity and acceleration are well known, jerk is the 3rd derivative. Jounce is sometimes given for the fourth derivative. Jounce is the rate of change of jerk, over the time. But some call the 4th, 5th and 6th derivatives "Snap, "Crackle" and "Pop" (as for the Rice Crispies, as for those interested in wavelets).


This story is summarized in Third Base at American Scientist, by Brian Hayes: (printer-friendly version, 2001).

"When base 2 is too small and base 10 is too big, base 3 is just right. "

It even recalls the following conjecture:
More than 20 years ago, Paul Erdös and Ronald L. Graham published a conjecture about the ternary representation of powers of 2. They observed that 2^2 and 2^8 can be written in ternary without any 2s (the ternary numerals are 11 and 100111 respectively). But every other positive power of 2 seems to have at least one 2 in its ternary expansion; in other words, no other power of 2 is a simple sum of powers of 3. Ilan Vardi of the Institut des hautes études scientifiques has searched up to 2^6973568802 without finding a counterexample, but the conjecture remains open.

Yet, even-though the first attempts have met difficulties (check out the early 1950 High Speed Computing Devices in djvu), people are still working towards ternary physical systems: Klein M., Mol J. A., Verduijn J., Levine R. D., et al. Ternary logic implemented on a single dopant atom field effect silicon transistor. APPLIED PHYSICS LETTERS. 2010; 96(4) (see Raphael Levine).



So yes Igor, this brick-like technology does (almost) exist. Or probably in a near future. Maybe it is not practical enough yet, or the world is not ready for that. A while ago (30 years), i learned how to count in binary with my fingers (thanks to a mormon American, Chris F., thinking of you), and we have three phalanges, so i can easily switch. But the ternary politic system still does not yet exist in France.

Additional links on ternary arithmetics and trits (trytes or trybbles):

The Ternary Manifesto: Douglas W. Jones proposes (quite interesting) "An alternative basis for development of a completely incompatible digital infrastructure is presented here. This minimizes the potential for leakage of information, particularly malware and other covert content from our existing digital infrastructure. This effort can be described as taking security through obscurity as a fundamental design principle."

Unsigned and Balanced Ternary Representations by Douglas W. Jones again.On bytes and nybbles, Trytes and trybbles, the tennary equivalent of nybbles (packet of trytes)

Third Base (American Scientist): Cheaper by the Threesome