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