Оптимальный выбор системы счисления

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

Определение

Стоимость представления числа N в данной базе b можно определить как

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

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

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

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

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

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

Количество $E(b,N)$ для больших N можно аппроксимировать следующим образом:

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

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

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

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

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

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

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

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

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

Значения $E(b,N)$ оснований b ₁ и b ₂ можно сравнивать при большом значении N :

{{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(b)} \over {E(e)}}\approx {{b\ln(e)} \over {e\ln(b)}}={{b} \over {e\ln(b)}}\,.

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

База б	декабрь. Е ( б , Н ) Н = от 1 до 6	декабрь. Е ( б , Н ) Н = от 1 до 43	декабрь. Е ( б , Н ) Н = от 1 до 182	декабрь. Е ( б , Н ) Н = от 1 до 5329	${{E(b)} \over {E(e)}}$	Относительный размер Е ( б ) / Е ( е )
1	3.5	22.0	91.5	2,665.0	$\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 ]}

В $d$ -арной куче — структура данных приоритетной очереди, основанная на $d$ -арных деревьях, наихудшее количество сравнений на операцию в куче, содержащее $n$ элементы это $d\log _{d}n$ (с точностью до членов низшего порядка), та же формула, что и выше. Было предложено выбрать $d=3$ или $d=4$ может обеспечить оптимальную производительность на практике. ^{[ 3 ]}

Брайан Хейс предполагает, что $E(b,N)$ может быть подходящей мерой сложности меню интерактивного голосового ответа : в древовидном меню телефона с $n$ результаты и $r$ вариантов за шаг, время перемещения по меню пропорционально произведению $r$ (время для представления вариантов выбора на каждом этапе) с $\log _{r}n$ (количество вариантов выбора, которые необходимо сделать, чтобы определить результат). Согласно этому анализу, оптимальное количество вариантов выбора на шаг в таком меню равно трем. ^{[ 1 ]}

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

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

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

Основание r	Трубки N = р-н
2	39.20
3	38.24
4	39.20
5	42.90
10	60.00

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

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

См. также

Ссылки

^ Перейти обратно: ^а ^б ^с Брайан Хейс (2001). «Третья база» . Американский учёный . 89 (6): 490. дои : 10.1511/2001.40.3268 . Архивировано из оригинала 11 января 2014 г. Проверено 28 июля 2013 г.
^ Бентли, Джон; Седжвик, Боб (1 апреля 1998 г.). «Тройные деревья поиска» . Журнал доктора Добба . УБМ Тех . Проверено 28 июля 2013 г.
^ Тарьян, Р.Э. (1983). «3.2.d - кучи». Структуры данных и сетевые алгоритмы . Серия региональных конференций CBMS-NSF по прикладной математике. Том. 44. Общество промышленной и прикладной математики . стр. 34–38.
^ Сотрудники Ассоциации инженерных исследований (1950). «3-6 Счетчик r -триодов по модулю r ». Высокоскоростные вычислительные устройства . МакГроу-Хилл. стр. 22–23 . Проверено 27 августа 2008 г.
^ Сотрудники Ассоциации инженерных исследований (1950). «3-7 2 - триодный счетчик по модулю r ». Высокоскоростные вычислительные устройства . МакГроу-Хилл. стр. 23–25 . Проверено 27 августа 2008 г.
^ Сотрудники Ассоциации инженерных исследований (1950). «Экономия 6–7, достигнутая выбором системы счисления». Высокоскоростные вычислительные устройства . МакГроу-Хилл. стр. 84–87 . Проверено 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.

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

[2] Бентли, Джон; Седжвик, Боб (1 апреля 1998 г.). «Тройные деревья поиска» . Журнал доктора Добба . УБМ Тех . Проверено 28 июля 2013 г.

[3] Тарьян, Р.Э. (1983). «3.2.d - кучи». Структуры данных и сетевые алгоритмы . Серия региональных конференций CBMS-NSF по прикладной математике. Том. 44. Общество промышленной и прикладной математики . стр. 34–38.

[4] Сотрудники Ассоциации инженерных исследований (1950). «3-6 Счетчик r -триодов по модулю r ». Высокоскоростные вычислительные устройства . МакГроу-Хилл. стр. 22–23 . Проверено 27 августа 2008 г.

[5] Сотрудники Ассоциации инженерных исследований (1950). «3-7 2 - триодный счетчик по модулю r ». Высокоскоростные вычислительные устройства . МакГроу-Хилл. стр. 23–25 . Проверено 27 августа 2008 г.

[6] Сотрудники Ассоциации инженерных исследований (1950). «Экономия 6–7, достигнутая выбором системы счисления». Высокоскоростные вычислительные устройства . МакГроу-Хилл. стр. 84–87 . Проверено 27 августа 2008 г.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]