tvec ← {larg} (fn ##.bt) rarg               ⍝ Balanced Ternary Arithmetic.

    "Perhaps the prettiest number system of all." - Donald Knuth.

Background
----------
Balanced  Ternary (BT) 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 first  of  which,  pro-
nounced "bar-one",  is more properly written with the bar or "vinculum" directly
over the 1. Here are the first few non-negative numbers together with their dec-
imal equivalents:

          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

Operation
---------
Operator  [bt]  applies its operand function to or between balanced ternary (BT)
arguments. Each scalar argument is represented by a vector of the balanced tern-
ary digits ∊ ¯1 0 1. For example:

        1 ¯1 +bt 1 0                ⍝ 2+3 → 5
    1 ¯1 ¯1

Special monadic operands ⊤ and ⊥ encode and decode between regular integer scal-
ars and their BT equivalents.

        ⊤bt 100                     ⍝ BT encoding of 100
    1 1 ¯1 0 1

        ⊥bt 1 0 ¯1 1                ⍝ decoding of BT 1 0 ¯1 1
    25
        ⊥bt (⊤bt 20) +bt ⊤bt 30     ⍝ 20+30 → 50
    50

A monadic operand may be one of:
  ¯¯¯¯¯¯¯
    +       identity
    -       negative
    ×       signum
    |       absolute
    ⊤       encode BT from integer
    ⊥       decode integer from BT

A dyadic operand may be one of:
  ¯¯¯¯¯¯
    +       sum
    -       difference
    ×       product
    ÷       quotient
    |       residue
    *       exponent
    ⌊       min
    ⌈       max
    ∨       greatest common divisor
    ∧       least common multiple
    <≤=≥>≠  relational

Many arithmetic operations on BT numbers are particularly elegant:

Conversion between BT and integers
----------------------------------
BT_vector to integer is just 3∘⊥

        3⊥  1 ¯1 ¯1     ⍝ decode BT
    5
        3⊥ ¯1 ¯1  1     ⍝ decode BT
    ¯11

Integer to BT_vector is also relatively simple:

    encode←{¯1 + norm 1 + 3 enco ⍵}

    where:
        enco, coded {3..3⊤⍵}, encodes with an appropriate number of 3-digits,
        norm, coded {3..3⊤3⊥⍵}, resolves (carries) overflows.

For example:
                      3 enco 50     ⍝ standard 3-encode.
    0 1 2 1 2

                  1 + 3 enco 50     ⍝ + 1 1 ... 1
    1 2 3 2 3

             norm 1 + 3 enco 50     ⍝ normalised (3-overflows carried forward).
    2 0 1 0 0

        ¯1 + norm 1 + 3 enco 50     ⍝ - 1 1 ... 1 → BT.
    1 ¯1 0 ¯1 ¯1

Negation
--------
Balanced ternary numbers are symmetrical with respect to sign; the negative of a
BT  number  is  just  the negative of each of its digits. Here are the first few
negative BT numbers:

          BT     Decimal
           0     0
          ¯1    ¯1
       ¯1  1    ¯2  = ¯3+1
       ¯1  0    ¯3
       ¯1 ¯1    ¯4
    ¯1  1  1    ¯5  = ¯9+3+1

        ⊤bt  100            ⍝ BT representation of +100 (+/ 81 27 ¯9 0 1)
    1 1 ¯1 0 1

        ⊤bt ¯100            ⍝ BT representation of ¯100 (+/ ¯81 ¯27 9 0 ¯1)
    ¯1 ¯1 1 0 ¯1

        ⊥bt - ⊤bt 100       ⍝ (negating its digits negates the number)
    ¯100

Notice  that, unlike two's complement binary numbers, both positive and negative
numbers  have  notional leading zeros to the left of the most significant digit.
A normal BT form would remove these leading zeros  except for the anomalous case
(shared with standard decimal notation) of the number zero itself.

    ... 0  0  1  1 ¯1  0  1  →   1  1 ¯1  0  1     ⍝  100

    ... 0  0 ¯1 ¯1  1  0 ¯1  →  ¯1 ¯1  1  0 ¯1     ⍝ ¯100

    ... 0  0  0  0  0  0  0  →               0     ⍝    0

Signum
------
The signum (sign) of a BT number is just its most significant digit.

        ×bt ¯1 1 1 0        ⍝ ׯ15 → ¯1
    ¯1
        ×bt 1 ¯1 ¯1 0       ⍝ ×15 → 1
    1
        ×bt 0               ⍝ ×0 → 0
    0

Addition
--------
The addition table for BT digits is:

     +  ¯1   0   1
       ┌───┬───┬───┐
    ¯1 │ 1-│¯1 │ 0 │   where:
       ├───┼───┼───┤
     0 │¯1 │ 0 │ 1 │       1- means 1 with a carry of ¯1 to the next column.
       ├───┼───┼───┤
     1 │ 0 │ 1 │¯1+│      ¯1+ means ¯1 with a carry of 1 to the next column.
       └───┴───┴───┘

For example:

     1  0 ¯1  0  1            73 +
       ¯1 ¯1 ¯1  1           ¯38
    --------------           ---
     0  1  1  0 ¯1            35
    --------------           ---
    ¯1 ¯1     1    ← carry

(subtraction is just addition of the negative of the subtrahend).

Multiplication
--------------
We use high-school long-multiplication with the following table:

     ×  ¯1   0   1
       ┌───┬───┬───┐
    ¯1 │ 1 │ 0 │¯1 │
       ├───┼───┼───┤
     0 │ 0 │ 0 │ 0 │
       ├───┼───┼───┤
     1 │¯1 │ 0 │ 1 │
       └───┴───┴───┘

For example:

           1  0 ¯1  1           25 ×
             ¯1  1  1           ¯5
          -----------         ----
    ¯1  0  1 ¯1       +       ¯225 +
        1  0 ¯1  1              75
           1  0 ¯1  1           25
    -----------------         ----
    ¯1  1  1  1  0  1         ¯125
    -----------------         ----
          ¯1

Division
--------
[bt] uses standard high-school long division. See: eval.dws/notes.Long_division.

First  the dividend is partitioned into two vectors p and s, where p has at most
the  same number of digits as the divisor (q) and s is a vector of the remaining
digits.  For  example,  if divisor q is 1 ¯1 ¯1 and the dividend is 1 ¯1 1 1 ¯1,
then p is 1 ¯1 1 and s is 1 ¯1.                                     └──p─┘ └s─┘

Multiples (1 or ¯1) of q are repeatedly (actually, only once or twice) subtract-
ed  from  p  until  p lies in the half-closed interval from (and including) 0 to
(but excluding) q. Note that q might be negative, so this means:

    q>0: (0≤p)∧(p<q)    ⍝ q positive: 0≤p<q
    q<0: (q<p)∧(p≤0)    ⍝ q negative: q<p≤0

At each step, the multiple (1 or ¯1) is added to the result r. When p is reduced
to  lie  within the interval bounded by q, the result is multiplied by 3 (by ap-
pending a 0) and the next digit from s is transferred to p. When s is exhausted,
result r and dividend p constitute the final quotient and remainder.

(muse:

    We can restate this procedure in →declarative← terms.

    Here is a definition of BT-division in a pattern-matching notation.  Defined
    infix  function  names are underlined and an indented definition is local to
    its exdented predecessor. Lexical name-scope rules apply.  Functions bind to
    the right as in APL.  The name alphabet is extended with additional charact-
    ers  prime (') and double-prime (").  White dots "·" are cosmetic and may be
    ignored.

    Notice that there are no guards!  In this notation, pattern-matching is used
    as an _alternative_ to the guard mechanism. See min.dws for more on pattern-
    matching.

    p div q = 0 div' q part p                       ⍝ result 0, q-partitioned p
      ¯¯¯       ¯¯¯    ¯¯¯¯
    ·   r div' p s = r div" p s, p in q             ⍝ p in interval [0..q)
    ·   · ¯¯¯          ¯¯¯         ¯¯
    ·   ·   r div" p ⍬ 1 = r p                      ⍝ null s: quotient remainder
    ·   ·     ¯¯¯
    ·   ·   r div" p s 1 = (r,0) div' p xfer s      ⍝ shift of dividend and rslt
    ·   ·   · ¯¯¯                ¯¯¯    ¯¯¯¯
    ·   ·   ·   p xfer s = (p,1↑s) (1↓s)            ⍝ transfer of next digit.
    ·   ·   ·     ¯¯¯¯
    ·   ·   r div" p s 0 = (r + m) div' (p-m×q) s   ⍝ rslt +← m, dividend -← m×q
    ·   ·   · ¯¯¯             ¯    ¯¯¯    ¯ ¯
    ·   ·   ·   m = ×/×p q                          ⍝ multiple: ¯1 or 1.
    ·   ·   ·         ¯
    ·   ·   p in q = p in' q (q>0)                  ⍝ p in half-interval [0..q)
    ·   ·   · ¯¯       ¯¯      ¯
    ·   ·   ·   p in' q 1 = (0≤p)∧(p<q)             ⍝ q positive: 0≤p<q
    ·   ·   ·     ¯¯          ¯     ¯
    ·   ·   ·   p in' q 0 = (-p) in (-q)            ⍝ q negative: q<p≤0
    ·   ·   ·     ¯¯         ¯   ¯¯  ¯
    ·   q part p = (min↑p)(min↓p)                   ⍝ q-partition of p.
    ·   · ¯¯¯¯
    ·   ·   min = (⍴p) ⌊ ⍴q                         ⍝ minimum number of digits.

    where:
        p q r s         are BT numbers.
        ↑ ↓ ∧ ⌊ ⍴ ,     are regular APL functions on numeric vectors.
        + - × > ≤ <     are BT functions on BT numbers.
)       ¯ ¯ ¯ ¯ ¯ ¯

As  a  worked  example, let's divide 1 ¯1 1 1 by ¯1 1 1, giving quotient ¯1 1 1,
remainder  ¯1 0.  In the commentary, q refers to the divisor ¯1 1 1, p refers to
the current residue, and r to the result:

                     ¯1  1  1       ⍝ quotient: ¯5
                        ¯1          ⍝ (¯1 → ¯1 1 in second step below)
                 ┌────────┬──
        ¯1  1  1 │ 1 ¯1  1  1       ⍝ ~ q < p ≤ 0:
                   1 ¯1 ¯1          ⍝   p -← ¯1 × q  ⋄  r +← ¯1  ⍝ r: 0 → ¯1
                  --------          ⍝
                      1 ¯1          ⍝ ~ q < p ≤ 0:
                   1 ¯1 ¯1          ⍝   p -← ¯1 × q  ⋄  r +← ¯1  ⍝ r: ¯1 → ¯1 1
                  --------          ⍝
                     ¯1  0          ⍝   q < p ≤ 0: append next digit.
                     ¯1  0  1       ⍝ ~ q < p ≤ 0:
                     ¯1  1  1       ⍝   p -← 1 × q  ⋄  r +← 1  ⍝ r:¯1 1 → ¯1 1 1
                     --------       ⍝   q < p ≤ 0: no more digits.
                        ¯1  0       ⍝ remainder: ¯3

(NB: if you try this method using pencil and paper, you might find it convenient
 to  negate  the  multiple  of the divisor as you write it under the dividend at
 each stage, and then use addition rather than subtraction:

                  ¯1
                 ┌───────────
        ¯1  1  1 │ 1 ¯1  1  1
                  ¯1  1  1  ← add negative of multiple
                  --------
                      1 ¯1
                  ...
)

Division by (powers of) 3
-------------------------
To divide a BT number by 3 (rounding down the result) we add ¯1; then all digits
but  the last constitute the integer quotient and the last digit + 1 is the rem-
ainder. Using the example 86÷3 → 28r2:

    1  0  1 ¯1 ¯1 +      86 +
               ¯1        ¯1
    -------------
    1  0  0  1  1 +      85
    └────┬───┘  1
         │   ----
         │   1 ¯1
         │   └─┬┘
         │     └────── remainder  2
         └──────────── quotient  28

More  generally, to divide a BT number by 3*⍵, we add ⍵⍴¯1 digits, then the int-
eger quotient is all but the rightmost ⍵ digits, and rightmost ⍵ digits + ⍵⍴1 is
the remainder. For example, to divide 54321 by 81 (81=3*4):

    54321÷81 → 670r51:

      1  0 ¯1  1  0 ¯1 ¯1 ¯1  0 ¯1  0 +     ⍝ 54321
                          ¯1 ¯1 ¯1 ¯1       ⍝ (3⍟81)⍴¯1
     --------------------------------
      1  0 ¯1  1 ¯1  1  1  0  1  1 ¯1 +
      └────────┬────────┘  1  1  1  1       ⍝ (3⍟81)⍴1
               │           ----------
               │        1 ¯1  0 ¯1  0
               │        └─────┬─────┘
               │              └─────── remainder 51
               └────────────────────── quotient 670

[bt] uses fast division by 3 to implement power (⍺ *bt ⍵).

Other fast divisors
-------------------
LeRoy Eide has an algorithm for fast division-by-2 of BT numbers. The method may
be  generalised  to division by numbers of the form ¯1 1+3*⍵, which include such
useful divisors as 2 4 8 and 10. See →JitSub←

Note  that  the  parity  (2|) of a BT number is just the parity of the (absolute
value of the) sum of its digits. For a proof, see: eval.dws/notes.proof.

        ↑+bt/ 1 ¯1 ¯1 ¯1 0              ⍝ bt-sum of digits → ¯2 (even)
    ¯1 1
        ↑+bt/ ↑+bt/ 1 ¯1 ¯1 ¯1 0        ⍝ bt-sum bt-sum of digits → 0 (even)
    0
        ↑∘(+bt/)⍣≡ 1 ¯1 ¯1 ¯1 0         ⍝ bt-sum →limit← of digits → 0 (even)
    0
        ↑∘(+bt/)⍣≡ 99⍴¯1                ⍝ bt-sum limit of ¯1 ¯1 .. ¯1 → ¯1 (odd)
    ¯1
        |↑∘(+bt/)⍣≡¨ ⊤bt¨ ¯10 to 10
    0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0

Power ⍺*⍵ (⍵≥0)
---------------
For  ⍺*⍵, we avoid calculating ⍵ products  ⍺ × ⍺ × ···,  by using the recurrence
relation:                                  └─── ⍵ ───┘

    ⍺*0 = 1
    ⍺*1 = ⍺
    ⍺*2 = ⍺×⍺
    ⍺*⍵ = (⍺*3|⍵) × {⍵×⍵×⍵} ⍺*⌊⍵÷3

which  needs  only  O(3×3⍟⍵)  products. 3|⍵ and ⍵÷3 use the fast division method
outlined above.

Extension to fractional numbers
-------------------------------
Operator [bt] deals only in integers.  Balanced ternary numbers extend nicely to
fractional values using a "ternary point", as the following sequence shows:

    decimal         balanced ternary
    -------         ----------------
    120             1 1 1 1 0
    120÷3             1 1 1 1
    120÷9               1 1 1 . 1
    120÷27                1 1 . 1 1
    120÷81                  1 . 1 1 1
    120÷243                 0 . 1 1 1 1

... and so on.

Fractional  BT  numbers  have  the pleasant property that truncating them on the
right  rounds  to  the  nearest number; in other words truncation is the same as
rounding.

Notice that, in common with all number bases, a rational number, whose denomina-
tor contains prime factors other than those of the base, gives rise to an infin-
itely  repeated  fractional sequence. Specifically, with BT numbers, this occurs
if  the  divisor  has prime factors other than 3. Here are some decimal rational
numbers together with their BT equivalents:

    1÷3     0  .  1
    2÷3     1  . ¯1
    1÷9     0  .  0  1
    2÷9     0  .  1 ¯1
    1÷2     0  .  1  1  1  1 ...
    1÷4     0  .  1 ¯1  1 ¯1 ...
    1÷8     0  .  0  1  0  1 ...
    1÷10    0  .  0  1  0 ¯1 0 1 0 ¯1 ...

Notice  also that, in common with decimal notation, some BT numbers have altern-
ative representations. For example, in decimal, one half may be expressed either
as 0.5 or as 0.4999... Similarly, in BT notation, one half may be written either
as 0 . 1 1 1 ... or as 1 .¯1 ¯1 ¯1 ...

For more on fractional BT numbers, see →ratsum← and →ratrep←.

Historical notes
----------------
In  1840, Thomas Fowler, a contemporary of Charles Babbage, designed and built a
balanced ternary calculating machine. See:

    http://www.mortati.com/glusker/fowler/index.htm
    http://www.ThomasFowler.org.uk

In  the early days of electronic computing, several attempts were made to employ
3-state  logic, in which case balanced ternary was a natural coding for numbers.
Notable among  these were the Russian Setun (1958) and Setun-70 (1970) machines.
See:

    http://www.computer-museum.ru/english/setun.htm

TERNAC: In 1973, Frieder, Fong and Chao produced an emulation of a ternary mach-
ine, written in FORTRAN on a (binary) Burroughs B1700.  A notable feature of the
implementation is that it represents a ternary word as a _pair_ of binary words,
separating the positive and negative ternary digits. For example:
      _ _
    10111  →  10010 00101

The following functions convert between  shape-S BT arrays and shape-(2,S) Tern-
ac style boolean (binary) arrays. This reduces the per-digit storage requirement
from 8 bits to 2 bits.

    ternac ← 1 ¯1 ∘.= ⊢     ⍝ BT to binary

    ternac 1 0 ¯1 1 ¯1
1 0 0 1 0
0 0 1 0 1

    canret ← 1 ¯1 +.× ⊢     ⍝ binary to BT

    canret ↑(1 0 0 1 0)(0 0 1 0 1)
1 0 ¯1 1 ¯1

Ref: G.Frieder, A.Fong, and C.Y.Chao. A Balanced Ternary Computer. Department of
     Computer Science, State University of New York at Buffalo, pp 68–88, 1972

Ref: https://en.wikipedia.org/wiki/Ternac

Examples:

    1 0 1 +bt 1 0 1             ⍝ 10+10 → 20
1 ¯1 1 ¯1

    1 0 1 -bt 1 ¯1 1 ¯1         ⍝ 10-20 → ¯10
¯1 0 ¯1

    1 0 1 ×bt 1 0 1             ⍝ 10×10 → 100
1 1 ¯1 0 1

    1 0 1 *bt 1 0 1             ⍝ 10*10 → 10,000,000,000
1 0 0 ¯1 ¯1 1 1 0 ¯1 1 ¯1 1 0 ¯1 0 ¯1 0 1 0 1 0 1

    ⊤bt 100                     ⍝ integer to BT
1 1 ¯1 0 1

    ⊥bt 1 1 ¯1 0 1              ⍝ BT to integer
100

See also: abc nats rats ratsum to limit stamps
See also: eval.dws/notes.bta
See also: JitSub ratrep
See also: ary ratsum phinary

Back to: contents

Back to: Workspaces