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

4 thoughts on “Base sqrt(2)”

  1. Interesting, but…

    “Subtraction can be implemented as the addition of the inverse”

    What is “the inverse”? How do I compute 1 – sqrt(2) ? Or even represent it?

  2. It depends on how you represent signed numbers. For singed magnitude or radix complement you would have two sign bits. The bits with even powers of sqrt(2) would get one sign bit and odd powers of two get another. If there is interest I could write up some examples.

  3. Thanks for good treatment of the subject.
    What happens if we try a number system based on 2^(1/3)? I guess it will be binary system interspersed with 2 additional significant places. Am I correct?

    1. Base sqrt(2) has up to two terms, one is rational and the other is multiplied by sqrt(2). In general, base p^(1/n) will have n terms — one for each of the roots.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s