Радикс-экономика

Количество цифр, необходимых для выражения числа в определенной системе счисления

Экономия системы счисления числа в определенной базе (или системе счисления ) — это количество цифр, необходимых для его выражения в этой базе, умноженное на базу (количество возможных значений, которые может иметь каждая цифра). Это одно из многочисленных предложений, которые были сделаны для количественной оценки относительных затрат на использование разных систем счисления для представления чисел, особенно в компьютерных системах.

Экономика Radix также имеет значение для организационной структуры, сетей и других областей.

Определение

Экономия системы счисления E ( b , N ) для любого конкретного числа N в данной базе b определяется как

${\displaystyle E(b,N)=b\lfloor \log _{b}(N)+1\rfloor \,}$

где мы используем функцию пола и ${\displaystyle \lfloor \rfloor }$логарифм по основанию b . ${\displaystyle \log _{b}}$

Если и b , и N являются целыми положительными числами, то экономия системы счисления равна количеству цифр , необходимых для выражения числа N по основанию b , умноженного на основание b . ^[1] Таким образом, десятичная экономика измеряет стоимость хранения или обработки числа N в базе b , если стоимость каждой «цифры» пропорциональна b . Таким образом, база с более низким средним показателем экономики в некотором смысле более эффективна, чем база с более высоким средним показателем экономики. ${\displaystyle E(b,N)}$

Например, десятичное число 100 имеет три цифры, поэтому его экономия по системе счисления равна 10 × 3 = 30; его двоичное представление имеет семь цифр (1100100 ₂ ), поэтому его система счисления имеет экономию 2×7 = 14 по основанию 2; в базе 3 его представление имеет пять цифр (10201 ₃ ) с экономией системы счисления 3×5 = 15; в базе 36 (2S ₃₆ ) его экономия по основанию равна 36×2 = 72.

Если представить, что число представлено кодовым замком или счетным счетчиком , в котором каждое колесо имеет b цифровых граней, от и имеющих колеса, то экономия системы счисления - это общее количество цифровых граней, необходимых для представления любого целого числа от 0 включительно. к Н.​ ${\displaystyle 0,1,...,b-1}$ ${\displaystyle \lfloor \log _{b}(N)+1\rfloor }$ ${\displaystyle b\lfloor \log _{b}(N)+1\rfloor }$

Асимптотическое поведение

Экономию по системе счисления для больших N можно аппроксимировать следующим образом:

${\displaystyle E(b,N)=b\lfloor \log _{b}(N)+1\rfloor \sim b\ \log _{b}(N)={b \over \ln(b)}\ln(N).}$

${\displaystyle {E(b,N) \over \ln(N)}\sim {b \over \ln(b)}.}$

Асимптотически лучшая экономия системы счисления получается для системы счисления 3, поскольку она достигает минимума в положительных целых числах: ${\displaystyle b \over \ln(b)}$ ${\displaystyle b=3}$

${\displaystyle {2 \over \ln(2)}\approx 2.88539\,,}$

${\displaystyle {3 \over \ln(3)}\approx 2.73072\,,}$

${\displaystyle {4 \over \ln(4)}\approx 2.88539\,.}$

По основанию 10 имеем:

${\displaystyle {10 \over \ln(10)}\approx 4.34294\,.}$

Радиксная экономика разных базисов

e имеет самую низкую систему счисления

Вот доказательство того, что база e является действительной базой с наименьшей средней экономикой по системе счисления:

Прежде всего заметим, что функция

${\displaystyle f(x)={\frac {x}{\ln(x)}}\,}$

строго убывает при 1 < x < e и строго возрастает при x > e . Поэтому его минимум при x > 1 приходится на e .

Далее учтите, что

${\displaystyle {E(b,N)}\approx {b\ {\log _{b}(N)}}={b{\ln(N) \over \ln(b)}}}$

Тогда для постоянного N будет иметь минимум в e по той же причине, что и f(x), что означает, что e является базой с наименьшей средней экономией по системе счисления. Поскольку 2 / ln(2) ≈ 2,89 и 3 / ln(3) ≈ 2,73, отсюда следует, что 3 — это целочисленное основание с наименьшей средней экономией по счислению. ${\displaystyle {E(b,N)}}$

Сравнение разных баз

Экономию оснований b ₁ и b ₂ можно сравнить при большом значении N :

${\displaystyle {{E(b_{1},N)} \over {E(b_{2},N)}}\approx {{b_{1}{\log _{b_{1}}(N)}} \over {b_{2}{\log _{b_{2}}(N)}}}={\left({\dfrac {b_{1}\ln(N)}{\ln(b_{1})}}\right) \over \left({\dfrac {b_{2}\ln(N)}{\ln(b_{2})}}\right)}={{b_{1}\ln(b_{2})} \over {b_{2}\ln(b_{1})}}\,.}$

Выбор e для b ₂ дает экономию по сравнению с e по функции:

${\displaystyle {{E(b)} \over {E(e)}}\approx {{b\ln(e)} \over {e\ln(b)}}={{b} \over {e\ln(b)}}\,}$

