Это условие может быть также записано в виде
bm≥ 10n>bm-1.
Возьмем логарифмы этих трех чисел. Вспомнив, что lg 10 = 1, получим, что
m lg b≥n> (m — 1) lg b.
В свою очередь эти неравенства могут быть переписаны в виде
m ≥n/lg b> (m — 1); (6.3.3)
таким образом, m является первым целым числом не меньшим, чем n/lg b.
Отсюда делаем вывод, что, грубо говоря, m — новое количество знаков, может быть получено делением числа n на lg b.
Примеры. Пусть вновь n будет количеством знаков числа в десятичной системе. Для b = 2 мы имеем: lg 2 = 0,30103, таким образом, количество цифр в двоичной системе приблизительно равно 3,32 n. Когда b = 60, мы имеем: lg 60 = 1,778, отсюда количество знаков приблизительно равно 0,56 n, т. е. немного больше, чем половина количества знаков в десятичной системе.
Ясно, что короткими числами удобнее оперировать. Но, с другой стороны, числа при больших основаниях имеют ряд недостатков. Во-первых, нужно иметь названия и обозначения для b различных цифр, чего обычно нет для больших значений b. Например, в вавилонской шестидесятеричной системе считали единицы до 60, группируя их по десять, как показано на рис. 15.
Рис. 15.
Это означает в действительности, что эта система расщеплялась на подсистемы с десятеричной записью. Аналогичная ситуация существует в двадцатеричной системе народа майя. Здесь цифры до 20 считались пятерками, как показано на рис. 16.
Рис. 16.
Вторым и гораздо большим недостатком является трудность, возникающая при попытках вычислений с помощью обычных методов. Когда мы выполняем действие умножения, то пользуемся знанием наизусть таблицы умножения, т. е. знанием произведений всех десяти цифр. Эта таблица Пифагора, как ее называют во многих странах, вдалбливалась нам в течение первых школьных лет, и знаем мы ее почти автоматически. Это знание не столь тривиально, как мы склонны думать. Из средневековых арифметических манускриптов ясно видно, что умножение было на грани высшей математики, а деление больших чисел было в действительности редким искусством. Но можно привести и гораздо более поздние примеры.
Самюэль Пепис, известный благодаря своему дневнику, был в возрасте около тридцати лет и служил клерком канцелярии лорда-хранителя печати, когда летом 1662 года он решил, что он должен знать кое-что из математики, по крайней мере основы арифметики, чтобы самостоятельно проверять счета. Заметим, что он тогда уже получил степени бакалавра и магистра в Кембридже. В то время было довольно обычным, что хорошо образованный английский джентльмен совершенно не владеет повседневными расчетами; эти расчеты могли перепоручаться младшим счетоводам.
4 июля 1662 года Пепис записывает в своем дневнике: «Вскоре придет мистер Купер, помощник капитана на „Ройял Чарльз", у которого я собираюсь учиться математике, и сегодня мы начнем; он очень способный человек, я полагаю, что не найдется дела, которое способно полностью его удовлетворить. После часа занятий арифметикой (я пытался выучить таблицу умножения) мы расстались с ним до завтра».
Каждый день и рано утром и поздно вечером Пепис учил проклятую таблицу умножения, с трудом продвигаясь вперед при поддержке своего моряка-учителя. Например, 9 июля он записывает: «Встал в четыре часа утра и снова упорно учу таблицу умножения, которая для меня является главной трудностью арифметики». Так продолжалось несколько дней, пока 11 июля он смог записать: «Встал в четыре часа утра и упорно работал над таблицей умножения, которой я теперь почти овладел». Пепис хорошо использовал полученные с таким трудом знания во всех все более важных постах, на которые он назначался. Однако может показаться слишком быстрым его продвижение, когда вы узнаете, что он был избран членом знаменитой Британской академии наук — Королевского общества — спустя два с половиной года после того, как выучил таблицу умножения.
Мы привели эту историю, которая никоим образом не является уникальной, чтобы подчеркнуть: запоминание таблицы умножения в те дни не было обычным этапом математического знания. Таким образом, мы видим, что использование в нашей арифметике чисел с небольшим основанием дает ряд преимуществ, как механических, так и интеллектуальных. Например, когда основанием является число b = 3, то в таблице умножения
| 0 1 2 |________ 0 | 0 0 01 | 0 1 22 | 0 2 (1,1)3существует только единственное нетривиальное умножение, а именно: 2 • 2 = 4 = (1, 1)3.
Для b = 2 мы имеем совершенно тривиальную таблицу
| 0 1 |____ 0 | 0 01 | 0 1Система задач 6.3.
1. Доказать, что количество нетривиальных умножений цифр (получающееся отбрасыванием умножений на 0 и 1) в системе с основанием b равно 1/2 (b — 1) (b — 2).
2. Чему равна сумма всех элементов в таблице умножения? Проверьте для b = 10.
§ 4. Некоторые задачи, связанные с системами счисления
Обсудим несколько задач, связанных с системами счисления, которые имеют отношение к выбору оснований систем счисления, удобных для машинного счета. Предположим, что мы имеем дело с обычным настольным арифмометром, который работает при помощи сцепленных числовых колес, каждое из которых имеет 10 цифр: 0, 1, … 9. Если имеется n колес, то мы можем представить все числа вплоть до
N = 99…9 (n раз), (6.4.1)
как и в (6.3.1).
Предположим теперь, что в качестве основания мы взяли число b, отличное от 10, но продолжаем рассматривать числа до N. Тогда мы должны иметь m колес, где m — целое число, удовлетворяющее условиям (6.3.2) и (6.3.3). Как и в (6.3.4). число m является целым числом, равным числу n/lg b или следующим за ним. Так как каждое колесо несет b цифр, то количество цифр, записанных на колесах, приближенно равно
D = n b/lg b.
Можно теперь спросить: какое нужно выбрать число b, чтобы получить наименьшее количество чисел, записанных на колесах? Чтобы найти наименьшее значение числа D, в формуле (6.4.2) необходимо лишь исследовать функцию
f(b) = b/lg b (6.4.3)
для различных оснований b = 2, 3, 4… С помощью таблицы логарифмов получаем значения
b 2 3 4 5 6f(b) 6,64 6,29 6,64 7,15 7,71Последующие значения для f(b) еще больше; например, f(10) = 10, как уже отмечалось. Мы заключаем, что для таких арифмометров имеет место следующее утверждение.
Наименьшее общее число цифр на арифмометре достигается при b = 3.
Видно, что для 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 6g(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 секунд.
Предположим, что мы изменили наше основание на число