Say goodbye to keeping track of the width of signed numbers! Say goodbye to sign extension! Say hello to negabinary!

Negabinary is base -2 (yes, negative two!) -- negative bases indeed exist! Bit 0 of a binary number is the ones digit, bit 1 is the twos digit, bit 2 is the fours digit, bit 3 is the eights digits, and so on. Likewise, a decimal number has a ones digit, a tens digit, a hundreds digit, and so forth. Generalizing this, for base b, there is a b^0 digit, a b^1 digit, a b^2 digit, a b^3 digit, etc. Thus for negabinary, there is a 1 digit, a -2 digit, a 4 digit, a -8 digit, etc. So the first few negabinary numbers are:



In other words, binary 110 is 1 * 4 + 1 * 2 + 0 * 1 = 6, decimal 110 is 1 * 100 + 1 * 10 + 0 * 1 = 110, and negabinary 110 is 1 * 4 + 1 * -2 + 0 * 1 = 2.

There is only one other thing to be aware of. With binary arithmetic, there are two possible values for a carry: 0 and 1. With negabinary, a carry has three possible values: -1, 0, and 1.

Interestingly, an LSR is a negabinary divide by -2, and the least significant digit (i.e. the even/odd status of negabinary number) will be in the C flag. Similarly, an ASL is a negabinary multiply by -2.

Now there is support for other operations! Four routines are provided: convert negabinary to binary, convert binary to negabinary, add, and subtract. They use only one byte of temporary storage (TMP).

Rather than use a pair of 6502 flags to hold the three possible values of a negabinary carry, in these routines, the Y register is used for the negabinary carry. In fact, the Y register holds a negated carry, since the ADD and SUB routines subtract the negabinary carry rather than add it (as ADC and SBC do for binary arithmetic) -- subtracting the negabinary carry simplified the implementation slightly.

In Y, -1 is represented as $FF, which is, of course, two's complement, not negabinary (where -1 is $03). Hey, nobody promised you artistic integrity!

By the way, after an ASL, the C flag contains the negabinary carry; the corresponding values of Y are 0 (for C flag clear) and -1 (for C flag set). One way to implement this is:



The four negabinary routines are:

NEG2BIN converts an 8-bit negabinary number to a (signed) binary number.

BIN2NEG converts a (signed) 8-bit binary number to a negabinary number.

ADD adds a pair of negabinary numbers: the accumulator and a zero page location (specified by the X register). The formula is A+M-C; again, note that unlike the formula for ADC (A+M+C), the carry is subtracted, not added.

SUB subtracts a pair of negabinary numbers: the accumulator and a zero page location (specified by the X register). The formula is A-M-C.

Because the ADD and SUB return carry (out) in the Y register, they can be used to extend negabinary calculations beyond 8-bits in the same way that the ADC and SBC instructions can extend binary calculations, e.g.:



Likewise, multiply and divide by -2 (ASL and LSR) can also be extended.

For more information on negabinary, see:

http://en.wikipedia.org/wiki/Negabinary



Incidentally, BIN2NEG can be implemented in terms of SUB as follows:

I recall discussions concerning negative radix systems from years ago, and back then, didn't think much of the idea. I wasn't aware that anyone had created a Wikipedia article about the topic, but after reading it, I have not changed my opinion. Negabinary still looks like a solution in search of a problem.

In the context of doing real mathematical work within the realm of the 65xx family, I can't see any advantage over other methods that have been in long-term use. While it is conceivable that a negabinary based processing package may be more efficient in some aspects than conventional floating point, integer or compressed BCD methods, the conversion between negabinary and other formats may efface any advantages gained. Certainly the artificiality of using any particular bit as a sign bit and then looking up results in a table to produce the real value is of dubious value. All formats, unless unsigned, require that something represent the sign. So just what is negabinary offering that other processing methods are not?

