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

QuickSynergy Server Troubles

Synergy allows one computer to control the keyboard and mouse of one or more other computers seamlessly, even if the computers are all running different operating systems. I am using my Mac laptop to drive my Mac and a Windows 7 laptop. When it is working it is a pretty sweet setup, but the configuration can be a little touchy.

Sometimes the Mac OS X server refuses to start. When it fails I see this message in /var/log/system.log on my Mac:

Oct  6 13:37:06 eagle [0x0-0xe4be4b].com.cordeiro.QuickSynergy[36223]: INFO: Synergy server 1.3.1 on Darwin 11.1.0 Darwin Kernel Version 11.1.0: Tue Jul 26 16:09:02 PDT 2011; root:xnu-1699.22.81~1/RELEASE_I386 i386
Oct  6 13:37:06 eagle [0x0-0xe4be4b].com.cordeiro.QuickSynergy[36223]: FATAL: unknown screen name `eagle.local'

It appears that QuickSynergy cannot resolve the name of my Mac for some reason, though I can ping it both locally and from another computer on the same subnet.

My Mac has both a wireless and a wired 1 Gbps link, by default, routes over the wired network.  When I disconnect and reconnect the wired network, the error from QuickSynergy goes away and netstat shows that Synergy is listening on the wireless network.  Since the client that connects does so through an ssh tunnel to localhost, it does not really matter.  It just seems strange that Synergy would be able to listen on the wireless network and not the wired network.

This problem requires more debugging, but for now I can make it work, so I’ll get back to what I wanted to do and figure it out later.