P is for Practical PerlMonks

### Negabinary Number System

by srawls (Friar)
 on Sep 05, 2001 at 23:28 UTC Need Help??

Hey all, been a while since I've been here, glad to be back! Anyway, this is a bit off topic to perl, but still related to programming in general; It's a question, but I didn't think it fit in the Seekers section (editors feel free to move it if you disagree). I am planning ahead on doing a mentorship project for next year. I want to do it on the prospect of using the negabinary number system in computer architecture, and how it would effect programming. Now, I have The Art of computer programming, and I got the idea from there (though sadly it is just a sentence, explaining the existance of such a number sytem only--in another book, it is merely a footnote). I have been looking all over the internet, and even in libraries, to no avail, thus I come here.

Do any of you have knowledge of this system? I have racked my head over it, but cannot figure out a boolean gate system of adding numbers together, if any of you know how to do this, I would be very apreciative. Also, in the Art Of Computer Programming, Knuth talks about a computer being built for use with the negabinary system, but doesn't develop anything from that; I was wondering if any of you knew where I could find information about that?

I know this is a lot to ask, but even just a point in the right direction would be helpful; I've exhasted all the means I know of (except for a few nasa-engineers that I know, that I plan to ask shortly), and I would appreciate just the mention of a place to look. Thanks all! P.S. For those who don't know, the negabinary system is almost like binary (base 2), but it is base -2. Thus, the 'columns' read 1,-2,4,-8,16,-32,64 ... instead of 1,2,4,8,16,32,64 ...

The 15 year old, sophmore programmer,
Stephen Rawls

Replies are listed 'Best First'.
Re: Negabinary Number System
by Cirollo (Friar) on Sep 06, 2001 at 03:19 UTC
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.

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

Re: Negabinary Number System
by jepri (Parson) on Sep 06, 2001 at 00:56 UTC
I have no information on the negabinary counting system, but I have noticed that every time someone uses an odd numbering system, it is because there is a benefit for certain kinds of operations. This is exactly the reason we can all count in octal and hex - they line up on byte boundaries, so we can conveniently represent the binary data in a form we can deal with.

What benefit do you get from using negabinary? Try a few operations and see if any patterns fall out. Try left shifting and right shifting numbers. What happens when you mask numbers with an and? Do the numbers cover a more convenient range? For what applications is it more convenient to count from -170 to 85?

____________________
Jeremy
I didn't believe in evil until I dated it.

Re: Negabinary Number System
by dragonchild (Archbishop) on Sep 06, 2001 at 00:03 UTC
That's an interesting concept. So, if we use this system, the first few numbers would be:
1. 0000 0001
2. 0000 0110
3. 0000 0111
4. 0000 0100
5. 0000 0101
6. 0001 1010
7. 0001 1011
8. 0001 0000
9. 0001 0001
10. 0001 0110
The system goes from -170 to 85, giving us 256 possible numbers, as we should have.

Does that look correct? What are the possible benefits to the negabinary system? What calculations does it make easier that binary has a problem with? I know that it would make working with negative numbers much easier, but why is that a problem with the current high-bit-flip?

Update: Just as a thought, wouldn't an inverse negabinary system work better? You'd go from -85 to 170 in an 8-bit number, which would allow more positives than negatives, which would seem more useful. (Interestingly enough, 85 * 2 = 170 ...) In that system, you'd have:

1. 0000 0011
2. 0000 0010
3. 0000 1101
4. 0000 1100
5. 0000 1111
6. 0000 1110
7. 0000 1001
8. 0000 1000
9. 0000 1011
10. 0000 1010
(Coincedentally, the second list is the negative numbers from the first system, and vice versa.)

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

Vote paco for President!

Actually, an inverse negabinary would have the same problems. Notice that if you use 9 bits in a regular negabinary system, you get numbers from -170 to 341 -- each time you add a bit, you go from having 1/3 negative numbers and 2/3 positive numbers, to having 2/3 negative numbers and 1/3 positive numbers, and vice versa. An inverse negabinary system would simply reverse which occurs during an odd number of bits and which occurs on an even number of bits.
Re: Negabinary Number System
by mitd (Curate) on Sep 06, 2001 at 05:23 UTC
See if your library can dig up a copy of Scientific American, April 1973. Martin Grdner's column is all about Negabinaries. Unfortunatly http://www.sciam.com/ only has back issues from 1998 online. But they do publish an archival CD maybe your library will have that.

I also found several articles/papers concerning Negabinaries in Optics and VLSI. Search at www.google.com for negabinary.

It would appear that coming up with a decimal to negabinary converter is a favourite assignment for Comp-sci profs. :)

Good Luck

'My favourite colour appears to be grey.'

Re: Negabinary Number System
by John M. Dlugosz (Monsignor) on Sep 06, 2001 at 02:40 UTC
I agree with everyone else I think. Instead of racking your brains to figure out how to do that with gates, figure out what naturally uses this system and map numbers to that system. We use binary two's compliment because that's what gates really like.

But "grey code" is kind of wierd, similar to your negbinary system, and it's not good for gates. But, it's very good for positional encoding of a shaft, since only one bit changes at a time.

So, think about what really works that way. It sounds like something swinging back and forth and getting higher each swing, like an amplifier sinewave, with + being left and - being right.

So think about a spring-driven system. The restoring force is proportional to the displacement, and this produces nice sine waves. If force is constantly being added (or the restoring force constantly weakening) what power curve would be needed to give each turn-around point twice as far away as the previous?

IAC, keep us posted.

—John

Of course, this only corresponds to an idealized driven-spring system, because the restoring force-displacement proportionality is only linear for small displacements, and it isn't 100% accurate (in a real physical system), because the return force is also proportional to the displacement squared, and cubed, and so on. The effect of the higher order proportionalities is just negligible for small displacement.

My point is that you could conceptualize the system as a system of springs, or a driven LC circuit, but if you were to try to actually build some sort of device to do calculations using the idea, it would quickly become inaccurate.

Which is exactly why analog computers fell out of favor, except for really specialized applications that can't be approached in any way other than modeling the system.

What else naturally alternates in two directions? And is digital in nature, no less? Natural positional systems are like car odometers.

Create A New User
Node Status?
node history
Node Type: perlmeditation [id://110395]
Approved by root
help
Chatterbox?
and snow settles gently...

How do I use this? | Other CB clients
Other Users?
Others wandering the Monastery: (2)
As of 2018-05-28 00:35 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
World peace can best be achieved by:

Results (198 votes). Check out past polls.

Notices?