Конспект: необычные основания

Понятия

Основание задаёт веса позиций: цифра в позиции i умножается на b^i. Битовая строка без договорённости о весах ещё не задаёт числовое значение.

Основание −2 использует цифры 0 и 1 с весами 1,−2,4,−8,…. Отдельного знакового бита нет. Ноль записывается как 0.

Гауссово целое - пара целых (a,b), записанная как a+bi, где i²=−1. Основание β=−1+i позволяет представить такие пары конечными строками 0 и 1.

Евклидово деление в этой главе: n=dq+r, 0≤r<|d|, d≠0. Это не всегда деление с усечением частного к нулю.

Что унести

Основание −2:
    кодирование: r=n%2; n=(n-r)//(-2)
    остатки собираются от младшего к старшему
    чтение слева направо: value=-2*value+digit

Ширина w, A - единицы во всех нечётных позициях:
    минимум = -A, максимум = 2^w-1-A
    value = (word XOR A)-A
    word = (value+A) XOR A, только внутри диапазона

Сложение:
    s = цифра первого + цифра второго + входящий перенос
    digit = s%2
    carry = (s-digit)//(-2)
    продолжать, пока не закончились и слова, и перенос

Примеры: 11 обозначает −1, 110 обозначает 2, 1101 обозначает −3. Четыре бита дают диапазон от −10 до 5; шесть - от −42 до 21. Сдвиг влево умножает значение на −2. Изменение знака можно получить сложением исходного слова с его сдвинутой копией.

Основание β=−1+i:
    r = (a+b)%2
    новые координаты одновременно:
        a' = (b-a+r)//2
        b' = (r-a-b)//2
    чтение цифры d: (a,b) <- (-a-b+d, a-b)

Запись 1100 означает 2, 11 означает i, 1011 означает 2+3i. В основании −1−i та же строка даёт комплексно сопряжённое значение. Для других оснований меняются и допустимые остатки, и свойства конечности. Например, при основании 2i и цифрах 0,1,2,3 число i записывается как 10.2.

Группы по два бита основания −2 дают основание 4 и цифры −2,−1,0,1. Пары цифр основания −1+i дают основание −2i и цифры 0,1,−1+i,i. При основании 1+i конечность уже не гарантирована: для i остаток 1, а частное снова i. Формальная запись с бесконечным хвостом слева требует иной договорённости и не является обычным сходящимся комплексным рядом.

Цена представления

При N различных значениях, целочисленном основании b≥2 и цене разряда k·b:

число разрядов = ceil(log_b N)
точная цена = k*b*ceil(log_b N)
сглаженная цена = k*ln(N)*b/ln(b)

Сглаженный минимум при вещественном b=e; среди целых оснований этой модели выигрывает 3. Округление числа разрядов меняет сравнение для конкретного N. Для N=16 цены оснований 2,3,4 при k=1 равны 8,9,8; для N=81 - 14,12,16. Реальное устройство может иметь другую зависимость цены от числа состояний.

Ловушки джокера

Складывать упаковки обычным a+b. При новом основании это другие числовые значения. Пример 11+1 должен дать 0, а обычное двоичное сложение дало бы 100.

Выбросить отрицательный перенос. В основании −2 он необходим и может потребовать ещё двух разрядов после конца входа. Ширину результата проверяют отдельно.

Обновить координаты по очереди. Формулы частного используют обе старые координаты; последовательное присваивание без сохранения значений портит комплексное число.

Непрерывный минимум выдать за устройство. Число состояний целое; для диапазона 0…M состояний M+1. Округления и фактическая стоимость оборудования обязательны.