Base sqrt(2)

So, everyone knows and loves positional number systems of different bases. We use base 10 every day, and base 2 if you are a computer, with base 16 as a more compact form that us humans enjoy. Our system of time and measuring circles in degrees uses base 60.

What might happen if you tried to build a positional number system around 2? In a positional number system each digit contributes to the value of the number by weighting the base to a power based on the position. The weights are required to be integers less than or equal to the base. Thus:

(437)10 = 4 × 102 + 3 × 101 + 7 × 100
        = 400 + 30 + 7
(110101)2 = 1 × 25 + 1 × 24 + 0 × 23 + 1 × 22 + 0 × 21 + 1 × 20
        = 32 + 16 + 4 + 1 = (53)10

If the rule is that each weight must be an integer less than the base, then for base \sqrt{2}, the weightings could either be 1 or 0. For example:

(1100101)_{\sqrt{2}} = 1 \times \sqrt{2}^6 + 1 \times \sqrt{2}^5 + 0 \times \sqrt{2}^4 + 0 \times \sqrt{2}^3 + 1 \times \sqrt{2}^2 + 0 \times \sqrt{2}^1 + 1 \times \sqrt{2}^0
             = 1 \times 2^3 + 1 \times 2^2\sqrt{2} + 0 \times 2^2 + 0 \times 2^1\sqrt{2} + 1 \times 2^1 + 0 \times 2^0\sqrt{2} + 1 \times 2^0 \\ = 8 + 4\sqrt{2} + 2 + 1 = 11 + 4\sqrt{2}

The interesting thing to note is that the even powers act just like base 2, and the odd powers act just like base 2 multiplied by a factor of \sqrt{2}. Addition is similar to binary addition, except that carries skip adjacent digits and go to the next digit. That is, a carry out in an even position is a carry in to the next most significant even position, and a carry out from an odd position is a carry in to the next most significant odd position.

It would be more convenient to split a base \sqrt{2} number into a rational part, that is a regular binary number, and an irrational part that is also a regular binary number, but that is multiplied by \sqrt{2} when computing the value of the number.

Using this representation, any base \sqrt{2} can be represented as two binary integers. Addition, subtraction, and multiplication are straight forward. For addition, add the real parts and the rational parts separately to get the result. That is, to add two numbers a and b,

 (a_r + a_i \sqrt{2}) + (b_r + b_i \sqrt{2}) = (a_r + b_r) + (a_i + b_i)\sqrt{2}

where a_r is the rational part of a, a_i is the irrational part of a, b_r is the rational part of b, and b_i is the irrational part of b. Subtraction can be implemented as addition of the inverse.

Multiplication works in the straightforward way:

 (a_r + a_i\sqrt{2}) \times (b_r + b_i\sqrt{2}) = (a_r b_r + 2 a_i b_i) + (a_r b_i + a_i b_r)\sqrt{2}

Division by a purely rational divisor follows the standard rules. Both the rational and irrational parts are divided by the divisor. If the divisor is not purely rational, it can be carried out as follows:

{(a_r + a_i\sqrt{2}) \over (b_r + b_i\sqrt{2})} = {(a_r + a_i\sqrt{2}) \over (b_r + b_i\sqrt{2})}{(b_r - b_i\sqrt{2}) \over (b_r - b_i\sqrt{2})} = {(a_r br - 2 a_i b_i)  + (a_i b_r - a_r b_i) \sqrt{2} \over b_r^2 - 2 b_i^2}

This arithmetic should work for any base \sqrt{n} where n is an integer. For example, the above addition and multiplication rules are reminiscent of complex arithmetic, as they should be, since i = \sqrt{-1}.

So, what is this all good for? It is hard to see a use for the general case of base \sqrt{n} (or even base n^{1/p}). However, base \sqrt{2} could be useful when dealing with cartesian coordinates and two dimensional maps.

Some games and mapping systems use a movement or planning system where players can move horizontally, vertically, or diagonally. Each move is considered one move, even though a diagonal move is \sqrt{2} than a horizontal or vertical move, in the interest of avoiding square root calculations. Printed circuit boards are often laid out with traces that are either horizontal, vertical, or at 45 degree angles.

In a mapping or planning system, like one of the above that can only make horizontal, vertical, or diagonal moves, distances between any two points can be computed in base \sqrt{2} using the above arithmetic with no need for square roots.

Advertisements