Compare at the top
You will learn
Why balanced-ternary numbers compare at their first differing trit.
In balanced ternary the trits below place i add up to less than half of 3^i, so the highest differing trit decides any comparison. 41 is +---- and 39 is 0+++0: they differ in the top trit, so 41 is greater although its tiles show four minus signs. The spec's compare() reads that trit and is checked against plain less and greater on 714 pairs.
Try it
Find two numbers that first differ in their lowest trit, and two that differ in every trit.
Two numbers line up trit by trit; the first place from the top where they differ decides. The answer is itself a trit.
specs/ternary/trits.t27
// SPDX-License-Identifier: Apache-2.0
// specs/ternary/trits.t27 -- balanced ternary, worked by hand: digits, logic, adders, products,
// storage in bits, comparison and a ternary neuron
// Host: gHashTag/trinity apps/website, the course "The ternary machine" (specs/course/
// ternary-computing.t27): every interactive widget of that course draws numbers that these fn
// bodies compute, compiled to wasm (scripts/t27-logic.mjs in gHashTag/999-multibots-telegraf,
// types stripped, beside a byte-for-byte copy of this file). The pages write no rule of their own.
//
// THE NUMBER SYSTEM: balanced ternary writes an integer with the digits -1, 0 and +1 (a "trit"),
// weights 1, 3, 9, 27 ... Every integer, negative ones included, has exactly one such form with no
// sign symbol: k trits cover -(3^k - 1)/2 .. +(3^k - 1)/2. Negating a number flips every trit, and
// cutting the lowest trits rounds to the nearest multiple of 3^k (D. Knuth, The Art of Computer
// Programming vol. 2, section 4.1; the Setun computer, Moscow State University, 1958, used it).
//
// LOGIC: the Kleene three-valued logic on -1 (false), 0 (unknown), +1 (true): NOT is negation, AND
// is the minimum, OR is the maximum; on -1 and +1 alone they are Boolean NOT, AND and OR.
// CONSENSUS keeps a value both inputs agree on, ANY keeps the decided one; SUM is addition mod 3.
//
// ARITHMETIC: two trits add to a sum trit and a carry trit (a + b = sum + 3 * carry); a full adder
// takes a carry in. A product by one trit needs no multiplier: the multiplicand is copied, dropped
// or negated. Long multiplication adds shifted copies.
//
// STORAGE: a trit in two bits (00, 01, 10 as the hardware specs pack it) wastes one of four codes; five trits fit one byte (3^5 = 243 <= 256),
// using 99.06 percent of the byte's information. A trit carries log2(3) = 1.585 bits.
//
// COMPARISON: two balanced-ternary numbers compare at their most significant differing trit.
//
// WHAT IT DOES NOT CLAIM: i32 limits the numbers to 19 trits (3^19 < 2^31); the widgets stay inside.
// Claim status: checked by the tests below, each against an independent sum over the digits.
// phi^2 + 1/phi^2 = 3 | TRINITY
module ternary::trits {
pub const KIND : str = "widget-logic";
pub const ID : str = "trits";
pub const VERSION : u8 = 1;
pub const MAX_TRITS : u32 = 19;
pub const LOG2_3 : f64 = 1.584962500721156;
pub const PACK5_CODES : u32 = 243;
// Gate numbers for gate(): the order the logic widget lists them in.
pub const GATE_NOT : u32 = 0;
pub const GATE_MIN : u32 = 1;
pub const GATE_MAX : u32 = 2;
pub const GATE_CONSENSUS : u32 = 3;
pub const GATE_ANY : u32 = 4;
pub const GATE_SUM : u32 = 5;
pub const GATE_CARRY : u32 = 6;
pub const GATE_COUNT : u32 = 7;
// --- Digits -------------------------------------------------------------------------------
// 3 to the power k, for k <= 19.
fn pow3(k: u32) -> i32 {
var p : i32 = 1;
var i : u32 = 0;
while (i < k) {
p = p * 3;
i = i + 1;
}
return p;
}
// The offset 111...1 in base 3 over all MAX_TRITS places: (3^19 - 1) / 2.
pub const OFFSET : u32 = 581130733;
// Trit i of n (i = 0 is the ones place): -1, 0 or +1. Adding 111...1 (base 3) turns every
// balanced trit t into an ordinary digit t + 1, so the digits of n + OFFSET, read in plain
// base 3 with unsigned arithmetic, are the trits of n plus one.
fn trit_at(n: i32, i: u32) -> i32 {
var u : u32 = ((n + (OFFSET as i32)) as u32);
var j : u32 = 0;
while (j < i) {
u = u / 3;
j = j + 1;
}
return ((u % 3) as i32) - 1;
}
// The largest number k trits can write: 1 + 3 + ... + 3^(k-1) = (3^k - 1) / 2.
fn max_of(k: u32) -> i32 {
var sum : i32 = 0;
var i : u32 = 0;
while (i < k) {
sum = sum + pow3(i);
i = i + 1;
}
return sum;
}
// How many trits n needs (at least one).
fn trits_needed(n: i32) -> u32 {
var a : i32 = n;
if (a < 0) {
a = 0 - a;
}
var k : u32 = 1;
while (max_of(k) < a && k < MAX_TRITS) {
k = k + 1;
}
return k;
}
// How many bits n needs in two's complement (at least one).
fn bits_needed(n: i32) -> u32 {
var k : u32 = 1;
var hi : i32 = 0;
var lo : i32 = 0 - 1;
while ((n > hi || n < lo) && k < 32) {
hi = hi * 2 + 1;
lo = lo * 2;
k = k + 1;
}
return k;
}
// The number written by the trits of n with every trit flipped: -n, digit by digit.
fn negate(n: i32) -> i32 {
var sum : i32 = 0;
var i : u32 = 0;
while (i < MAX_TRITS) {
sum = sum + (0 - trit_at(n, i)) * pow3(i);
i = i + 1;
}
return sum;
}
// n with its lowest k trits cut off: the nearest multiple of 3^k (no ties are possible).
fn cut_round(n: i32, k: u32) -> i32 {
var sum : i32 = 0;
var i : u32 = k;
while (i < MAX_TRITS) {
sum = sum + trit_at(n, i) * pow3(i);
i = i + 1;
}
return sum;
}
// --- Logic --------------------------------------------------------------------------------
fn t_not(a: i32) -> i32 {
return 0 - a;
}
fn t_min(a: i32, b: i32) -> i32 {
if (a < b) {
return a;
}
return b;
}
fn t_max(a: i32, b: i32) -> i32 {
if (a > b) {
return a;
}
return b;
}
// The value both inputs agree on, else unknown.
fn t_consensus(a: i32, b: i32) -> i32 {
if (a == b) {
return a;
}
return 0;
}
// The decided input when the other is unknown; unknown when they contradict.
fn t_any(a: i32, b: i32) -> i32 {
if (a == 0) {
return b;
}
if (b == 0 || a == b) {
return a;
}
return 0;
}
// Half adder: the sum trit of a + b.
fn half_sum(a: i32, b: i32) -> i32 {
return trit_at(a + b, 0);
}
// Half adder: the carry trit of a + b.
fn half_carry(a: i32, b: i32) -> i32 {
return trit_at(a + b, 1);
}
// One gate by number (GATE_*); NOT reads a only.
fn gate(id: u32, a: i32, b: i32) -> i32 {
if (id == GATE_NOT) {
return t_not(a);
}
if (id == GATE_MIN) {
return t_min(a, b);
}
if (id == GATE_MAX) {
return t_max(a, b);
}
if (id == GATE_CONSENSUS) {
return t_consensus(a, b);
}
if (id == GATE_ANY) {
return t_any(a, b);
}
if (id == GATE_SUM) {
return half_sum(a, b);
}
return half_carry(a, b);
}
// How many different gates of n inputs exist in base 3 (3^(3^n)), n <= 2.
fn ternary_functions(n: u32) -> u32 {
var rows : u32 = 1;
var i : u32 = 0;
while (i < n) {
rows = rows * 3;
i = i + 1;
}
var count : u32 = 1;
var j : u32 = 0;
while (j < rows) {
count = count * 3;
j = j + 1;
}
return count;
}
// The same count in base 2 (2^(2^n)), n <= 4.
fn binary_functions(n: u32) -> u32 {
var rows : u32 = 1;
var i : u32 = 0;
while (i < n) {
rows = rows * 2;
i = i + 1;
}
var count : u32 = 1;
var j : u32 = 0;
while (j < rows) {
count = count * 2;
j = j + 1;
}
return count;
}
// --- Adding -------------------------------------------------------------------------------
// Full adder: the sum trit of a + b + carry_in.
fn full_sum(a: i32, b: i32, c: i32) -> i32 {
return trit_at(a + b + c, 0);
}
// Full adder: the carry trit of a + b + carry_in.
fn full_carry(a: i32, b: i32, c: i32) -> i32 {
return trit_at(a + b + c, 1);
}
// The carry that enters column i when x and y are added trit by trit from column 0.
fn carry_into(x: i32, y: i32, i: u32) -> i32 {
var c : i32 = 0;
var j : u32 = 0;
while (j < i) {
c = full_carry(trit_at(x, j), trit_at(y, j), c);
j = j + 1;
}
return c;
}
// x + y, built column by column with full adders only.
fn ripple_add(x: i32, y: i32) -> i32 {
var sum : i32 = 0;
var c : i32 = 0;
var i : u32 = 0;
while (i < MAX_TRITS) {
const a = trit_at(x, i);
const b = trit_at(y, i);
sum = sum + full_sum(a, b, c) * pow3(i);
c = full_carry(a, b, c);
i = i + 1;
}
return sum;
}
// --- Multiplying --------------------------------------------------------------------------
// n times one trit, without a multiplier: copy, drop or negate.
fn trit_times(n: i32, t: i32) -> i32 {
if (t > 0) {
return n;
}
if (t < 0) {
return negate(n);
}
return 0;
}
// The partial product of row i of n * m: n times trit i of m, shifted up i places.
fn partial(n: i32, m: i32, i: u32) -> i32 {
return trit_times(n, trit_at(m, i)) * pow3(i);
}
// n * m as the sum of its partial products.
fn long_mul(n: i32, m: i32) -> i32 {
var sum : i32 = 0;
var i : u32 = 0;
while (i < MAX_TRITS) {
sum = sum + partial(n, m, i);
i = i + 1;
}
return sum;
}
// One step of a ternary multiply-accumulate: acc plus x times weight trit w.
fn mac_step(acc: i32, w: i32, x: i32) -> i32 {
return acc + trit_times(x, w);
}
// What the MAC hardware does for weight trit w: 1 add, -1 subtract, 0 nothing.
fn mac_op(w: i32) -> i32 {
return trit_at(w, 0);
}
// --- Storing trits in bits ----------------------------------------------------------------
// A trit in two bits, packed the way this repository's hardware specs pack it (specs/ternary/
// ternary_mac.t27, ternary_ripple_adder.t27): -1 -> 00, 0 -> 01, +1 -> 10; 11 is unused.
fn code2(t: i32) -> u32 {
if (t > 0) {
return 2;
}
if (t < 0) {
return 0;
}
return 1;
}
// The trit a two-bit code holds; the unused code 11 reads as 0.
fn decode2(c: u32) -> i32 {
if (c == 2) {
return 1;
}
if (c == 0) {
return 0 - 1;
}
return 0;
}
fn code2_valid(c: u32) -> bool {
return c < 3;
}
// Five trits in one byte: (t0 + 1) + 3 (t1 + 1) + 9 (t2 + 1) + 27 (t3 + 1) + 81 (t4 + 1).
fn pack5(t0: i32, t1: i32, t2: i32, t3: i32, t4: i32) -> u32 {
const v = (t0 + 1) + 3 * (t1 + 1) + 9 * (t2 + 1) + 27 * (t3 + 1) + 81 * (t4 + 1);
return v as u32;
}
// Trit i (0..4) of a packed byte.
fn unpack5(byte: u32, i: u32) -> i32 {
var v : u32 = byte;
var j : u32 = 0;
while (j < i) {
v = v / 3;
j = j + 1;
}
return ((v % 3) as i32) - 1;
}
// A byte is a valid five-trit code below 243.
fn pack5_valid(byte: u32) -> bool {
return byte < PACK5_CODES;
}
// The share of the stored bits that carries information: trits * log2(3) / bits.
fn bit_use(trits: u32, bits: u32) -> f64 {
return (trits as f64) * LOG2_3 / (bits as f64);
}
// The fewest bits that can hold every value of k trits: the smallest b with 2^b >= 3^k.
fn bits_for_trits(k: u32) -> u32 {
var three : f64 = 1.0;
var i : u32 = 0;
while (i < k) {
three = three * 3.0;
i = i + 1;
}
var two : f64 = 1.0;
var b : u32 = 0;
while (two < three) {
two = two * 2.0;
b = b + 1;
}
return b;
}
// The largest number k trits write, for words too wide for i32: (3^k - 1) / 2.
fn word_max(k: u32) -> f64 {
var three : f64 = 1.0;
var i : u32 = 0;
while (i < k) {
three = three * 3.0;
i = i + 1;
}
return (three - 1.0) / 2.0;
}
// --- Comparing ----------------------------------------------------------------------------
// The highest place where a and b differ, or -1 when they are equal.
fn first_diff(a: i32, b: i32) -> i32 {
var i : i32 = (MAX_TRITS as i32) - 1;
while (i >= 0) {
if (trit_at(a, i as u32) != trit_at(b, i as u32)) {
return i;
}
i = i - 1;
}
return 0 - 1;
}
// a against b as one trit: -1 less, 0 equal, +1 greater, read at the first differing trit.
fn compare(a: i32, b: i32) -> i32 {
const i = first_diff(a, b);
if (i < 0) {
return 0;
}
if (trit_at(a, i as u32) > trit_at(b, i as u32)) {
return 1;
}
return 0 - 1;
}
// Questions with two answers needed to find one of n things: ceil(log2 n).
fn questions2(n: u32) -> u32 {
var reach : u32 = 1;
var q : u32 = 0;
while (reach < n) {
reach = reach * 2;
q = q + 1;
}
return q;
}
// Questions with three answers needed: ceil(log3 n).
fn questions3(n: u32) -> u32 {
var reach : u32 = 1;
var q : u32 = 0;
while (reach < n) {
reach = reach * 3;
q = q + 1;
}
return q;
}
// --- A ternary neuron ---------------------------------------------------------------------
// The neuron's output trit: +1 at or above the threshold, -1 at or below minus it, else 0.
fn activate(sum: i32, threshold: i32) -> i32 {
if (sum >= threshold) {
return 1;
}
if (sum <= 0 - threshold) {
return 0 - 1;
}
return 0;
}
// --- Tests --------------------------------------------------------------------------------
// The value of the trits of n read back: an independent check of trit_at.
fn read_back(n: i32) -> i32 {
var sum : i32 = 0;
var i : u32 = 0;
while (i < MAX_TRITS) {
sum = sum + trit_at(n, i) * pow3(i);
i = i + 1;
}
return sum;
}
test "every number reads back from its trits, and each trit is -1, 0 or +1" {
var n : i32 = 0 - 400;
while (n <= 400) {
assert(read_back(n) == n);
assert(trit_at(n, 0) >= 0 - 1 && trit_at(n, 0) <= 1);
assert(trit_at(n, 3) >= 0 - 1 && trit_at(n, 3) <= 1);
n = n + 1;
}
}
test "eight is nine minus one, and minus eight flips it" {
assert(trit_at(8, 0) == 0 - 1);
assert(trit_at(8, 1) == 0);
assert(trit_at(8, 2) == 1);
assert(trit_at(0 - 8, 2) == 0 - 1);
assert(trit_at(0 - 8, 0) == 1);
assert(trit_at(13, 0) == 1 && trit_at(13, 1) == 1 && trit_at(13, 2) == 1);
}
test "k trits reach (3^k - 1) / 2" {
assert(max_of(1) == 1);
assert(max_of(3) == 13);
assert(max_of(5) == 121);
assert(trits_needed(13) == 3);
assert(trits_needed(14) == 4);
assert(trits_needed(0 - 13) == 3);
assert(trits_needed(0) == 1);
assert(bits_needed(0) == 1);
assert(bits_needed(127) == 8);
assert(bits_needed(128) == 9);
assert(bits_needed(0 - 128) == 8);
assert(bits_needed(0 - 129) == 9);
}
test "negation flips every trit" {
var n : i32 = 0 - 300;
while (n <= 300) {
assert(negate(n) == 0 - n);
assert(trit_at(negate(n), 2) == 0 - trit_at(n, 2));
n = n + 7;
}
}
test "cutting trits rounds to the nearest multiple" {
assert(cut_round(8, 1) == 9);
assert(cut_round(7, 1) == 6);
assert(cut_round(13, 1) == 12);
assert(cut_round(14, 2) == 18);
assert(cut_round(0 - 14, 2) == 0 - 18);
assert(cut_round(4, 1) == 3);
assert(cut_round(5, 1) == 6);
var n : i32 = 0 - 100;
while (n <= 100) {
const d = n - cut_round(n, 2);
assert(d >= 0 - 4 && d <= 4);
n = n + 1;
}
}
test "Kleene logic is Boolean logic on -1 and +1" {
assert(t_min(1, 1) == 1 && t_min(1, 0 - 1) == 0 - 1 && t_min(0 - 1, 0 - 1) == 0 - 1);
assert(t_max(1, 0 - 1) == 1 && t_max(0 - 1, 0 - 1) == 0 - 1);
assert(t_not(1) == 0 - 1 && t_not(0) == 0);
assert(t_min(0, 1) == 0 && t_min(0, 0 - 1) == 0 - 1);
assert(t_max(0, 1) == 1 && t_max(0, 0 - 1) == 0);
}
test "consensus keeps agreement, any keeps the decided input" {
assert(t_consensus(1, 1) == 1 && t_consensus(1, 0) == 0 && t_consensus(0 - 1, 1) == 0);
assert(t_any(0, 1) == 1 && t_any(0 - 1, 0) == 0 - 1 && t_any(1, 0 - 1) == 0 && t_any(0, 0) == 0);
assert(gate(GATE_NOT, 1, 0) == 0 - 1);
assert(gate(GATE_MIN, 1, 0) == 0);
assert(gate(GATE_MAX, 0 - 1, 0) == 0);
assert(gate(GATE_CONSENSUS, 1, 1) == 1);
assert(gate(GATE_ANY, 0, 0 - 1) == 0 - 1);
}
test "a half adder: a + b = sum + 3 carry for all nine inputs" {
var a : i32 = 0 - 1;
while (a <= 1) {
var b : i32 = 0 - 1;
while (b <= 1) {
assert(half_sum(a, b) + 3 * half_carry(a, b) == a + b);
assert(gate(GATE_SUM, a, b) == half_sum(a, b));
assert(gate(GATE_CARRY, a, b) == half_carry(a, b));
b = b + 1;
}
a = a + 1;
}
assert(half_sum(1, 1) == 0 - 1 && half_carry(1, 1) == 1);
assert(half_sum(1, 0 - 1) == 0 && half_carry(1, 0 - 1) == 0);
}
test "nine rows give 19683 two-input gates against 16 in binary" {
assert(ternary_functions(1) == 27);
assert(ternary_functions(2) == 19683);
assert(binary_functions(1) == 4);
assert(binary_functions(2) == 16);
}
test "a full adder covers all 27 inputs" {
var a : i32 = 0 - 1;
while (a <= 1) {
var b : i32 = 0 - 1;
while (b <= 1) {
var c : i32 = 0 - 1;
while (c <= 1) {
assert(full_sum(a, b, c) + 3 * full_carry(a, b, c) == a + b + c);
assert(full_carry(a, b, c) >= 0 - 1 && full_carry(a, b, c) <= 1);
c = c + 1;
}
b = b + 1;
}
a = a + 1;
}
assert(full_sum(1, 1, 1) == 0 && full_carry(1, 1, 1) == 1);
}
test "the ripple adder adds" {
var x : i32 = 0 - 60;
while (x <= 60) {
var y : i32 = 0 - 60;
while (y <= 60) {
assert(ripple_add(x, y) == x + y);
y = y + 11;
}
x = x + 7;
}
assert(carry_into(4, 4, 0) == 0);
assert(carry_into(1, 1, 1) == 1);
assert(carry_into(13, 1, 3) == 1);
}
test "a product by one trit needs no multiplier" {
assert(trit_times(25, 1) == 25);
assert(trit_times(25, 0) == 0);
assert(trit_times(25, 0 - 1) == 0 - 25);
assert(partial(7, 8, 0) == 0 - 7);
assert(partial(7, 8, 1) == 0);
assert(partial(7, 8, 2) == 63);
}
test "long multiplication is the sum of shifted copies" {
var n : i32 = 0 - 40;
while (n <= 40) {
var m : i32 = 0 - 40;
while (m <= 40) {
assert(long_mul(n, m) == n * m);
m = m + 9;
}
n = n + 3;
}
assert(mac_step(10, 1, 4) == 14);
assert(mac_step(10, 0 - 1, 4) == 6);
assert(mac_step(10, 0, 4) == 10);
assert(mac_op(0 - 1) == 0 - 1 && mac_op(0) == 0 && mac_op(1) == 1);
}
test "two bits per trit waste a code, five trits fill a byte" {
assert(code2(0 - 1) == 0 && code2(0) == 1 && code2(1) == 2);
assert(decode2(code2(0 - 1)) == 0 - 1 && decode2(code2(1)) == 1 && decode2(code2(0)) == 0);
assert(code2_valid(2) && !code2_valid(3));
assert(decode2(3) == 0);
assert(pack5(0 - 1, 0 - 1, 0 - 1, 0 - 1, 0 - 1) == 0);
assert(pack5(1, 1, 1, 1, 1) == 242);
assert(pack5(0, 0, 0, 0, 0) == 121);
const b = pack5(1, 0 - 1, 0, 1, 0 - 1);
assert(unpack5(b, 0) == 1 && unpack5(b, 1) == 0 - 1 && unpack5(b, 2) == 0);
assert(unpack5(b, 3) == 1 && unpack5(b, 4) == 0 - 1);
assert(pack5_valid(242) && !pack5_valid(243));
}
test "a byte of five trits uses 99 percent of its bits, two bits per trit 79" {
assert(bit_use(5, 8) > 0.9905 && bit_use(5, 8) < 0.9907);
assert(bit_use(1, 2) > 0.7924 && bit_use(1, 2) < 0.7926);
assert(bits_for_trits(5) == 8);
assert(bits_for_trits(27) == 43);
assert(bits_for_trits(1) == 2);
assert(word_max(27) == 3812798742493.0);
assert(word_max(3) == 13.0);
}
test "two numbers compare at their first differing trit" {
var a : i32 = 0 - 50;
while (a <= 50) {
var b : i32 = 0 - 50;
while (b <= 50) {
var want : i32 = 0;
if (a < b) {
want = 0 - 1;
}
if (a > b) {
want = 1;
}
assert(compare(a, b) == want);
b = b + 3;
}
a = a + 5;
}
assert(first_diff(9, 9) == 0 - 1);
assert(first_diff(8, 9) == 0);
assert(first_diff(13, 0 - 13) == 2);
}
test "three answers find a number in fewer questions than two" {
assert(questions2(1000) == 10);
assert(questions3(1000) == 7);
assert(questions3(27) == 3);
assert(questions2(27) == 5);
assert(questions3(1) == 0);
}
test "the neuron answers with a trit" {
assert(activate(3, 2) == 1);
assert(activate(2, 2) == 1);
assert(activate(1, 2) == 0);
assert(activate(0 - 2, 2) == 0 - 1);
assert(activate(0, 2) == 0);
}
}
All lessons
Module 1 · Three values
Why three, how balanced ternary writes every number without a sign, and what flipping and cutting trits do.
Module 2 · Logic with unknown
Kleene's three-valued gates, two gates binary has no twin for, and addition as a pair of tables.
Module 3 · Adding trits
The half adder, the full adder and a carry that ripples left, one place at a time.
Module 4 · Multiplying without a multiplier
Copy, drop or flip: a product by one trit, long multiplication, and a MAC that only adds.
Module 5 · Trits in binary memory
Two bits per trit, five trits per byte, and the bits a 27-trit word needs.
Module 6 · The TRI-27 instruction word
The 32-bit word the Trinity emulator decodes: its fields, its 47 opcodes and its 15-bit immediate.
Module 7 · A ternary machine
An ALU built from this course's adders, a three-way jump, and a program you can step.
Module 8 · Three answers
Compare at the highest differing trit, find a number in thirds, sort with three-way compares.
Module 9 · Ternary neurons
Weights of -1, 0, +1: one neuron, a detector and a small layer, with no multiplier anywhere.