t27.aiРусский

Sum and carry

You will learn

How the addition of two trits splits into a sum table and a carry table.

Two trits add to something from -2 to +2. Written in balanced ternary that is a sum trit plus three times a carry trit: +1 + +1 = 2 = 3 - 1, carry +1, sum -1. The widget shows both as gates. Counting tables, a two-input ternary gate has 3^9 = 19683 possibilities against 16 in binary. The lesson spec builds XOR from ternary neurons, the hardware side of the same idea.

Try it

Find the two input pairs whose carry is not 0, and check a + b = sum + 3 x carry on each.

Open the interactive lesson →

Sum and carry: addition as two gates
Sum and carry: addition as two gates ↗

The sum trit and the carry trit of a + b are two 3 x 3 tables. There are 19,683 such two-input gates in ternary and 16 in binary.

specs/ternary/ternary_xor.t27

module TernaryXor;
fn tmul(ta: u8, tb: u8) -> i8 {
    if (ta == 1) { return 0; }
    if (tb == 1) { return 0; }
    if (ta == tb) { return 1; }
    return -1;
}
fn dot27(a: u64, b: u64) -> i16 {
    var acc : i16 = 0;
    var i : u32 = 0;
    while (i < 27) {
        var ta : u8 = ((a >> (i << 1)) & 3) as u8;
        var tb : u8 = ((b >> (i << 1)) & 3) as u8;
        acc = acc + tmul(ta, tb) as i16;
        i = i + 1;
    }
    return acc;
}
// Sign at zero: v > 0 -> P, v < 0 -> N, else Z.
fn sign0(v: i16) -> u8 {
    if (v > 0) { return 2; }
    if (v < 0) { return 0; }
    return 1;
}
// Trit negate: P<->N, Z fixed.
fn negate(t: u8) -> u8 {
    if (t == 2) { return 0; }
    if (t == 0) { return 2; }
    return 1;
}
// Pack 2 trits into lanes 0,1 of a chunk; the rest are Z.
fn pack2(t0: u8, t1: u8) -> u64 {
    var z : u64 = 6004799503160661;
    var cleared : u64 = z & 18446744073709551600;
    return cleared | (t0 as u64) | ((t1 as u64) << 2);
}
// Biased ternary neuron: sign(dot(x, w) + bias). The bias is the neuron's
// threshold offset -- what a trained network learns alongside the weights.
fn bneuron(x: u64, w: u64, bias: i16) -> u8 {
    return sign0(dot27(x, w) + bias);
}
// Ternary XOR over binary-embedded inputs {N=-1, P=+1}: P if the inputs differ,
// N if they match. XOR is NOT linearly separable -- a single neuron cannot
// compute it -- so this is a genuine 2-LAYER network:
//   h1 = sign(a + b - 1)   (AND-like)
//   h2 = sign(a + b + 1)   (OR-like)
//   out = sign(h2 + (-h1) - 1)   (h2 AND NOT h1)
pub fn ternary_xor(a: u8, b: u8) -> u8 {
    var x : u64 = pack2(a, b);
    var w_pp : u64 = pack2(2, 2);
    var h1 : u8 = bneuron(x, w_pp, -1);
    var h2 : u8 = bneuron(x, w_pp, 1);
    var hidden : u64 = pack2(h2, negate(h1));
    return bneuron(hidden, w_pp, -1);
}
test xor_p_p { assert_eq(ternary_xor(2, 2), 0); }
test xor_p_n { assert_eq(ternary_xor(2, 0), 2); }
test xor_n_p { assert_eq(ternary_xor(0, 2), 2); }
test xor_n_n { assert_eq(ternary_xor(0, 0), 0); }
// W697: the hardware boundary, derived from the CALL GRAPH.
//
// This spec has several functions that take a parameter and return a value,
// so W696's count rule left it AMBIGUOUS. But exactly ONE of them is called
// by no other function -- it is the root, and every other candidate is a
// helper it reaches. With one root the choice is forced by structure rather
// than by count, and forwarding to it still invents nothing.
//
// The call graph is built from FUNCTION BODIES ONLY. Counting `test` blocks
// as callers makes the rule vacuous -- every function is called by its own
// test, so nothing is ever a root.
//
// Measured: the rule resolved 14 of 136 ambiguous specs, 6 of them with
// types that can cross a module boundary. It is narrow because most of the
// rest are libraries of INDEPENDENT functions, which have several roots and
// correctly stay ambiguous.
fn on_comb(a: u8, b: u8) -> u8 { return ternary_xor(a, b); }

endmodule

Open the lesson's spec in the player ↗

All lessons