Видно, что для b = 2 и b = 4 общее число цифр не на много больше; в этом смысле маленькие основания имеют преимущество.
Рассмотрим небольшое изменение этой задачи. Обычные счеты того типа, который иногда используется для обучения детей счету, имеют несколько металлических спиц с девятью[9] подвижными косточками на каждой из них, чтобы отмечать цифры чисел. С таким же успехом можно провести параллельные прямые на листе бумаги и отмечать цифры соответствующим количеством спичек, или же подобно древним начертить эти прямые на песке и отмечать цифры камешками.
Но вернемся к счетам. Если имеется n спиц и на каждой по 9 косточек, то можно представить вновь все целые числа с п знаками вплоть до числа N, записанного в (6.4.1). Теперь зададим следующий вопрос: можно ли, взяв другое основание b, сделать счеты более компактными, т. е. обойтись меньшим количеством косточек?
При основании b количество косточек на каждой спице будет b — 1. Как и прежде, для того чтобы счеты имели ту же вместимость N, количество знаков или спиц должно определяться соотношением (6.3.4). Это дает значение
E = n/lg b (b — 1) (6.4.4)
в качестве приближения для общего количества косточек. Чтобы найти, когда это число принимает наименьшее возможное значение, мы должны исследовать функцию
g(b) = (b — 1)/lg b (6.4.5)
для различных значений числа b = 2, 3… Значение функции g(b) для небольших значений числа b даны в таблице
b 2 3 4 5 6
g(b) 3,32 4,19 4,98 5,72 6,43
Для больших значений числа b функция продолжает возрастать, поэтому мы заключаем, что необходимое количество косточек на счетах будет минимально при b = 2.
Можно интерпретировать этот результат с другой точки зрения. Предположим, что мы отметили цифры нашего числа, используя спички или камешки, расположенные на прямых линиях. В десятичной системе будет от 0 до 9 отметок на каждой прямой. Это дает в среднем по 4,5 спички на каждой прямой для наугад взятых чисел; следовательно, числа с n знаками потребуют в среднем 4,5 n спичек, когда они укладываются произвольно.
Посмотрим, какое время потребуется, чтобы уложить эти спички на места. Имея в виду какое-нибудь расположение, предположим, что потребуется одна секунда, чтобы уложить одну спичку. Тогда общее время, требуемое для того, чтобы уложить все спички, будет в среднем составлять приблизительно 4,5 n секунд.
Предположим, что мы изменили наше основание на число b и допустим ту же самую вместимость для представления чисел. В таком случае на каждой прямой будет от 0 до b — 1 спичек, следовательно, в среднем 1/2 (b — 1) из всего количества спичек. Как мы упоминали несколько раз, мы будем иметь приблизительно n/lg b прямых. Отсюда делаем вывод, что среднее время, требуемое для представления числа с n знаками, составляет примерно
n/lg n 1/2 • (b — 1) = 1/2 E
секунд, здесь Е есть выражение из (6.4.4). Так как это время было минимальным для b = 2, мы также можем сделать вывод:
среднее время, необходимое для установления числа с помощью спичек на прямых, минимально для b = 2.
Система задач 6.4.
1. Постройте графики функций y = f(b) из (6.4.3) и у = g(b) из (6.4.5) для b > 1. Если вы уже знакомы с дифференциальным исчислением, используйте его для определения формы кривых.
§ 5. Компьютеры и их системы счисления
До появления электронных вычислительных машин всюду при вычислениях безраздельно господствовала десятичная система. Интерес к другим системам носил либо исторический, либо познавательный характер. Существовало лишь несколько отдельных задач, которые наиболее удачно формулировались с использованием двоичной или троичной систем счисления. Одним из излюбленных примеров в книгах по теории чисел является игра «Ним»[10]. К тому времени, когда появилось много различных типов компьютеров, возникла задача сделать устройство ЭВМ как можно более компактным и эффективным. Это привело к тщательному изучению систем счисления с целью нахождения более подходящей системы. По ряду причин, некоторые из которых мы обсудили в предыдущем параграфе, двоичная система была признана предпочтительной. Единственным ее недостатком явилось то, что для большинства из нас требуются немалые усилия для того, чтобы чувствовать себя в ней «как дома», так как мы были воспитаны в других традициях. Следовательно, поскольку числа, которые должны вводиться в компьютеры, обычно записаны в десятичной системе, то требуется начальное устройство, переводящее их в двоичную систему, а ответы в конце концов должны быть выражены в десятичной системе, как уступка менее математически подготовленным членам общества.