Какое основание дешевле: модель и округления

Если выводишь цену регистра из числа состояний и можешь показать случай, где округление меняет сравнение оснований, переходи к «Теперь сам».

Как думаешь, три состояния выгоднее двух

Чтобы хранить 16 разных значений, нужны четыре двоичных цифры. Если одна двоичная цифра стоит две условные единицы, итоговая цена 8. У троичного регистра трёх цифр достаточно: 3³=27. Но каждая стоит 3, поэтому цена 9. Двоичный регистр выиграл.

Теперь нужны 81 значение. Двоичных цифр требуется семь: шести хватило бы только на 64 состояния. Цена 14. Четырёх троичных цифр хватает ровно: 3⁴=81, цена 12. На этот раз троичный выиграл. Значит выражение «троичная запись дешевле» без указания числа значений и модели уже слишком сильное.

На что это похоже

Ты арендуешь шкафы с разным числом ячеек. Большой шкаф дороже маленького, но может сократить число нужных шкафов. Если разрешить арендовать дробные шкафы, сравнение будет плавным и простым. Реальный заказ состоит из целых шкафов: последний часто заполнен не полностью, но платить нужно за него целиком.

Здесь разряды - шкафы, а состояния - возможные значения содержимого. Неполное использование последнего разряда объясняет разницу между гладкой формулой и точной ценой. Называть эту разницу «малой погрешностью» для короткого регистра нельзя: она способна поменять лучший вариант.

Механизм: от ёмкости к цене

Пусть основание b - целое не меньше 2. В одном разряде b вариантов, в двух b², в m разрядах b^m. Чтобы хранить N значений, требуется b^m≥N, поэтому минимальное m=ceil(log_b N). Здесь N - число значений, а не наибольшее значение. Для диапазона 0…M нужно подставлять N=M+1.

Пусть стоимость разряда равна k·b, где k>0 - одна и та же константа для всех сравниваемых оснований. Тогда цена регистра равна k·b·m. Это предположение модели, а не закон электроники. Оно учитывает только хранение, оставляя за рамками сумматор, проводники, чтение, надёжность и кодирование внешних данных.

Если снять округление, получим C(b)=k·b·log_b N=k·ln(N)·b/ln(b). При фиксированном N>1 первые множители не влияют на лучший выбор, поэтому сравниваем только b/ln(b). Рост основания сокращает число цифр, но одновременно делает каждый разряд дороже: формула выражает обе причины.

Правило

В модели линейной цены состояний точная стоимость равна k·b·ceil(log_b N). Сглаженная цена k·ln(N)·b/ln(b) минимальна при вещественном b=e. Среди целых оснований сглаженный минимум у 3. Для конечного регистра сравнивай точные целые числа разрядов, а для устройства сначала проверь саму модель стоимости.

В программе ниже число разрядов вычисляется умножением целой ёмкости на основание. Так мы не рискуем получить 4.0000000001 вместо точного логарифма 4 и случайно округлить вверх ещё раз. Алгоритм останавливается, как только ёмкость достигла N. Для N=1 достаточно нулевого числа разрядов: единственное значение можно заранее знать без хранения.

Разбор: непрерывный минимум без догадки

Число e≈2,71828 характеризуется равенством ln(e)=1. Докажем, что b/ln(b)≥e для b>1. Используем неравенство ln(x)≤x−1 при x>0. Для x≥1 площадь под 1/u на отрезке от 1 до x не больше площади прямоугольника высоты 1; для 0<x<1 знак интеграла меняется, и получается тот же вывод. Равенство достигается только при x=1.

Подставим x=b/e. Получим ln(b)−1≤b/e−1, то есть ln(b)≤b/e. Так как при b>1 логарифм положителен, деление даёт b/ln(b)≥e. Равенство возможно при b/e=1, то есть b=e. Теперь результат выведен из модели, а не выбран из перебранных двоичной и троичной записей.

Для целых оснований достаточно сравнить 2 и 3, если докажем, что после 3 цена растёт. Пусть c>b≥3. Уже использованное неравенство даёт ln(c/b)≤c/b−1, поэтому ln(c)≤ln(b)+(c/b−1). Так как ln(b)>1, правая часть меньше (c/b)·ln(b). Разделив на c, получаем ln(c)/c<ln(b)/b, то есть c/ln(c)>b/ln(b). Все целые основания больше 3 хуже тройки. Остаётся сравнить: 2/ln2≈2,88539, 3/ln3≈2,73072, выигрывает 3.

Разбор: цена после округления

import math


def digits(n, base):
    count, states = 0, 1
    while states < n:
        states *= base
        count += 1
    return count


for n in [2, 16, 81, 256]:
    costs = [(b, b * digits(n, b)) for b in range(2, 6)]
    print("состояний", n, costs)
ratio = (2 / math.log(2)) / (3 / math.log(3))
print("цена 2 / цена 3 без округления:", f"{ratio:.6f}")
print("непрерывный минимум:", f"{math.e:.6f}")

состояний 2 [(2, 2), (3, 3), (4, 4), (5, 5)]
состояний 16 [(2, 8), (3, 9), (4, 8), (5, 10)]
состояний 81 [(2, 14), (3, 12), (4, 16), (5, 15)]
состояний 256 [(2, 16), (3, 18), (4, 16), (5, 20)]
цена 2 / цена 3 без округления: 1.056642
непрерывный минимум: 2.718282

Каждая пара в квадратных скобках означает (основание, цена) при k=1. В строке для 16 цена оснований 2 и 4 одинакова: 2·4=4·2=8. У основания 3 три цифры стоят 9, у основания 5 две цифры стоят 10. Для 81 выигрывает основание 3. Для 256 двоичное снова дешевле троичного.

Отношение 1,056642 относится к сглаженной цене двоичного и троичного вариантов. В пределах этой модели двоичная запись примерно на 5,66% дороже. Это отношение не зависит от N, потому что общий множитель ln(N) сокращается. Но в точной формуле множители ceil(log_b N) уже не сокращаются, и строки программы показывают, что один процентный вывод ко всем N неприменим.

Что ломается без этого

Берут наибольшее значение вместо числа состояний: для хранения 0…16 подставляют 16 и получают четыре бита, хотя нужны пять. Или округляют вниз число цифр и теряют верхние значения диапазона. Исправление - сначала записать, сколько различных значений требуется, затем проверить условие b^m≥N.

Другая ошибка - выдавать непрерывный минимум за готовую схему. У регистра не может быть 2,718 состояния. Нельзя также забыть, что реальная цена различения уровней зависит от шума и технологии. Если многоуровневый элемент требует непропорционально дорогого чтения, функция цены будет другой. Математически правильное решение неверной модели не отвечает инженерному вопросу.

Зачем это в работе

Так сравнивают варианты кодирования и структуры хранения: задают ёмкость, считают число единиц хранения, умножают на их цену, затем проверяют округления и ограничения устройства. Например, выигрыш по числу символов ещё не означает выигрыша по байтам, если каждый символ требует более дорогого хранения. Модель нужна, чтобы назвать причину выбора и увидеть, какое предположение может изменить результат.

Теперь сам

Сравни основания 2,3,4 при N=10 и цене одного разряда b. Затем скажи, изменится ли победитель, если все цены одновременно умножить на 7. Можно ли по этому ответу выбрать основание настоящего процессора?