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