Also, from a human perspective, the concept is of questionable value, as we upright apes don't think in terms of a discrete positive number representing a negative value, or vice versa. Just how will negabinary benefit the end user? If it really were of value, its wholesale adoption on modern systems would have already taken place.

Other discussions here (especially posts by Garth Wilson) have suggested using scaled integer arithmetic (SIA) in place of floating point methods. For much of what we do with our 65xx systems, SIA is more than adequate and can be made to support a wide range of numbers. In fact, SIA using compressed BCD notation is relatively simple compared to the processing acrobatics required of negabinary (or IEEE floating point, for that matter), with the only real penalties being somewhat less memory usage efficiency and slower processing. Conversion between BCD and ASCII is straightforward and since all 65xx MPUs can add and subtract in BCD, the math routines themselves are not particularly difficult to implement.

SIA treats all internal operations as simple integer processing, and then adjusts the result to the desired level of precision. For example, suppose your math package is doing financial calculations and everything is dollars and cents. You need two-place precision, so you start by taking a value such as 123.45, multiply it by 100, which makes it the integer 12345. Do the same with the other operand. Perform the desired math operation. Finish by reverse-scaling, which would be dividing the number by 100. Note that the only times scaling would actually be required is during input from the user or data source and output to the user or data source. The internal representation can remained in the scaled format.

Point to ponder: to multiply (scale) a binary number in any format by, say, 100 requires a shift-and-add sequence that can eat quite a few clock cycles. To multiply a compressed BCD number by 100 requires one left shift of the entire number, which can be implemented with a very simple algorithm. For example, assuming dollars and cents, the value 123.45, after being entered and converted to compressed four byte BCD, is $00012345. Scaling it by 100 results in $01234500. Reversing the process rescales the number back to $00012345, ready for conversion to ASCII. Can't get much simpler than that.

My point is to illustrate that SIA works well with the 65xx. Why adopt something like negabinary that is less efficient and more complicated?

_________________
x86?  We ain't got no x86.  We don't NEED no stinking x86!

BDD, I will assume you are talking to everyone. Bruce has not been very active here since you got on, but he is our resident algorithms expert. I kind of wonder if he really believes in negabinary. If he does, he will surprise us with good reasons. I suspect he was just introducing an idea just because it's good to not be ignorant about it though. I was not aware of it until now.

The way Forth handles the location of the radix in fixed-point (a special case of scaled-integer) math at input and output time does not even involve shifting, although base conversions do normally require division or multiplication. The efficiency of its base conversions is also the same regardless of base, meaning you use some odd base like 7 or 11 just as easily as 8 or 10.

If Bruce only posts once a year, you have to keep an eye on the date of the post. He always makes sense, but sometimes he's having fun.

Edit: fixup stray apostophe

As Ed noticed, the date was the key piece of information.

Negabinary is pretty solidly in the realm of pure math, but I suppose it's main advantage is (as I alluded to in the first sentence of the original post) the fact that you don't need to keep track of the width, e.g. in two's complement:

$80 is -128
but $0080 is 128
and $FF80 is -128
etc. for $000080, $00FF80, $FFFF80, ...

whereas in negabinary $03 is -1, as is $0003, $000003, etc.

So I suppose it's possible it could be used (in some situations) as a "storage" format, e.g. (like, say IEEE floating point) you'd read it from a file, convert it to a format more suitable to the processor being used (two's complement in this case -- unpacking the sign etc. for FP), perform the calculations, and then convert back to negabinary and write the result.

I also though it was interesting that converting from negabinary to two's complement is very simple/fast -- no loop!

Anyway, I find these sorts of pure math topics fascinating. For those of you who enjoy them too, I've got another pure math topic ready to go which is scheduled to be posted in a few months. In fact, it's (loosely) related to this one, though that may not be obvious at first blush.

(In fact, my original idea was golden ratio base routines, but that seemed a little too obviously facetious for the 6502; I chose negabinary since it at least seemed plausible and the Wikipedia article uses "INTERCAL-72 notation" near the end.)