research!rsc

Thoughts and links about programming, by

Bi-quinary and other bases
Posted on Friday, April 11, 2008.

Doug McIlroy's talk on History of Computing at Bell Labs mentioned that George Stibitz's relay-based decimal calculators that stored digits in what he called bi-quinary: “Arithmetic was done in bi-quinary, a two out of five representation for decimal integers, and if there weren't exactly two out of five relays activated it would stop.” This allowed a sequence of computing jobs to run unattended over the weekend: if the computer detected an error (not exactly two relays active in some digit), then it would stop the current job and start over.

McIlroy's description of the number system as being 5 bits differs from any of the representations given by the Wikipedia entries for bi-quinary coded decimal and biquinary, which describe a system that is basically unary: 5 bits to count 0 through 4 (only 1 bit on at a time) and two top bits: 01 = 0, 10 = 5. Other historical summaries you can find online by searching for Stibitz and bi-quinary seem to back up Wikipedia. In this version, bi-quinary was 1-of-2 plus 1-of-5, not 2-of-5. In the 7-bit version, the bit positions are worth 5, 0, 4, 3, 2, 1, and 0, which isn't very interesting. It's far more interesting to think about the 2-out-of-5 system.

The valid codes in a 2-of-5 system like McIlroy described would be 00011, 00101, 00110, 01001, 01010, 01100, 10001, 10010, 10100, 11000. If you assign these the values 0 through 9, you can set up a system of linear equations and solve them to find the value of each of the five bit positions b4, b3, b2, b1, and b0. The fact that 00011 = 0 means that b1 + b0 = 0. The fact that 00110 - 00101 = 2 - 1 = 1 means that b1 - b0 = 1. These two equalities imply b1 = ½ and b0 = -½. Given that you can pick out the other bits fairly easily: from right to left the "places" are -½, ½, 1½, 3½, and 6½. This works for 0 through 8 but then, sadly, fails for 9: 11000 = 6½ + 3½ = 10. No other code assignment has a solution either (I wrote a small program to try them all.)

I guess that's why the 1-of-2 plus 1-of-5 form was more popular than 2-of-5: it was probably easier to design the arithmetic circuits if each bit could be assigned a particular value. It's too bad, because 2-of-5 would have mathematical elegance on its side if it could be made to work.

If you dig around, you can find other esoteric number representations: negabinary has base -2 (negative two), so the positional values are 1, -2, 4, -8, and so on. Thus 5 is 101 but 3 is 111 = 1-2+4. Negabinary appears to have been first invented by Vittorio Grunwald in 1885. It was used in a few experimental computers in the 1950s, but it didn't catch on. Even weirder than negabinary numbers are the quater-imaginary numbers, invented by a high school student named Donald Knuth in 1955. Those use base 2i (where i is the imaginary square root of -1). (Knuth is also responsible for the negabinary history.)

Odder still are balanced ternary (ternary but digits are -1, 0, and 1) and Bubble Babble, but no discussion of interesting counting systems or high school math nerds would be complete without mentioning counting on your fingers in binary.

(Comments originally posted via Blogger.)

  • robx (April 11, 2008 10:48 AM) Factorials are another interesting base (that's lacking a wikipedia article). It's particularly useful for enumerating permutations. I can't find any better references than or this, unfortunately

  • Chris Lesniewski-Laas (April 11, 2008 7:00 PM) Balanced ternary is great for parallel big-number multipliers because you don't need to propagate carry bits arbitrarily far. I used balanced N-ary for my RSA-on-a-GPU implementation.

  • Derek Peschel (July 27, 2010 8:03 AM) Relay telephone switches use a 2-out-of-5 code very similar to the one you describe. Give the bits the values 0, 1, 2, 4, and 7. Then look at the code as storing the digits 1 through 10, not 0 through 9. (Why? because the switch is reading dial pulses from a rotary phone.) Note how each bit value is ½ more than yours.

    One bar-coded form of ZIP code on envelopes—the one with the bottoms of the bars lined up—uses the same encoding. The version where the tops and bottoms of the bars stick out from the middles uses a much sparser encoding with more error checking.

    If you're in Seattle and you want to see some working Bell Labs relay switches, check out the Vintage Telephone Equipment Museum.