Integer Vitae IIIA

.. I.V. IIIA republishes I.V. III without the crappy formatting (my hour on the library computer ran out and then came Thanksgiving).

Remember?

…, 1010, 1011, 1000, 1001, 1110, 1111, 1100, 1101, 10, 11, 0, 1, 110, 111, 100, 101, 11010, 11011, 11000, 11001, 11110, ...

Reprise:

.. No other digits ==> binary
.. Context free ==> “0” is always 0, “1” is always 1 ==> no minus sign even for negative integers
.. Extrapolation, and considering that log2(21) = 4+ suggests a unique total unsigned representation
.. Pairs, e.g. “0” “1”, “110” “111”, suggest radix or at least some kind of positional notation
.. Aha: radix, base -2

.. In I.V. II, I mentioned, “Arithmetic? Looks dicey, but simple algorithms must exist, because indeed this is a familiar radix system (successive positions indicate successive powers of the so-called base).” Well, I know you have been slavering over that ever since (unless you worked it out for yourself). Subtraction is just a dialect of addition, really, and for the sake of brevity we shall pass over division in blessed silence; so that leaves addition and multiplication. The algorithm is the same for any radix: add digitwise with carry; multiply digitwise, aligning the partial products with the digits of the multiplier, and add them. These operations require tables of addition and multiplication for single digits—and that is really the only difference between different bases. And multiplication’s table is the same for the corresponding portion of the table for any base:

..... x : 0 1
..... --:-----
..... 0 : 0 0
..... 1 : 0 1

.. So, really, it’s all about addition. And here is something new: using this addition table

..... + : 0 1
..... --:------
..... 0 : 0 1
..... 1 : 1 110

try adding 11 + 1. The algorithm breaks down, with infinite recursion. Here is the minimal addition table required for base -2:

..... + : 0 1 11
..... --:---------
..... 0 : 0 1
..... 1 : 1 110 0
..... 11 : 0

Examples:

....... 10 (-2) .. 10 (-2) .. 11001 (+9) ..... 11001 (+9)
..... + 11 (-1) .x 11 (-1) . + 1110 (-6) .... x 1110 (-6)
..... --------- .--------- . ----------- .... -----------
..... 1101 (-3) .. 10 ....... 00111 (+3) .... 11001
................. 10 ....................... 11001
.................--------- ................ 11001
................. 110 (+2) ................ --------------
........................................... 11011110 (-54)

.. OK, does base -8 relate to base -2 the way octal relates to binary? Sure.

.... (-2) (-8)
.... --------------------
.... 010 . -2 written “X”
.... 011 . -1 written “Y”
.... 000 . 0 same as “Z” (to help you remember “X” and “Y”)
.... 001 . 1
.... 110 . 2
.... 111 . 3
.... 100 . 4
.... 101 . 5

.. Our version of “negoctal” uses the digits -2,…,5 (eight in all).

Example: 11,011,110 (base -2) = YY2 (base -8) = -54 (decimal).

.. Here are the addition and multiplication tables for base -8:

.... + : X Y 0 1 2 3 4 5
.... --:------------------------
.... X :14 15 X Y 0 1 2 3
.... Y :15 X Y 0 1 2 3 4
.... 0 : X Y 0 1 2 3 4 5
.... 1 : Y 0 1 2 3 4 5 YX
.... 2 : 0 1 2 3 4 5 YX YY
.... 3 : 1 2 3 4 5 YX YY Y0
.... 4 : 2 3 4 5 YX YY Y0 Y1
.... 5 : 3 4 5 YX YY Y0 Y1 Y2

.... x : X Y 0 1 2 3 4 5
.... --:------------------------
.... X : 4 2 0 X 14 12 10 1X
.... Y : 2 1 0 Y X 15 14 13
.... 0 : 0 0 0 0 0 0 0 0
.... 1 : X Y 0 1 2 3 4 5
.... 2 :14 X 0 2 4 YX Y0 Y2
.... 3 :12 15 0 3 YX Y1 Y4 XY
.... 4 :10 14 0 4 Y0 Y4 X0 X4
.... 5 :1X 13 0 5 Y2 XY X4 151

.. Note that 5x5 is three digits long.

.. There is no end to this silliness. Here are some central integers (from -20 (decimal) to +20 (decimal)) in base -3, using the digits -1 written “Y”, 0, and 1 (note the antisymmetry around 0):

…, 1111, 110Y, 1100, 1101, 11YY, 11Y0, 11Y1, Y1Y, Y10, Y11, Y0Y, Y00, Y01, YYY, YY0, YY1, 1Y, 10, 11, Y, 0, 1, YY, Y0, Y1, 11Y, 110, 111, 10Y, 100, 101, 1YY, 1Y0, 1Y1, YY1Y, YY10, YY11, YY0Y, YY00, YY01, YYYY, …

Well, there you have it.