t27.aiEnglish

Почему три

Вы узнаете

Почему основание 3 — самое дешёвое целое основание для записи чисел и что этот довод упускает.

Число в системе с основанием b занимает сколько-то цифр, и каждая цифра должна различать b состояний. Если цена цифры равна b, число стоит b, умноженное на число цифр. Виджет запускает собственную cost() спеки: любое число до 999999 стоит 39 в основании 3 и 40 в основаниях 2 и 4. На длинном отрезке цена одной цифры равна b / ln b, и минимум у неё в точке e; 3 — ближайшее к ней целое. Модель не объясняет, почему победила двоичная система: элементы на два состояния дёшевы, быстры и надёжны.

Попробовать

Переберите все диапазоны и отметьте самое дешёвое основание; найдите диапазон, где выигрывает основание 2, и объясните, почему кривая всё равно за 3.

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

Why three: what a number costs in each base
Why three: what a number costs in each base ↗

Pick a range of numbers. Every base pays digits times states per digit; base 3 pays least, bases 2 and 4 tie behind it.

specs/ternary/radix_economy.t27

// SPDX-License-Identifier: Apache-2.0
// specs/ternary/radix_economy.t27 -- why three: what a number costs in each base
// Host: gHashTag/trinity apps/website, lesson 1 of the course "The ternary machine" (specs/course/
//       ternary-computing.t27) and its widget tc-why-three: the page draws what these fn bodies
//       compute, compiled to wasm (scripts/t27-logic.mjs in gHashTag/999-multibots-telegraf).
//
// THE MODEL (radix economy): writing every number below N in base b takes d = ceil(log_b N)
// digits, and a digit of base b needs hardware that tells b states apart. Take the price of one
// digit as b, so the price of a number is b * d. Over a range, b * log_b N = (b / ln b) * ln N, and
// b / ln b is smallest at b = e = 2.718...; among whole bases 3 is cheapest, 2 and 4 tie behind it
// (B. Hayes, "Third Base", American Scientist 89(6), 2001; the argument is older, in Knuth, TAOCP
// vol. 2, 4.1).
//
// WHAT IT DOES NOT CLAIM: "a digit costs b" is a model, not a transistor count. Binary won for
// reasons this model leaves out (two-state devices are cheap, fast and robust); the lesson says so.
// Claim status: checked by the tests below, against digit counts worked by hand.
// phi^2 + 1/phi^2 = 3 | TRINITY

module ternary::radix_economy {

    pub const KIND : str = "widget-logic";
    pub const ID : str = "radix-economy";
    pub const VERSION : u8 = 1;
    pub const E : f64 = 2.718281828459045;

    // How many base-b digits the number n needs (n >= 1, b >= 2).
    fn digits(n: u32, b: u32) -> u32 {
        var reach : u32 = 1;
        var d : u32 = 0;
        while (reach <= n && d < 40) {
            if (reach > 4294967295 / b) {
                return d + 1;
            }
            reach = reach * b;
            d = d + 1;
        }
        if (d == 0) {
            return 1;
        }
        return d;
    }

    // The price of writing n in base b: digits times states per digit.
    fn cost(n: u32, b: u32) -> u32 {
        return digits(n, b) * b;
    }

    // ln x for x > 0: 2 atanh((x - 1) / (x + 1)), the series summed until it stops moving.
    fn ln(x: f64) -> f64 {
        const y = (x - 1.0) / (x + 1.0);
        const y2 = y * y;
        var term : f64 = y;
        var sum : f64 = 0.0;
        var k : f64 = 1.0;
        while (k < 400.0) {
            sum = sum + term / k;
            term = term * y2;
            k = k + 2.0;
        }
        return 2.0 * sum;
    }

    // The per-digit price of base b over a long range: b / ln b. Smallest at b = e.
    fn economy(b: f64) -> f64 {
        return b / ln(b);
    }

    // The cheapest whole base from 2 to max_base for writing numbers up to n.
    fn cheapest(n: u32, max_base: u32) -> u32 {
        var best : u32 = 2;
        var b : u32 = 3;
        while (b <= max_base) {
            if (cost(n, b) < cost(n, best)) {
                best = b;
            }
            b = b + 1;
        }
        return best;
    }

    fn near(a: f64, b: f64) -> bool {
        return a - b < 0.0005 && b - a < 0.0005;
    }

    test "digit counts worked by hand" {
        assert(digits(999999, 2) == 20);
        assert(digits(999999, 3) == 13);
        assert(digits(999999, 4) == 10);
        assert(digits(999999, 10) == 6);
        assert(digits(1, 2) == 1);
        assert(digits(8, 2) == 4);
        assert(digits(26, 3) == 3);
        assert(digits(27, 3) == 4);
    }

    test "a million costs 39 in base 3 and 40 in bases 2 and 4" {
        assert(cost(999999, 3) == 39);
        assert(cost(999999, 2) == 40);
        assert(cost(999999, 4) == 40);
        assert(cost(999999, 10) == 60);
        assert(cheapest(999999, 10) == 3);
    }

    test "b / ln b is smallest at e, and 3 beats 2" {
        assert(near(ln(E), 1.0));
        assert(near(ln(2.0), 0.693147));
        assert(near(economy(E), 2.718282));
        assert(near(economy(3.0), 2.730718));
        assert(near(economy(2.0), 2.885390));
        assert(near(economy(4.0), 2.885390));
        assert(economy(3.0) < economy(2.0));
        assert(economy(E) < economy(3.0));
    }
}

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

Все уроки