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←