Приглашение в теорию чисел
Шрифт:
g(b) = (b — 1)/lg b (6.4.5)
для различных значений числа b = 2, 3… Значение функции g(b) для небольших значений числа b даны в таблице
Для больших значений числа b функция продолжает возрастать, поэтому мы заключаем, что необходимое количество косточек на счетах будет минимально при b = 2.
Можно
Посмотрим, какое время потребуется, чтобы уложить эти спички на места. Имея в виду какое-нибудь расположение, предположим, что потребуется одна секунда, чтобы уложить одну спичку. Тогда общее время, требуемое для того, чтобы уложить все спички, будет в среднем составлять приблизительно 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] . К тому времени, когда появилось много различных типов компьютеров, возникла задача сделать устройство ЭВМ как можно более компактным и эффективным. Это привело к тщательному изучению систем счисления с целью нахождения более подходящей системы. По ряду причин, некоторые из которых мы обсудили в предыдущем параграфе, двоичная система была признана предпочтительной. Единственным ее недостатком явилось то, что для большинства из нас требуются немалые усилия для того, чтобы чувствовать себя в ней «как дома», так как мы были воспитаны в других традициях. Следовательно, поскольку числа, которые должны вводиться в компьютеры, обычно записаны в десятичной системе, то требуется начальное устройство, переводящее их в двоичную систему, а ответы в конце концов должны быть выражены
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,
Следовательно,
197110 = (1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1)2.
Ранее мы отмечали, что в двоичной системе числа имеют более длинные выражения, следовательно, становится труднее с первого взгляда оценить величину числа. По этой причине в языке ЭВМ часто используется восьмеричная система счисления (с основанием 8). Это является лишь незначительным изменением двоичной системы, которое получается разбиением бит в числе на группы по три. Это можно представить себе как систему с основанием
b = 8 = 23.
Коэффициентами при этом являются восемь чисел
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)8.
Таким образом, этот способ записи незначительно отличается от предыдущего. В действительности, такое деление на группы нам хорошо знакомо по обычным десятичным числам: при записи и произнесении большого числа мы обычно делим его цифры на группы по три, например,
N = 89 747 321 924.
Таким образом, можно сказать, что это является представлением нашего числа при основании b = 1000= 103.
В компьютерах иногда используются и другие представления чисел. Предположим, что мы хотим записать десятичное число, скажем, N = 2947, в ЭВМ, работающей в двоичной системе. Тогда, вместо того чтобы полностью менять N на двоичное число, можно было бы изменить лишь цифры этого числа
2 = 0010,
9 = 1001,
4 = 0100,
7 = 0111
и, таким образом,
N = 0010, 1001, 0100, 0111.
Такие числа известны как кодированные десятичные числа. Этот метод иногда называется «системой 8421», так как эти десятичные цифры представляются в виде сумм двоичных единиц
0 = 0000, 1 = 0001, 2 = 0010,
22 = 4 = 0100, 23 = 8 = 1000.
Такие кодированные десятичные числа неудобны для всех видов вычислений, но не всегда целью ЭВМ являются вычисления. Тем же образом, любая буква алфавита или любой другой символ могут быть приписаны какому-нибудь двоичному числу. Это означает, что любое слово или предложение можно запоминать как двоичное число. Таким образом, если бы мы были соответствующим образом натренированы и имели бы дело со столь же подготовленной аудиторией, то могли бы общаться лишь с помощью бит.