t27.aiEnglish

Сумма и перенос

Вы узнаете

Как сложение двух тритов распадается на таблицу суммы и таблицу переноса.

Два трита в сумме дают число от -2 до +2. В сбалансированной троичной записи это трит суммы плюс трижды трит переноса: +1 + +1 = 2 = 3 - 1, перенос +1, сумма -1. Виджет показывает оба как вентили. Если считать таблицы, у двухвходового троичного вентиля 3^9 = 19683 вариантов против 16 в двоичной. Спека урока собирает XOR из троичных нейронов: аппаратная сторона той же идеи.

Попробовать

Найдите две пары входов, у которых перенос не равен 0, и проверьте для каждой a + b = sum + 3 x carry.

Открыть интерактивный урок →

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

Открыть спеку урока в плеере ↗

Все уроки