Generalized balanced ternary

Generalized balanced ternary is a generalization of the balanced ternary numeral system to represent points in a higher-dimensional space. It was first described in 1982 by Laurie Gibson and Dean Lucas. It has since been used for various applications, including geospatial and high-performance scientific computing.

General form

Like standard positional numeral systems, generalized balanced ternary represents a point $p$ as powers of a base $B$ multiplied by digits $d_i$.

$$p=d_0+B{d}_1+B^2{d}_2+\dots$$

Generalized balanced ternary uses a transformation matrix as its base $B$. Digits are vectors chosen from a finite subset $\{D_0=0,D_1,\dots ,D_n\}$ of the underlying space.

One dimension

In one dimension, generalized balanced ternary is equivalent to standard balanced ternary, with three digits (0, 1, and −1). $B$ is a $1\times 1$ matrix, and the digits $D_i$ are length-1 vectors, so they appear here without the extra brackets.

$$\begin{array}{cc}B& =3\\ D_0& =0\\ D_1& =1\\ D_2& =-1\end{array}$$

Addition table

This is the same addition table as standard balanced ternary, but with $D_2$ replacing T. To make the table easier to read, the numeral $i$ is written instead of $D_i$.

Addition

+	0	1	2
0	0	1	2
1	1	12	0
2	2	0	21

Two dimensions

File:Visualization of three-digit 2D generalized balanced ternary numbers.png

The 2D points addressable by three generalized balanced ternary digits. Each point is addressed by its path from the origin; the six colors correspond to the six non-zero digits.

In two dimensions, there are seven digits. The digits $D_1,\dots ,D_6$ are six points arranged in a regular hexagon centered at $D_0=0$.

$$\begin{array}{cc}B& =\frac{1}{2}\left[\begin{array}{cc}5& \sqrt{3}\\ -\sqrt{3}& 5\end{array}\right]\\ D_0& =0\\ D_1& =(0,\sqrt{3})\\ D_2& =(\frac{3}{2},-\frac{\sqrt{3}}{2})\\ D_3& =(\frac{3}{2},\frac{\sqrt{3}}{2})\\ D_4& =(-\frac{3}{2},-\frac{\sqrt{3}}{2})\\ D_5& =(-\frac{3}{2},\frac{\sqrt{3}}{2})\\ D_6& =(0,-\sqrt{3})\\ \end{array}$$

Addition table

As in the one-dimensional addition table, the numeral $i$ is written instead of $D_i$ (despite e.g. $D_2$ having no particular relationship to the number 2).

Addition

+	0	1	2	3	4	5	6
0	0	1	2	3	4	5	6
1	1	12	3	34	5	16	0
2	2	3	24	25	6	0	61
3	3	34	25	36	0	1	2
4	4	5	6	0	41	52	43
5	5	16	0	1	52	53	4
6	6	0	61	2	43	4	65

If there are two numerals in a cell, the left one is carried over to the next digit. Unlike standard addition, addition of two-dimensional generalized balanced ternary numbers may require multiple carries to be performed while computing a single digit.

See also

• Gosper curve

External links

• Spiral Honeycomb Mosaic, another name for the two-dimensional form of this numbering system
• "Clever Hex Grid Method" discussion on rec.games.roguelike.development