Tunguska: Ternary Computer Emulator (2008)
tunguska.sourceforge.net
tunguska.sourceforge.net
The Jewel in the Triple Crown
“Perhaps the prettiest number system of all,” writes Donald E. Knuth in The Art of Computer Programming, “is the balanced ternary notation.” As in ordinary ternary numbers, the digits of a balanced ternary numeral are coefficients of powers of 3, but instead of coming from the set {0, 1, 2}, the digits are –1, 0 and 1. They are “balanced” because they are arranged symmetrically about zero. For notational convenience the negative digits are usually written with a vinculum, or overbar, instead of a prefixed minus sign.
[0] (pdf) http://bit-player.org/wp-content/extras/bph-publications/AmS...
However, in hardware this model could be made clockless / asynchronous, such that computations go as fast as they can. The extra state of "unknown" can be interpreted as "not all required inputs are ready yet". Some care would be needed to buffer loops in a recurrent circuit, but that's about the only extra complication.
So if there is an adder which outputs “0”, there is bo way to tell if the computation was done and result was zero, or if it is still in progress.
I basically used this sort of design in a dual-rail logic framework which had 4 line-states per "data" line pair, two of which were real data bits, a third indicated unknown vs. unknown, and the fourth was unused.
See https://core.ac.uk/download/pdf/82751815.pdf, but beware that even though it doesn't look at all like ternary numbers in use, it absolute is.
I know you didn't imply otherwise, but it's worth pointing out that ternary logic is by no means required for asynchronous hardware design. The same effect is possible with dual rail channels using two wires per bit, or even fewer on average using Sperner codes and the like.
> computations go as fast as they can
Although asynchronous circuits might not have to wait for a clock, they do have to wait for handshake completion detection in various forms. It's more like a trade-off than a free lunch.
Worth remembering that the ENIAC was a decimal design but after careful consideration, von Neumann (and pals?) decided that using binary would be more efficient. (Decimal was popular for many reasons).
Binary has great noise immunity and all other coding schemes are inherently worse. It's also a lot simpler to make binary gates than ternary.
True, but I imagine it wouldn't impact typical high-level code that much.
I couldn't find anything after a very quick search, but if not already done, I want to start referring a ternary bit as a 'tit'!
[1] https://en.wikipedia.org/wiki/Ternary_computer#Types_of_stat...
I looked at the screenshots and it's not obvious to me how they map back on to ternary. Like how do you have a hex editor when 16/3=5.333?
"Brousentsov's Ternary Principle, Bergman's Number System and Ternary Mirror-symmetrical Arithmetic" by Alexy Stakhov:
https://pdfs.semanticscholar.org/b946/f8ec0c0ffa12427d73940c...
Also available here (but apparently behind a registration/paywall of some sort...):
https://www.researchgate.net/publication/220458145_Brousents...
Or here:
https://ieeexplore.ieee.org/document/8140230
Or, just Google for "Brousentsov's Ternary Principle, Bergman's Number System and Ternary Mirror-symmetrical Arithmetic".
Keywords: Ternary Symmetrical Number System, Ternary Tau, Base Phi, Golden Ratio, Fibonnacci, 3-Valued Logic, Number Systems With Transcendental/Irrational Bases, etc., etc.
I'm not sure where I picked up the notion (and a cursory search doesn't seem to turn up any supporting evidence), so it's possible that I absorbed this idea from technobabble in some mid-80s or earlier SF novel or TV show.
[1]: https://www.sigineer.com/product-category/inverter-chargers/...
I think the main obstacle would be the lack of ternary logic designers. VHDL/Verilog could probably be extended/enhanced to support ternary logic, but there would be a learning curve for the designers.
There are companies making specialized chips all the time, so if there were a way to create an efficient ternary circuits, then someone would have made one. For example, AI/neural networks do not care about base (they just need math), and they only need a few types of cells to be useful. But I have not heard of any applications of ternary there.
Intuitively, I assume we'd still want to drive transistors to saturation, so we are not dependent on process parameters. Which means that each transistor still only handles two states, and we need two transistors for each trit. But if we have two transistors, we might as well use them for 2 bits and get even more state out of them.
I'd be curious how modern fpgas do it.
Note that this link is tri-state, not ternary. The "tri-state" is still binary, the third state is to allow attaching multiple outputs to the same bus. Or in the C pseudocode:
Regular binary:
enum { FALSE, TRUE } value;
value = result()
enum { UNKNOWN, FALSE, TRUE } value;
value = result()
enum { FALSE, TRUE } value;
if (enabled())
value = result()
But replicating that with an ATMEL or similar generally requires dancing around with resistor ladders or similar.
For the output side, I guess I you can tri-state the output, but this will by default keep the previous voltage, you will need some resistors to actually emit a voltage outer than "low" or "high". And Z80 cannot even control this on per-pin basis, since it has no integrated GPIOs.
For the input side, I have no idea how would Z80 get more than two states. All the peripherals I know of (like 82C55 GPIO chips) also only provide two input levels as well.
The only way to get 3-state input into a system I can think of are:
- ADC input followed by software thresholding (this will be pretty slow, and works with hundreds of states, not just 3)
- Use external voltage comparators to split a single input wire into multiple input pins. This no long is "single pin" though.
- Some FPGA/CPLDs have multiple banks with changeable input thresholds. This lets you avoid external comparators. You'd still need multiple pins for each input wire.
Secondly, Jim Keller paints a fairly convincing picture that (for some definition of Moore's law) there is definitely a long way to go yet.
https://www.howtogeek.com/444787/multi-layer-ssds-what-are-s...
Also, early computers were not all based on binary. E.g. The ENIAC was base-10. https://en.wikipedia.org/wiki/ENIAC
What it did not have was base-2 bytes. It's bit encoding algorithm had "prohibited" states to ensure all numbers are in base 10.
But each individual element in the machine only had 2 states, ON or OFF.
In other words, a binary computer will have 2 possible bit states, 2^n possible byte values, and 2^(n*m) possible word values. For example, Z80 will have 2^8 byte values and 2^16 word values.
A ternary computer will have 3 possible bit states, 3^n possible byte values, and (3^n)^m possible word values.
ENIAC has 2 possible bit states, but a byte has only 10 possible values (which means that some combinations of bits do not form a valid byte). And a word has 10^m possible values.
For more details, let's look at "A REPORT ON THE ENIAC (1946)" [0] from 1946. It is pretty interesting.
The data transmission is in unary(!), see section "1.1.3. Representation of Digits by Pulses". There is a wire per byte which can have 2 voltage levels, and number of pulses corresponds to a number transmitted.
The logic is classical binary, see "1.2.1.3. Gate Tube":
> A gate tube emits a negative signal when both of its input grids are brought from a negative cut off voltage to a positive voltage. Thus, a gate tube is used to note the coincidence of two positive signals and hence corresponds to the logical "and".
The data storage is in binary (or at least bi-state?), see section "1.2.2.1. Flip-Flops". Quote:
> A flip-flop consists essentially of a pair of triodes so connected that at any given time only one of the pair can be conducting. When a certain one of the tubes is conducting (and the other is not), the flip-flop is said to be in the normal state; when the other tube is conducting (and the first is not), the flip-flop is in the abnormal state.
The "byte" counters have ten bits (flip-flops), but only one can be on at a time. so the numbers are stored as 0000000001, 0000000010, 0000000100, etc...
https://ftp.arl.army.mil/~mike/comphist/46eniac-report/chap1...
You might want to read it: https://news.ycombinator.com/item?id=25618303
This reminds me of Alan Perlis' famous admonition to "Beware of the Turing tar-pit in which everything is possible but nothing of interest is easy."
There are many programming languages which are Turing complete, and so are interchangeable as far as their computing power goes, but as you know they don't tend to compete on efficiency alone.
People want to use the right tool for the job, and many other considerations come in to play.
I'd be interested in hearing a sophisticated counter-argument if anybody has a good one. Here's my take on this:
1. Binary is that smallest base in which we can encode Shannon information, and thus yields to "bits" a more elegant foundation for computation. Choosing any other base sounds like it would be a very arbitrary choice, and to the best of my knowledge, the only other canonical base for computation that inherently makes sense (as in, not arbitrary) aside from the `bit` is the `nat`[0], but since it uses Euler's constant (a transcendental number) it would be (ironically) very unnatural to express "computation" in it.
2. By theorem, all bases are equivalent in power with respect to their capabilities of encoding information and processing/computing said information, and binary logic can be used to bootstrap any other multi-valued logic system desirable (goes for ternary logic and 64-bit integer computation alike). Thus, the decision to make a base-3 falls back pretty much entirely on circuit efficiency ...
3. The claims of computational efficiency, as far as I've been able to observe, are fallaciously constructed by studying their performance characteristics in abstract computer models that are completely detached from computational thermodynamics:
3a. Turing-machines, for example, fail to adequately model real-world constraints due to information locality being one-dimensional (while the real world is 3D). Von-Neumann computers (and other RAM based machine models) are IMO the largest infractor of this — there is no such thing as "RAM" in the real world: you can't access any address space irrespective of locality in O(1), such a computer would violate relativistic physics and thermodynamical constraints, RAM can only exist by making all memory access equally inneficient and mitigating that as much as possible with L3 caches and what not. Semiconductor engineers and chip designers inherently understand this and are aware of die-locality, most computer scientists and software engineers are completely oblivious to this and get to ignore it most of the time [1]
3b. This means that even though anyone can theorize an abstract machine where every discrete "tick" of time will perform a ternary operation in constant time, that doesn't mean such a machine can be efficiently reified if you move it out of the realm of abstraction. We could just as easily theorize a computer that uses base-1T (one trillion), and assume that all "trilliernary" operations execute instantly in discrete ticks of O(1), and voila! We have a computation device that can rival all of Google's data-centers!
3c. In the real world however, there are thermodynamic constraints on how information can "flow" across spacetime, and I have seen absolutely zero evidence that a ternary, trilliernary, or whatevernary logic gate can be constructed without introducing many new voltage levels or other circuit fuckery to counteract this, in a way that wouldn't completely wreck any purported efficiency. It's either that, or we'd implement whatevernary logic using binary gates (which is exactly what 64-bit integer arithmetic already is!)
4. Bottom line and TLDR is this: You can't get more computation[2] for free. Welcome to the real world.
---
[0] https://en.wikipedia.org/wiki/Nat_(unit)
[1] This is especially painful to watch when they are forced to deal with it, and these optimistic-assumptions clash with reality, as evidenced by NUMA bottlenecks wrt RAM/RDMA/GPUs/Disk access, a collective failure of most engineers to understand the CAP theorem or other concepts related to networking, and so on...
[2] And by "computation" I mean it in the thermodynamical, relativistically-physical, information-theoretical kind of way. Physics is a thing we forget about way too often in computer science...
-1, 0, +1 has as elegant symmetry that will inspire fascination until either someone can prove its inferiority with some heretofore unimagined model of computing or someone builds a clearly superior device based on it. I strongly doubt such a device is possible with contemporary two dimensional etched semiconductors; too many people have been torturing conventional mosfet circuits for too many decades to think they've left much on the table. But who knows what the future will deliver? Maybe we'll start computing with proteins next year and somehow 3 (or more) levels will make sense.
Instead of clocked design:
data0: 000001111111111111111111111111111000000000
data1: 000000000000000000000000000000000000000000
data2: 000111111111111111111111111111100000000000
...
clock: 000000000001111111111100000000000000000000
data0: --111---
data1: ---000--
data2: ----111-
data: --111---000---111---
That said, I don't understand how you arrived at this:
> anyone can theorize an abstract machine where every discrete "tick" of time will perform a ternary operation in constant time, that doesn't mean such a machine can be efficiently reified if you move it out of the realm of abstraction.
One can definitely create a circuit which will perform a ternary operation in a (some) constant time. It is not hard, and people have done this before [0]. The real question is: can you make a ternary computer which is somehow better (faster, power efficient, cheaper, etc...) than a binary one? But to answer this you need to talk MOSFETS, voltage levels, gate charge, and current tecnhology capabilities. Shannon and Von-Neumann won't help you here.
[0] https://hackaday.io/project/6284-tern-ternary-logic-circuits
Sorry if it seems like it's just a floating comment, indeed the article made claims of the kind, and I really think the project (and others like it) is nice. My comment is directed towards the practical concerns and real-world feasibility of a ternary computer, especially with regards to comments that threads like this inevitably attract (as seen on this comment section) that "ternary computers would revolutionize X", and is partly fueled by me having had non-fuitful conversations with coworkers that insisted on this point in the past. Hopefully this helps contextualize my comment a bit better.
> That said, I don't understand how you arrived at [point 3b]. One can definitely create a circuit which will perform a ternary operation in a (some) constant time. The real question is: can you make a ternary computer which is somehow better than a binary one?
I think you and I are in agreement here, so let me try to clarify what I meant:
My point is precisely regarding the arbitrariness with which "constant time" is defined. Asymptotic analysis of algorithms always treats complexity in the "time" dimension as a measurement of discrete "ticks" on computational state, meaning: you can pick any encoding of data you want, and any set of operations you want, and have any "operation" execute instantly as a tick. When analysing "ticks", an algorithm might seem extremely efficient, however that might be a non-reifiable performance gain when you translate from ticks to milliseconds.
For example: assume a binary NAND gate takes 1ms to propagate a stable output signal. All other conditions being equal with respect to manufacturing technology, voltage, and other things you mentioned, I don't see how you could perform "more" computation at the same cost. Sure you can implement a ternary gate that runs in "constant time", but would that constant time still be 1ms? If yes, would it take up the same amount of die space? If yes, would it consume the same amount of power and dissipate the same amount of heat? etc
You'll eventually be tickling the Landauer limit [0] for whatever your manufacturing technology is at some point, no matter if you're doing binary or whatevernary logic, but getting "more compute" for free would be cheating thermodynamics. Improving manufacturing technology is, of course, a viable strategy for squeezing "more computation" into the same physical space, but switching bases will not immediately make Moore's law wither away.
A more succinct way of putting what I'm trying to say into words I guess would be that "all other things being equal, the choice of base is arbitrary with regards to computational and representational power"
Hopefully this helps clear things up :)
And the Laundauer limit seems completely unrelated. Your link says, "Modern computers use millions of times as much energy per second" -- so we can have 1000x more efficient computer and still be well under the limit.
So the only way to compare the binary vs ternary is in the context of a specific implementation, because that's how you can evaluate the speedup. "All other conditions being equal" is never true -- for example, binary machines can run faster because they need less voltage swing (and thus less bit charge), while ternary machines are faster because balanced adders do not need ripple carry. Which one has more effect? This depends on technology.
Here is a made-up example: let's say we have a small amount of ancient transistors and diodes, and we want to sum up numbers, with range from -5000 to 5000. The transistor switches in 0.1 mS. How do we do it?
In binary, we'd need 14 bit word. Assuming we do ripple-carry adder (it is smallest part count, but slowest), in the worst case we'll need to propagate carry across all bits, and this means we'd need at least 20 mS per operation, getting performance of at most 50 addition/second.
In ternary, we'd need 9-trit word. Ternary adders do not propagate, so we could add the numbers in 2 mS. Here, the ternary is going to be much faster, at 500 addition/sec.
This is a very contrived example (who makes wide ripple-carry adders anyways?) but hopefully this illustrates my point. You cannot use asymptotic analysis for this, and there are times when you can totally perform more computation for the same cost.
Can Ternary Computing Improve Information Assurance? https://www.mdpi.com/2410-387X/2/1/6/htm