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 [math]\displaystyle{ p }[/math] as powers of a base [math]\displaystyle{ B }[/math] multiplied by digits [math]\displaystyle{ d_i }[/math].

[math]\displaystyle{ p = d_0 + B d_1 + B^2 d_2 + \ldots }[/math]

Generalized balanced ternary uses a transformation matrix as its base [math]\displaystyle{ B }[/math]. Digits are vectors chosen from a finite subset [math]\displaystyle{ \{D_0 = 0, D_1, \ldots, D_n\} }[/math] 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). [math]\displaystyle{ B }[/math] is a [math]\displaystyle{ 1\times 1 }[/math] matrix, and the digits [math]\displaystyle{ D_i }[/math] are length-1 vectors, so they appear here without the extra brackets.

[math]\displaystyle{ \begin{align}B &= 3 \\ D_0 &= 0 \\ D_1 &= 1 \\ D_2 &= -1\end{align} }[/math]

Addition table

This is the same addition table as standard balanced ternary, but with [math]\displaystyle{ D_2 }[/math] replacing T. To make the table easier to read, the numeral [math]\displaystyle{ i }[/math] is written instead of [math]\displaystyle{ D_i }[/math].

Addition

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

Two dimensions

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 [math]\displaystyle{ D_1, \ldots, D_6 }[/math] are six points arranged in a regular hexagon centered at [math]\displaystyle{ D_0 = 0 }[/math].

[math]\displaystyle{ \begin{align} B &= \frac{1}{2}\begin{bmatrix} 5 & \sqrt{3} \\ -\sqrt{3} & 5 \end{bmatrix} \\ D_0 &= 0 \\ D_1 &= \left( 0, \sqrt{3} \right) \\ D_2 &= \left( \frac{3}{2}, -\frac{\sqrt{3}}{2} \right) \\ D_3 &= \left( \frac{3}{2}, \frac{\sqrt{3}}{2} \right) \\ D_4 &= \left( -\frac{3}{2}, -\frac{\sqrt{3}}{2} \right) \\ D_5 &= \left( -\frac{3}{2}, \frac{\sqrt{3}}{2} \right) \\ D_6 &= \left( 0, -\sqrt{3} \right) \\ \end{align} }[/math]

Addition table

As in the one-dimensional addition table, the numeral [math]\displaystyle{ i }[/math] is written instead of [math]\displaystyle{ D_i }[/math] (despite e.g. [math]\displaystyle{ D_2 }[/math] 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