Приглашение в теорию чисел

При основании 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]. К тому времени, когда появилось много различных типов компьютеров, возникла задача сделать устройство ЭВМ как можно более компактным и эффективным. Это привело к тщательному изучению систем счисления с целью нахождения более подходящей системы. По ряду причин, некоторые из которых мы обсудили в предыдущем параграфе, двоичная система была признана предпочтительной. Единственным ее недостатком явилось то, что для большинства из нас требуются немалые усилия для того, чтобы чувствовать себя в ней «как дома», так как мы были воспитаны в других традициях. Следовательно, поскольку числа, которые должны вводиться в компьютеры, обычно записаны в десятичной системе, то требуется начальное устройство, переводящее их в двоичную систему, а ответы в конце концов должны быть выражены в десятичной системе, как уступка менее математически подготовленным членам общества.

Разумеется, двоичная система, используемая в ЭВМ, является той же самой системой, которую мы обсуждали в предыдущем параграфе, однако используемая терминология носит более технический оттенок. Двоичные цифры 0, 1 называются битами, что является сокращением английского выражения Binary digiTs (двоичные цифры). Так как существуют лишь две возможности: 0 и 1 в каждой позиции, то часто говорят об элементе с двумя состояниями.

Если следовать общему правилу, изложенному в § 2 этой главы, то представление данного числа в двоичной системе довольно просто. Например, возьмем N = 1971. Повторное деление на b = 2 дает

1971 = 985 • 2 + 1,

985 = 492 • 2 + 1,

492 = 246 • 2 + 0,

246 = 123 • 2 + 0,

123 = 61 • 2 + 1,

61 = 30 • 2 + 1,

30 = 15 • 2 + 0,

15 = 7 • 2 + 1,

7 = 3 • 2 + 1,

3 = 1 • 2 + 1,

1 = 0 • 2 + 1,

Следовательно,

1971₁₀ = (1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1)₂.

Ранее мы отмечали, что в двоичной системе числа имеют более длинные выражения, следовательно, становится труднее с первого взгляда оценить величину числа. По этой причине в языке ЭВМ часто используется восьмеричная система счисления (с основанием 8). Это является лишь незначительным изменением двоичной системы, которое получается разбиением бит в числе на группы по три. Это можно представить себе как систему с основанием

b = 8 = 2³.

Коэффициентами при этом являются восемь чисел

0 = 000, 4 = 100, 1 = 001, 5 = 101, 2 = 010, 6 = 110, 3 = 011, 7 = 111.

В качестве иллюстрации возьмем число 1971 из рассмотренного выше примера; в восьмеричной системе оно представляется как

1971 = 011, 110, 110, 011 = (3, 6, 6, 3)₈.

Таким образом, этот способ записи незначительно отличается от предыдущего. В действительности, такое деление на группы нам хорошо знакомо по обычным десятичным числам: при записи и произнесении большого числа мы обычно делим его цифры на группы по три, например,

N = 89 747 321 924.

Таким образом, можно сказать, что это является представлением нашего числа при основании b = 1000= 10³.

В компьютерах иногда используются и другие представления чисел. Предположим, что мы хотим записать десятичное число, скажем, N = 2947, в ЭВМ, работающей в двоичной системе. Тогда, вместо того чтобы полностью менять N на двоичное число, можно было бы изменить лишь цифры этого числа

2 = 0010,

9 = 1001,

4 = 0100,

7 = 0111

и, таким образом,

N = 0010, 1001, 0100, 0111.

Такие числа известны как кодированные десятичные числа. Этот метод иногда называется «системой 8421», так как эти десятичные цифры представляются в виде сумм двоичных единиц

0 = 0000, 1 = 0001, 2 = 0010,

2² = 4 = 0100, 2³ = 8 = 1000.

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

10

При игре в «Ним» раскладывается некоторое количество камешков в несколько кучек. Двое играющих по очереди берут камешки из кучек, при ходе можно брать произвольное количество камней, но только из одной кучки. Выигрывает игрок, взявший последний камень. (Прим. перев.)