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