One ternary neuron
You will learn
How a neuron with weights -1, 0, +1 computes without multiplying.
A neuron multiplies each input by a weight, adds the products and compares the sum with a threshold. With ternary weights every product is a copy, a zero or a flip, so the sum is adds and subtracts only. The spec's activate() answers +1 at or above the threshold, -1 at or below minus it and 0 between: a neuron that can say not sure.
Try it
Draw a vertical bar on the input and raise the threshold until the neuron stops firing; then press weights until it fires on a horizontal bar.
Nine inputs and nine weights of -1, 0, +1. Each product is a copy, a zero or a flip; the sum against a threshold gives an output 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.