Slashdot Mirror
Ternary Computing
eviltwinimposter writes: "This month's American Scientist has an article about base-3 or ternary number systems, and their possible advantages for computing and other applications. Base-3 hardware could be smaller because of decreased number of components and use ternary logic to return less than, greater than, or equal, rather than just the binary true or false, although as the article says, '...you're not going to find a ternary minitower in stock at CompUSA.' Ternary also comes the closest of any integer base to e, the ideal base in terms of efficiency, and has some interesting properties such as unbounded square-free sequences. Also in other formats."
... the choices will be 0, 1, and Maybe :)
... this might be an easier step to integrate. There was a previous article here talking about light based quantum computing- give it a few years :)
Actually not a bad step- I wonder when they look at quantum computers using light
They've finally invented my favorite circuit... the Maybe gate?
Fascism starts when the efficiency of the government becomes more important than the rights of the people.
Seems like someone has to bring up base3 computing every once in a while, just like asynchronous circuit design. I'm sure there are plenty of reasons why they are technically superior. But it has taken us 50+ years to get to this point with synchronous circuit design and binary logic. It would take many years to get to this point using totally new technology, and in the meantime the current computer industry would continue to grow exponentially. I'll believe in these technologies when I see a useful example of them.
Try reading Knuth's The Art of Computer Programming, Vol. 2, Section 4.1, Positional
Number Systems.
There is an extended discussion on the balanced
ternary system and some other exotic number
systems (base 2i etc). There are some merits
to the ternary system but it would be
harder to implement with transistors.
Setun operated on numbers composed of 18 ternary digits, or trits
Awww...they shied away from the obvious choice, tits.
Ternary numbers are an interesting sidetrack and some similar techniques are used in fast chip-based systems to speed up adding (each bit also caries it's own overflow and sign bits, turning the classic serial add-with-carry into a more parallel operation).
It must be remembered that, for floating point numbers, base 2 is *the* most efficient representation, as argued in the classic paper "What Every computer Scientist Should Know About Floating Point Arithmetic" by David Goldberg. The deep understanding behind IEEE754 is a masterpiece of numerical engineering that is often overlooked, IMO.
As far as I know radio astronomers user 3-level data recording for their VLBI (Very Long Baseline Interferometry) data. One of the equipment was from JPL at Caltech lab. Their problem is to detect a weak signal in presence of strong noise. In this case, it doesn't make sense to do 8-bit digitization. Instead people do 1-bit, 2-bit digitization and average out many sample of data. They found that the recording efficiency was highest when they used 3-level digitization.
I myself worked on VLBI in the same lab but our machines were using 1-bit digitization (BTW, we used regular video cassette and somewhat modified VCR to record 7 GBytes on single 2-hour tape).
Nope: one, zero, and CowboyNeal.
I have seen in one book that there was created a ternary computer long time ago. I have tried to find anything with google and found this page.
--
Ilya Martynov (http://martynov.org/)
Close, but you are still doing digital computing! Just because it's not binary doesn't mean it isn't digital.
The problem is understanding the new metaphors required to implement new modes of math. Simply adding a third state doesn't get you a revolutionalry new mode of computation, it just gets you more bits per wire. For example, look at flash technology: they now store multiple bits per cell by designing sense amps to convert the analog level to a binary pattern.
Read the book "An Introduction to Quantum Computing". I forget the author, but it's the one that comes with the CD of mathematica examples.
In this book they discuss a simple adder that Feynman derived. The realization of the Hamiltonion operator (similar to the transfer function H(s)) requires a gate called:
Square root of NOT!
It's pretty crazy, but when you walk through the example step-by-step, it becomes more clear why it is needed to build the simple adder.
Now how you actually build a root-not gate is another problem, but I'm just making this point to illustrate how "meta" the new concepts have to be to truly revolutionize computation.
There's simply nothing better than binary right now.
https://www.accountkiller.com/removal-requested
Think about applying it to D/A and A/D conversion for AC signals. It could simplify a flash converter,a nd conversion to convention twos-complement signed integers can be performed by a hard-wired lookup table.
-jcr
The only title of honor that a tyrant can grant is "Enemy of the State."
If bits becomes tits, then I say bytes should become teats.
And, instead of a 'nibble' being four bits, we'd have a 'suckle' equaling three tits, like that babe in the movie Total Recall.
Instead of dealing in megabits or gigabytes, we'd have gigatits, which could be abbreviated as DD, saving vast amounts of bandwidth -- which might as well be called handwidth now -- or terateets, abbreviatable as DDD.
With all the sexual content in technical lingo (e.g., male and female plugs, master/slave, unix, etc.) this is only a natural development, and given that half of these machines are used for nothing but downloading pictures of naked breasts anyways...
Is this truly the only Earth I can live on?
I looked over the article and it made a good arument for a ternary computing architecture, however there are some big problems with this that were not addressed in the article. Although I'm not a math expert, I did gain a math minor in college during my computer engineering curriculum, and I have to say ternary computing seems to have too many complex problems that need solving to be worth it.
First of all, hardware is getting smaller and smaller all the time, so the whole premise behind ternary computing (base 3 would use less hardware) doesn't apply, especially since brand new gates would have to be made in order to distinguish between 3 signal levels rather than 2, and that would be taking a HUGE step backwards.
Secondly, doing things on a chip or two is great, but the main problem in computing is communications. The major part of creating efficient communications protocols is determining the probability of a bit error. Probability is a very complicated science, even using the binary distribution, which is a very simple function (that just happens to escape me at the moment.) Now, add another bit, and you have to use a trinary distribution, which I'm sure exists but isn't very common (and not surprisingly, I can't recall that one either). Long story short, this theoretical math has been made practical in computer communications over a long period of time dating back 50 years, starting all over with 3 bits rather than 2 would be extremely complicated and VERY, VERY expensive.
Finally, figuring out logical schemes for advanced, specialized chips is a daunting task. Engineers have come up with shortcuts over the years (K-maps, state diagrams, special algorithms, etc) but adding in a 3rd state to each input would make things almost impossibly complicated. All computer engineers working at the hardware level would have to be re-educated, starting with the simplest of logical gates.
Overall, in my humble opinion, we'll never see large scale use of ternary computing. There's just too much overhead involved in switching over the way of doing things at such a fundamental level. The way hardware advances each year, things are getting smaller and smaller without switching the number base, so until we reach the limit using binary, we'll probably stick with it.
~ now you know
As if in precognition, a language has already been developed for ternary computers:
TriINTERCAL! (the link is about INTERCAL, chapter 6 is about the TriINTERCAL extension)
I can't wait until college courses are taught in this truly wonderous and -- who would have thought -- futuristic language.
The enemies of Democracy are
and rain on the computer scientist's parade, but...
.5? Is it your ternary maybe, or is it the circuit switching from 0 to 1? And what about the case when your manufacturing process introduces errors greater than you expected? What if 1 comes out .75? Is that in the maybe range or the 1 range?
The reason that you can't get, and won't for a long time, anything greater than base 2 is that setting and sensing more than two logical levels in a given voltage range is very hard. Those ones and zeros you like to look at and think about discretely are not really ones and zeros, but voltages close to those that represent one and zero, close enough to not confuse the physics of the device in question.
For example, if you arbitrarily define 0 volts to be a 0 and 1 volt to be 1 in an equally useless and arbitrary circuit, and you monitor the voltage, what do you assume is happening if one of your discrete samples is
Now, I remember something about double flash memory densities by sensing 4 voltage ranges in each cell, but I imagine the timing precision required to do that correctly is orders of magnitude easier to do (and still a royal pain) than putting ternary logic into a modern microprocessor (with tens of millions of transistors, implementing everything created in the entire history of computing that might be even marginally useful so that you can 3 more frames per second in quake3).
Outside of a dog, a book is a man's best friend. Inside a dog, its too dark to read.
I am shocked, shocked to discover that a fundamental computer architecture explored in the 1950's, rejected as unworkable, and forgotten is in fact unworkable.
The feeling that this induces has no word in English, but in Japanese it's called yappari.
A friend and I were thinking about representations on a ternary system. We had to figure out what units of storage would be available.
;-)
Obviously, there's the basic unit of storage (1, 0, -1; on, off, undefined; true, false, maybe; whatever). We called this a trit for obvious reasons of parallel to the binary world.
Ok, good enough so far. Then, there's the basic unit that's used to store characters or very simple numbers. We decided that 9 trits would be good (this was to allow for UNICODE-like representations). This seemed to be a shoe-in for the title, tryte.
Then, you occasionally want to have something that is used in firmware to sub-divide trytes into various fields. In binary we call this a nibble, so in honor of Star Trek we called this one (3 trits) a tribble.
But, there it stopped, as we soon realized what we'd be measuring the system's word-size in.... Man, I thought SCSI was a painful phrase to use all the time
Excellent. This will translate Tri-Intercal, with native bitwise trinary operators, into much more efficient machine code.
As long as we're turning the world on its ear, lets go all the way, and use triacs. We implement it (the tri-state gate, that is) like an inverter, more-or-less. These have two (non-linear ) on states plus off, and are just right for implementing an inverter. They'd probably be great for trinary logic, too.
I just dug out my old physical electronis book (Micro Electronics, by Jacob Millman, First edition), and can't find them in there, so here's a slightly less academic reference.
There might be some problems with trying to get the clock speed high enough to compete with the Intel/AMD marketing, though; it says that they can be triggered into conduction by high dV/dt.
See what I've been reading.
I've read a lot of posts on how this will be difficult to implement using voltages and circuits....and you know what? It *IS* difficult to sense 3 different voltage.
The solution? Don't use electric circuits...don't use transistors.
Electric circuits will only get us so far, and then we'll have to move on to more 'exotic' hardware -- optical computing, molecular computing, quantum computing.......
Suppose a qubit's state is describe by the spin polarization of an electron pair -- they can either be both up, both down, or one of each -- you can't tell which one, so it's actually 3 states (balanced at that)......
In optical computing, suppose you can push the frequency of the lasers a little in either direction of 'neutral'...this is also base 3.
So what I'm trying to say is, don't just say "base-3 computing is not practical with current technology" -- because it isn't, but it WILL be practical (perhaps even more so than binary computing) with future technology.
And to finish with something lighter...
troolean x, y, z;
x = true;
y = false;
z = existentialism;
:)
"You have the option of insanity. I do not. And that makes me crazy!" - Brian to Angela, My So-Called Life
Actually apart from the colors, all the other
particles are come in (isospin) pairs.
Under SU(2) (weak force pairs)
Electron Neutrino
up down
strange charmed
bottom top
proton neutron (which is up down again)
blue red green because color has
SU(3) symmetry
You really couldn't be more wrong! Ternary logic is at the basis of some of the hottest research in asynchronous logic design right now.
For instance, if you had a group of transistors that computed multiplication and stored the output in a register you might see the value of that register change several times until the computation was completed. Right now, the only way that you know a computation is complete is that logic is designed to complete an action in X cycles; as long as you feed in the data and wait X cycles you will get the proper result. Clock cycles can be waisted here, because a simple multiplication might be completed in a single clock while harder multiplications might take the full amount of time the logic area is spec'ed for.
Using async logic, this can be done much more effciently. The multiplication happens just as soon as input data is given and the next stage of the logic knows when the operation is complete because its wires has three states: 0, 1, and not-yet-done. As soon as all the wires are 0 or 1, the computation is finished (consequently, this is how input works to). There are no "wasted" clock cycles, stuff moves through the logic as quickly as it is completed.
Of course, there has been some debate whether three states are needed on each wire, or an just additional acknowledgement wire is needed (say 8 wires + 1 for an 8-bit computation block). But, believe it or not there are already patents for both methods!
I guess, by having true ternary logic on each wire, you could have logic that will grab a result just as soon as X% of the wires report they are done with the computation to get "good enough" answer if the logic is iteratively improving a problem.
-AP