Средняя экономия по системе счисления от различных оснований до нескольких произвольных чисел (без учета близости к степеням от 2 до 12 и e ) приведена в таблице ниже. Также показана экономия по системе счисления по сравнению с экономией e . Обратите внимание, что экономия по системе счисления любого числа в базе 1 равна этому числу, что делает его наиболее экономичным для первых нескольких целых чисел, но по мере того, как N стремится к бесконечности, увеличивается и его относительная экономия.

Эффективность троичного дерева

Одним из результатов относительной экономии базы 3 является то, что троичные деревья поиска предлагают эффективную стратегию поиска элементов базы данных. ^[2] Подобный анализ показывает, что оптимальная конструкция большой телефонной системы меню , позволяющая минимизировать количество вариантов меню, которые должен прослушать средний клиент (т. е. произведение количества вариантов на одно меню и количества уровней меню), составляет иметь три варианта в меню. ^[1]

Эффективность компьютерного оборудования

В справочнике « Высокоскоростные вычислительные устройства» 1950 года описывается конкретная ситуация с использованием современных технологий. Каждая цифра числа будет храниться как состояние кольцевого счетчика , состоящего из нескольких триодов . Будь то электронные лампы или тиратроны , триоды были самой дорогой частью счетчика. Для небольших радиусов r меньше примерно 7 для одной цифры требуется r триодов. ^[3] (Для более крупных оснований требовалось 2 r триода, расположенных в виде r триггеров , как в десятичных счетчиках ENIAC.) [ ^4]

Таким образом, количество триодов в числовом регистре с n цифрами было rn . Для представления чисел до 10 ⁶ понадобилось следующее количество трубок:

Авторы заключают,

При этих предположениях система счисления 3 в среднем является наиболее экономичным выбором, за ней следуют системы счисления 2 и 4. Эти предположения, конечно, справедливы лишь приблизительно, и выбор системы счисления 2 в качестве системы счисления часто оправдан на более полный анализ. Даже при оптимистическом предположении, что 10 триодов дадут десятичное кольцо, система счисления 10 приводит примерно в полтора раза к сложности системы счисления 2, 3 или 4. Это, вероятно, важно, несмотря на поверхностный характер использованных здесь аргументов. ^[5]

Другие критерии

В другом приложении авторы « Высокоскоростных вычислительных устройств» рассматривают скорость, с которой может быть отправлено закодированное число, как серию высокочастотных импульсов напряжения. Для этого приложения компактность представления более важна, чем в приведенном выше примере хранения. Они заключают: «При переходе от двоичной к тройной системе можно сэкономить 58 процентов. Меньший процентный выигрыш достигается при переходе от системы счисления 3 к системе счисления 4». ^[6]

Двоичное кодирование имеет заметное преимущество перед всеми другими системами: большую помехоустойчивость. Случайные колебания напряжения с меньшей вероятностью будут генерировать ошибочный сигнал, а схемы могут быть построены с более широкими допусками по напряжению и при этом точно представлять однозначные значения.

Смотрите также

• Троичный компьютер
• Список систем счисления

Рекомендации

1. Брайан Хейс (2001). «Третья база». Американский учёный . 89 (6): 490. дои : 10.1511/2001.40.3268. Архивировано из оригинала 11 января 2014 г. Проверено 28 июля 2013 г.
2. Бентли, Джон; Седжвик, Боб (1 апреля 1998 г.). «Тройные деревья поиска». Журнал доктора Добба . УБМ Тех . Проверено 28 июля 2013 г.
3. Сотрудники Ассоциации инженерных исследований (1950). «3-6 Счетчик r- триодов по модулю r ». Высокоскоростные вычислительные устройства. МакГроу-Хилл. стр. 22–23 . Проверено 27 августа 2008 г.
4. Сотрудники Ассоциации инженерных исследований (1950). «3-7 2- триодный счетчик по модулю r ». Высокоскоростные вычислительные устройства. МакГроу-Хилл. стр. 23–25 . Проверено 27 августа 2008 г.
5. Сотрудники Ассоциации инженерных исследований (1950). «Экономия 6–7, достигнутая выбором системы счисления». Высокоскоростные вычислительные устройства. МакГроу-Хилл. стр. 84–87 . Проверено 27 августа 2008 г.
6. Сотрудники Ассоциации инженерных исследований (1950). «16-2 Новые методы». Высокоскоростные вычислительные устройства. МакГроу-Хилл. стр. 419–421 . Проверено 27 августа 2008 г.

дальнейшее чтение

• С.Л. Херст, «Многозначная логика – ее статус и будущее», IEEE пер. компьютеры , Том. C-33, № 12, стр. 1160–1179, декабрь 1984 г.
• Дж. Т. Батлер, «Многозначная логика в проектировании СБИС», серия IEEE Computer Society Press Technology, 1991.
• К.М. Аллен, Д.Д. Гивоне «Алгебра, ориентированная на реализацию Аллена-Гивоне», в книге « Информатика и многозначная логика: теория и приложения» , Д.С. Райн, второе издание, Д.С. Райн, изд., The Elsevier North-Holland, Нью-Йорк, Нью-Йорк , 1984. С. 268–288.
• Г. Абрахам, «Интегральные схемы с многозначным отрицательным сопротивлением», в книге « Информатика и многозначная логика: теория и приложения» , Д.С. Райн, второе издание, Д.С. Райн, изд., The Elsevier North-Holland, Нью-Йорк, штат Нью-Йорк, 1984. стр. 394–446.