This column builds on A prior column on "Just in Time Subtraction"
What is Balanced Ternary Arithmetic?
Well, it is a modification of standard base three arithmetic.
OK, what is base three (ternary) arithmetic?
Base three arithmetic is like base 10, except that we only have digits 0, 1, 2 instead of 0 through 9. This means that counting has to carry to the next column after your digits get bigger than two, instead of when they get bigger than nine. In base 10, an integer has a "one's column", a "ten's column", a "hundred's column", and so on. In base 3, an integer has a "one's column", "a "three's column, a "nine's column", and so on.
On to balanced ternary
Balanced ternary is almost exactly like regular ternary arithmetic, except that instead of digits being 0, 1, and 2, they are +1, 0, and -1. This is awkward to write, so I'll follow a common convention and use "+", "0", and "-" as the digits.
Terminology aside: In binary, a digit is referred to as a "bit", short for Binary digiIT. In ternary (or balanced ternary) a digit is called a "trit", short for TeRnary digIT.
Lets try counting:
Base 10, Binary, Ternary, Balanced Ternary
0, 0, 0, 0
1, 1, 1, +
2, 10, 2, +-
3, 11, 10, +0
4, 100, 11, ++
5, 101, 12, +--
6, 110, 20, +-0
7, 111, 21, +-+
8, 1000, 22, +0-
9, 1001, 100, +00
10, 1010, 101, +0+
11, 1011, 102, ++-
12, 1100, 110, ++0
13, 1101, 111, +++
14, 1110, 112, +---
15, 1111, 120, +--0
16, 10000, 121, +--+
17, 10001, 122, +-+-
18, 10010, 200, +-+0
. . . .
. . . .
. . . .
I imagine that many of my readers are looking at that last column and cringing. No doubt many feel that it is ugly, complex, non-intuitive, etc.. And, I'm sure some question why anyone, in their right mind, would want to compute in balanced ternary.
I don't think anyone would actually want to compute in it. But it, like binary, is great for COMPUTERS to compute with. Balanced ternary does have many nice properties. The famous computer scientist/mathematician Donald Knuth described it as the most elegant of the number bases. For example, in the traditional number bases you have a negative number you mark it with a negative sign ("-6", for example). This convention is called "signed magnitude form". In binary, this convention leads to more complexity in the logic than some other choices. Other representations include "two's complement binary" and "One's complement binary" representations. You don't need to know what these are for this discussion, and you can Google them if you want details. But with balanced ternary you don't need anything other than the number, since the left most non-zero trit is not only a digit, but is also the sign of the number, so we don't need anything extra. As Knuth points out, rounding and truncating are EXACTLY the same in balanced ternary. This is true even to the left of the ternary point if you understand "truncating" as "make all digits to the right be zeros". So there is no complex code needed to deal with rounding. Negating a number is just "flipping the signs all the way through. For example 6 is +0-, and negative six is just -0+. For arithmetic logic units balanced ternary has numerous advantages. For example, the multiplication times table has *no* carries.
Balanced Ternary
Multiplication Addition
* | - 0 + + | - 0 +
--.------ --.-----------
- | + 0 - - | +- - 0
0 | 0 0 0 0 | - 0 +
+ | - 0 + + | 0 + -+
0 carries 2 carries
Contrast with Ternary
* | 0 1 2 + | 0 1 2
--.-------- --.---------
0 | 0 0 0 0 | 0 0 0
1 | 0 1 2 1 | 0 1 10
2 | 0 2 11 2 | 0 10 11
1 carry 3 carries
Technical/historical aside: Most modern machines using binary use two's compliment arithmetic for signed numbers, because it is straight forward to implement, intuitive, and easy to describe. Some computers (Univac mainframes, CRAY super computers and some others) use one's complement arithmetic instead. As an example of disadvantages of one's complement include that it has both a positive and a negative zero, and it can count down one more than it can count up. The arithmetic unit has to do an "End around carry or borrow" in many cases to make the arithmetic work. An obvious question is why anyone would want to use representation that has those bad properties. I'm told that the answer is that they didn't really want to, but IBM had patents on two's compliment arithmetic, which effectively prevented others from using it. So why is it that modern machines are almost all using two's complement? Simple, the patents expired. END ASIDE
Why do computers, almost universally, use binary, instead of ternary or balanced ternary? Slamming a current level all the way on, or all the way off, is a good match for a transistor, or even a vacuum tube. Trying to exactly hit any intermediate level exactly leads to much more complexity. Transistors devices that can drive a line positive, negative, and zero are much more complex than a single transistor. Why would Russian's Setsun series computers use balanced ternary anyway, given the engineering issue above? I'm told that they didn't want to. But after the US invented the transistor, the military uses were clear... you could (for example) make smaller, lighter, more reliable missile guidance systems. So the US restricted the export of transistors. So in Russia, Computer Science folk at Universities had a very hard time getting access to them. [Of course, they did get them, but they were big budget items due to the difficulty of getting the transistors.] Therefore they were not cost effective for computer logic units. So, what is an engineer to do? You can do logic with things other than transistors. Vacuum tubes work, but are unreliable and relatively short lived, easily broken, quite expensive, and relatively large (100's of times larger).
You can reliably tell the difference between current in one direction, current in the other direction, or no current at all. But, if you wind coils on a metal rod or donut, you can use it for logic. A perfect match to balanced ternary. And diodes were available.
Example of two coils on a metalic rod: Opposite directions In the same direction. | - 0 + | - 0 + --.------ --.------- - | 0 - 0 - | - 0 0 0 | - 0 + 0 | - 0 + + | 0 + 0 + | 0 0 +
You can combine signals directly by different winding arrangement and organizations, and while the russians didn't have easy access to transistors, they had access to diodes (which had been around at least since the old crystal radios)
You can use many many windings on one core, if the windings have the same orientation this is an "OR" gate, with however many inputs as you want. You can make a "NOT" of a signal by reversing the direction of the winding. (You get zero if it is zero, and the opposite direction otherwise. Just like "NOT AND" and "NOT OR" can generate any other binary function, there are "complete" functions for three valued logic. And, there are a lot more than two of them, leaving a lot of room for creative design. You can send the output to other logic gates also, and assemble much more complex logic units.
In a ternary, or balanced ternary, computer one has to communicate with humans, and binary computers. So code or hardware needs to be able to convert balanced ternary (or ternary) numbers to base ten for people, and two or eight for binary computers. There is an method discussed in Just in Time Subtraction I and Just in Time Subtraction II that provides fast divides by any power of the base plus or minus 1. In decimal, that gives you divides and modulo by 10-1 = 9) and 10+1 = 11, 100-1 = 99 and 100+1 = 101... which doesn't seem all that useful. But in base three (balanced or not) it gives fast divides (and modulo functions) by 3-1 = 2, 3+1 = 4, 9-1 = 8, 9+1 = 10, ... Both 2 and 10 are exactly what we need to convert numbers for use by binary computers and humans.
Navigation:
No comments:
Post a Comment