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

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

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

Определение

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

{ Displaystyle E (b, N) = b lfloor log _ {b} (N) +1 rfloor ,}

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

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

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

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

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

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

{ Displaystyle E (b, N) = b lfloor log _ {b} (N) +1 rfloor приблизительно b log _ {b} (N) = {b over ln (b)} ln (N)}

{ Displaystyle {Е (b, N) над ln (N)} приблизительно {b над ln (b)}}

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

е имеет самую низкую экономию основания

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

Во-первых, обратите внимание, что функция

{ Displaystyle е (х) = { гидроразрыва {х} { ln (x)}} ,}

строго убывает на 1 < Икс < е и строго возрастает Икс > е. Следовательно, его минимум при x> 1 приходится на е.

Далее рассмотрим, что

{ Displaystyle {E (b, N)} приблизительно {b { log _ {b} (N)}} = {b { ln (N) over ln (b)}}}

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

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

Радиксная экономия оснований б₁ и б₂ можно сравнить для большого значения N:

{ displaystyle {{E (b_ {1}, N)} over {E (b_ {2}, N)}} приблизительно {{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})}} ,.}

Выбор е за б₂ дает экономию по сравнению с е функцией:

{ displaystyle {{E (b)} over {E (e)}} приблизительно {{b ln (e)} over {e ln (b)}} = {{b} over {e ln (b)}} ,}

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

Основание б	Средн. E(б,N) N = От 1 до 6	Средн. E(б,N) N = От 1 до 43	Средн. E(б,N) N = От 1 до 182	Средн. E(б,N) N = От 1 до 5329	${ Displaystyle {{Е (б)} над {Е (е)}}}$	Относительный размер E (б )/ E (е )
1	3.5	22.0	91.5	2,665.0	${ displaystyle infty}$	—
2	4.7	9.3	13.3	22.9	1.0615	1.0615
е	4.5	9.0	12.9	22.1	1.0000	1
3	5.0	9.5	13.1	22.2	1.0046	1.0046
4	6.0	10.3	14.2	23.9	1.0615	1.0615
5	6.7	11.7	15.8	26.3	1.1429	1.1429
6	7.0	12.4	16.7	28.3	1.2319	1.2319
7	7.0	13.0	18.9	31.3	1.3234	1.3234
8	8.0	14.7	20.9	33.0	1.4153	1.4153
9	9.0	16.3	22.6	34.6	1.5069	1.5069
10	10.0	17.9	24.1	37.9	1.5977	1.5977
12	12.0	20.9	25.8	43.8	1.7765	1.7765
15	15.0	25.1	28.8	49.8	2.0377	2.0377
16	16.0	26.4	30.7	50.9	2.1230	2.123
20	20.0	31.2	37.9	58.4	2.4560	2.456
30	30.0	39.8	55.2	84.8	3.2449	3.2449
40	40.0	43.7	71.4	107.7	3.9891	3.9891
60	60.0	60.0	100.5	138.8	5.3910	5.391

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

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

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

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

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

Radix р	Трубки N = rn
2	39.20
3	38.24
4	39.20
5	42.90
10	60.00

Авторы делают вывод:

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

Прочие критерии

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

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

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

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

S.L. Херст, «Многозначная логика - ее статус и будущее», IEEE trans. компьютеры, Vol. C-33, № 12, стр. 1160–1179, DEC 1984.
Дж. Т. Батлер, «Многозначная логика в проектировании СБИС», Серия изданий IEEE Computer Society Press, 1991.
СМ. Аллен, Д.Д. Гивоне «Алгебра, ориентированная на реализацию Аллена-Живона», в Информатика и многозначная логика: теория и приложения, D.C. Rine, второе издание, D.C. Rine, ed., The Elsevier North-Holland, New York, N.Y., 1984. pp. 268–288.
Г. Абрахам, "Многозначные интегральные схемы с отрицательным сопротивлением", в Информатика и многозначная логика: теория и приложения, D.C. Rine, второе издание, D.C. Rine, ed., The Elsevier North-Holland, New York, N.Y., 1984. pp. 394–446.

[Hayes-1] а ^б Брайан Хейс (2001). «Третья база». Американский ученый. 89 (6): 490. Дои:10.1511/2001.40.3268. Архивировано из оригинал на 2014-01-11. Получено 2013-07-28.

[2] Бентли, Джон; Седжвик, Боб (1998-04-01). "Деревья троичного поиска". Журнал доктора Добба. UBM Tech. Получено 2013-07-28.

[3] Сотрудники компании Engineering Research Associates (1950). «3-6 р-триодный счетчик, по модулю р". Высокоскоростные вычислительные устройства. Макгроу-Хилл. стр. 22–23. Получено 2008-08-27.

[4] Сотрудники компании Engineering Research Associates (1950). "3-7 2р-триодный счетчик по модулю р". Высокоскоростные вычислительные устройства. Макгроу-Хилл. стр. 23–25. Получено 2008-08-27.

[5] Сотрудники компании Engineering Research Associates (1950). «6-7 Экономия, достигнутая Radix Choice». Высокоскоростные вычислительные устройства. Макгроу-Хилл. стр. 84–87. Получено 2008-08-27.

[6] Сотрудники компании Engineering Research Associates (1950). «16-2 Новые методы». Высокоскоростные вычислительные устройства. Макгроу-Хилл. стр. 419–421. Получено 2008-08-27.

[1]

[2]

[3]

[4]

[5]

[6]