Generalized balanced ternary explained

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.^[1] It has since been used for various applications, including geospatial^[2] and high-performance scientific^[3] 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\; +\; \backslash ldots$$

Generalized balanced ternary uses a transformation matrix as its base

B . Digits are vectors chosen from a finite subset \{D _{0} = 0 , D _{1,} \ldots, 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 x 1 matrix, and the digits D _{i} are length-1 vectors, so they appear here without the extra brackets.

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

- align="right" ! +	0	1	2	-	- ! 0	0	1	2	- ! 1	1	12	0	- ! 2	2	0	21

Two dimensions

In two dimensions, there are seven digits. The digits

D _{1,} \ldots, D _{6} are six points arranged in a regular hexagon centered at D _{0} = 0 .^[4]

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

- align="right" ! +	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

Notes and References

1. Gibson . Laurie . Lucas . Dean . Spatial Data Processing Using Generalized Balanced Ternary . Proceedings of the IEEE Computer Society Conference on Pattern Recognition and Image Processing . 1982 . 566–571.
2. Sahr . Kevin . Hexagonal Discrete Global Grid Systems for Geospatial Computing. Archives of Photogrammetry, Cartography and Remote Sensing . 2011-01-01 . 22 . 363 . 2011ArFKT..22..363S .
3. de Kinder . R. E. Jr. . Barnes . J. R. . The Generalized Balanced Ternary (GBT) Applied to High-Performance Computational Algorithms . APS Meeting Abstracts . August 1997. 1997APS..CPC..C409D .
4. van Roessel . Jan W. . Conversion of Cartesian coordinates from and to Generalized Balanced Ternary addresses . Photogrammetric Engineering and Remote Sensing . 1988 . 54 . 1565–1570 .