Syntactic Confectionery Delight PerlMonks

### Re: Negabinary Number System

by Cirollo (Friar)
 on Sep 06, 2001 at 03:19 UTC ( #110446=note: print w/replies, xml ) Need Help??

in reply to Negabinary Number System

Maybe you should take a more serious look at the balanced ternary number system. (described in TAOCP, vol. 2 ch. 4.1, p207, you've probably already read about it)

Knuth says it is "perhaps the prettiest number system of all," and it has some properties that are quite beautiful. For those who aren't familiar with balanced ternary notation, it's similar to what you would expect of base 3 - except, instead of the digits 0, 1 and 2, one uses -1, 0 and 1 (-1 being denoted by a 1 with a bar over it).

Like negabinary, this system is unsigned; instead, the sign is captured in the representation of the number itself. And, according to Knuth, a balanced ternay representation of a number requires only about 63% as many digit positions as its binary representation.

There were even a number of computers built based on the balanced ternary system. Instead of using "off" and "on" in an electrical system, I assume one would use "positive," "negative," and "off" voltages, which is really an interesting concept.

Replies are listed 'Best First'.
Re: Re: Negabinary Number System
by dragonchild (Archbishop) on Sep 06, 2001 at 18:20 UTC
It makes perfect sense that representation that gets to use 150% more types would need roughly 66% as many positions. *grins*

Tell us more about balanced ternary, please. Why is it pretty? (What is TAOCP?)

------
We are the carpenters and bricklayers of the Information Age.

Vote paco for President!

Ah, sorry. TAOCP is The Art of Computer Programming by Donald Knuth.

Here are some of the reasons Knuth gives for the "prettiness" of balanced ternary:

You can get the negative of a number simply by interchanging all of the 1's and -1's.

The sign of a number can be found from it's most significant (aka leftmost) nonzero digit; positive if it is 1, negative if it is -1 (again, the sign is contained in the number itself)

The operation of rounding to the nearest integer is identical to truncation, or simply deleting everything to the right of the radix (decimal) point; this is another consequence of using a "balanced" system. The reason for this is that fractional values will range from -1/2 to 1/2 (the largest fractional value you could have, 0.1, is 1/2 in base 10); so, any fractional number is expressed as it's nearest integer, plus or minus some value up to 1/2.

TAOCP is The Art of Computer Programming.

A few reasons why Knuth considers it as pretty are:
1)The negative of a number is obtained by changing all 1s to -1s and all -1s to 1s;
2)The sign is the sign of it's most significant trit (trinary digit); and
3)Rounding to the nearest integer is identicle to truncating.

Oh, and Cirollo; thanks for the reminder. I had forgotten about the balanced ternary system, but remembered it once I saw the name of it. Perhaps I will do my research on that, I'll wait and see. Update:Hey Cirollo, looks like you beat me to the punch : ) Thanks again!

The 15 year old, sophmore programmer,
Stephen Rawls

Create A New User
Node Status?
node history
Node Type: note [id://110446]
help
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others contemplating the Monastery: (4)
As of 2018-01-21 05:55 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
How did you see in the new year?

Results (227 votes). Check out past polls.

Notices?