Balanced Ternary Numbers
------------------------
Balanced Ternary is a number system in which each place represents a power of 3:
1 9 27 81 243 ···. It differs from "standard" ternary in that instead of using
non-negative digits (0 1 2), BT uses (1 0 ¯1), the third of which, pronounced
"bar-one", is usually written with the bar or "vinculum" directly over the 1.
Here are the first few non-negative numbers together with their decimal equival-
ents:
BT Decimal
0 0
1 1
1 ¯1 2 = 3-1 "one, bar-one"
1 0 3
1 1 4
1 ¯1 ¯1 5 = 9-3-1 "one, bar-one, bar-one"
1 ¯1 0 6
1 ¯1 1 7 = 9-3+1
1 0 ¯1 8
1 0 0 9
1 0 1 10
1 1 ¯1 11
1 1 0 12
1 1 1 13
1 ¯1 ¯1 ¯1 14 = 27-9-3-1
To negate a BT number, we just flip the sign of each digit.
BT Decimal
0 0
¯1 ¯1
¯1 1 ¯2 = ¯3+1
¯1 0 ¯3
¯1 ¯1 ¯4
¯1 1 1 ¯5 = ¯9+3+1
To turn the APL vector representation of a BT number into decimal, we use base
(decode) ⊥:
dec←3∘⊥
dec 1 ¯1 0 ¯1
17
dec ¯1 ¯1 0 ¯1
¯37
Conversely, the following function converts a single decimal number to BT (there
may be a simpler way):
bt←{ ⍝ Balanced ternary from decimal.
width←1+⌈3⍟1⌈|⍵ ⍝ number (+1) of ternary digits.
tdigs←{ ⍝ bt digits with possible leading 0.
~2∊⍵:⍵ ⍝ no 2s: finished.
p2s←2=⍵ ⍝ positions of 2s.
∇ ⍵+(1⌽p2s)-p2s×3 ⍝ bt (1 0 ¯1) digits.
}(width⍴3)⊤|⍵ ⍝ standard (0 1 2) ternary digits.
(0=⍬⍴tdigs)↓tdigs××⍵ ⍝ leading 0 removed, sign adjusted.
}
bt 37
1 1 0 1
bt ¯17
¯1 1 0 1
Part of the appeal of balanced ternary numbers is that their arithmetic is rel-
atively simple. Like APL, negativity is represented within the number itself; we
don't need to attach a separate unary negate function.
This leads to very simple reduction sequences for arithmetic operations:
⍝ negate
- ¯1 = 1
- 0 = 0
- 1 = ¯1
- p.i = (-p).(-i) ⍝ negate each digit.
The sign of a number is just the sign of its leftmost digit:
⍝ signum
× i = i
× p.i = × p
... and we can use conventional "high school long multiplication" for product:
p * ¯1 = -p
p * 0 = 0
p * 1 = p
p * q.j = (p*q).0 + p*j
Parity: A BT number is odd (resp. even) if the sum of its digits is odd (resp.
even) (see →proof←). The following reduction sequence (not presently included in
→#.bta←) defines a function that returns 1 for an odd argument and 0 for an even
one; it is equivalent to the APL function: 2∘|.
odd() ⍝ parity
odd ¯1 = 1 ⍝ base cases
odd 0 = 0
odd 1 = 1
odd p.i = odd (odd p)+i ⍝ general case.
To experiment with this function, just copy the above lines into script →#.bta←,
noting that the position of the first line relative to other declarations in the
script determines the function's binding precedence.
Examples:
load bta ⍝ Install rules for Balanced Ternary arithmetic.
until'→'
0
0
0+1
1
0+1+1
1.¯1
0+1+1+1
1.0
0+1+1+1+1
1.1
0+1+1+1+1+1
1.¯1.¯1
ten=1.¯1.¯1 * 1.¯1
ten
1.0.1
ten*ten
1.1.¯1.0.1
1.0∧1.0∧1.0 ⍝ 3∧3∧3 => 7625597484987
1.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0
⍝ We can do "infinite precision integer arithmetic". The next example shows
⍝ the BT representation of increasingly greater powers of 2, up to 2∧64: a
⍝ number which is not representable with perfect accuracy in IEEE 64-bit
⍝ floating point format.
two=1+1 ⍝ 2
two∧two∧0 ⍝ 2∧2∧0 → 2∧1
1.¯1
two∧two∧1 ⍝ 2∧2∧1 → 2∧2
1.1
two∧two∧(1+1) ⍝ 2∧2∧2 → 2∧4
1.¯1.¯1.1
two∧two∧(1+1+1) ⍝ 2∧2∧3 → 2∧8
1.0.0.1.1.1
two∧two∧(1+1+1+1) ⍝ 2∧2∧4 → 2∧16
1.0.1.0.0.0.¯1.0.1.¯1.1
two∧two∧(1+1+1+1+1) ⍝ 2∧2∧5 → 2∧32
1.1.¯1.0.1.¯1.1.0.0.¯1.1.¯1.0.0.¯1.¯1.¯1.¯1.¯1.1.1
two∧two∧(1+1+1+1+1+1) ⍝ 2∧2∧6 → 2∧64
1.¯1.¯1.¯1.¯1.0.0.¯1.0.1.0.0.¯1.0.0.¯1.¯1.0.1.1.¯1.¯1.1.1.1.¯1.1.¯1.¯1.1.¯1.1.1.¯1.1.1.0.¯1.¯1.0.¯1.1
→
load std ⍝ restore standard (Excel) rules.
See also: →#.bta←
http://www.americanscientist.org/Issues/Comsci01/Compsci2001-11.html
Back to: →Overview←