Системы счисления и их применение

§ 1. Деньги в конвертах и зерна на шахматной доске

Представьте себе, дорогой читатель, что вы банкир, занимающийся отмыванием грязных денег, и завтра ждете важного клиента, которому вы должны выдать круглую сумму, или не очень круглую, но заранее вам неизвестную сумму от 1 до 1 000 000 000 у.е. Чтобы не пачкать руки о грязные деньги, вы заранее дали указание своим кассирам заготовить некоторое количество конвертов с деньгами, на которых написаны содержащиеся в них суммы, и собираетесь просто отдать клиенту один или несколько конвертов, в которых и будет содержаться требуемая им сумма. Какое наименьшее количество конвертов необходимо иметь?

Конечно, можно просто заготовить конверты со всеми суммами от 1 до 1 000 000 000. Но где взять столько денег на конверты?

1. А какова будет в этом случае полная сумма во всех конвертах? Попробуйте оценить также массу бумаги, предполагая, что использованы не более чем сотенные купюры. ¹

Есть более рациональный подход к нашему делу. Надо положить в первый конверт 1 у.е., а в каждый следующий класть двое большую сумму, чем в предыдущий. Тогда, например, в 5-м конверте будет 16 у.е., в 10-м — 512 у.е., в 11-м — 1024 у.е., в 21 — 1024² = 1 048 576 у.е., в 31-м — 1024³ = 1 073 741 824 у.е., но он нам, очевидно, уже не понадобится, а вот 30-й с   у.е. может и пригодиться. В общем случае сумма в (n + 1)-м конверте будет равна произведению n двоек, это число принято обозначать 2ⁿ и называть n-й степенью двойки. Условимся считать, что 2⁰ = 1. Проведенные выше вычисления основывались на следующих свойствах операции возведения в степень:

Экспериментально легко проверить, что любое число можно представить единственным образом в виде суммы различных меньших степеней двойки, и поэтому наша задача почти решена. Например,

30 000 = 2¹⁴ + 2¹³ + 2¹² + 2¹⁰ + 2⁸ + 2⁵ + 2⁴.

Но для реального применения нужен алгоритм построения такого разложения. Далее будут приведены несколько разных алгоритмов, но вначале мы рассмотрим самый простой.
В сущности, это алгоритм выдачи сдачи клиенту, записанный некогда даже в инструкции для работников торговли, но очень редко ими выполняющийся. А он очень прост — сдачу надо выдавать, начиная с самых больших купюр. В нашем случае нужно найти конверт с наибольшей суммой денег, не превосходящей требуемую, то есть наибольшую степень двойки, не превосходящую требуемого количества денег.

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

Ниже мы докажем, что, имея набор конвертов с суммами в 1 у.е, 2 у.е., 4 у.е., ..., 2ⁿ у.е., любую сумму денег от 1 у.е. до (2^n + 1 – 1) у.е. можно выдать единственным способом. Также будет доказано, что, действуя по описанному алгоритму, мы всегда получим этот способ выдачи требуемой суммы.

Вначале рассмотрим пример работы алгоритма с числом 2ⁿ – 1. Ясно, что на первом шаге будет выбрано число 2^n–1, останется число 2ⁿ – 1 – 2^n – 1 = 2^n – 1 – 1, потом будет выбрано число 2^n – 2 и т.д., и в результате получится разложение

2ⁿ – 1 = 2^n – 1 + 2^n – 2 + ... + 2² + 2¹ + 2⁰.

Но оно не показалось бы очевидным, если, не зная заранее ответа, пришлось бы вычислять сумму

1 + 2 + 4 + 8 + ... + 2^n – 2 + 2^n – 1,

называемую суммой геометрической прогрессии со знаменателем 2. Ведь для этого пришлось бы выдумать какой-нибудь трюк наподобие следующего:

1 + 2 + 4 + 8 + ... + 2^n – 2 + 2^n – 1 = 2 – 1 + 2 + 4 + 8 + ... + 2^n – 2 + 2^n – 1 =
= 4 – 1 + 4 + 8 + ... + 2^n – 2 + 2^n – 1 = 8 – 1 + 8 + 16 + ... + 2^n – 2 + 2^n – 1 = ... =
= 2^n – 2 – 1 + 2^n – 2 + 2^n – 1 = 2^n–1 + 2^n – 1 = 2ⁿ – 1.

2.  Используя подобный трюк, вычислите произведение

Докажем теперь существование и единственность представления числа N в виде суммы меньших степеней двойки. Доказательство будем производить индукцией по N.

Для N = 1 утверждение очевидно.

Пусть оно верно для всех N < N₀. Пусть 2ⁿ — максимальная степень двойки, не превосходящая N, то есть 2ⁿ ≤ N₀ < 2^n + 1. Тогда, по предположению индукции, число N₀ – 2ⁿ ≤ 2ⁿ представимо в виде суммы степеней двойки, меньших N₀ – 2ⁿ < 2ⁿ. Следовательно, число N₀ тоже представимо в виде суммы меньших степеней двойки (достаточно к представлению числа N₀ – 2ⁿ добавить 2ⁿ). Кроме того, так как 1 + 2 + ... + 2^n – 1 = 2ⁿ – 1 < 2ⁿ, то не существует представления числа N₀, не использующего 2ⁿ.
Таким образом, доказана единственность такого представления.

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

Заметим еще, что, в отличие от первого варианта решения, полная сумма во всех конвертах менее чем в два раза превосходит верхнюю границу подлежащей выплате суммы.

Для краткой записи результата работы алгоритма над данным числом a можно вместо разложения

которое и записать-то в общем виде без использования трехэтажных обозначений затруднительно, использовать последовательность показателей степеней (n₁, ..., n_k) или, что еще удобнее (но не всегда короче), написать последовательность (a_m, ..., a₁) чисел 0 и 1, в которой a_i = 1, если число 2^i – 1 входит в указанное выше разложение, и a_i = 0 в противном случае. Тогда это разложение можно будет переписать в виде

a = a₁ + 2a₂ + 4a₃ + ... + 2^m – 1a_m.

Ясно, что приведенный выше алгоритм позволяет строить такое представление, причем оно определяется однозначно, если предполагать, что старший его разряд a_m ненулевой. Это представление и называется двоичной записью числа a.

Читатель увидит, что понятие двоичной записи очень похоже на понятие десятичной записи и в каком-то смысле даже проще.

Остался вопрос о минимальности найденной системы конвертов. В общем виде указанный выше прием предлагает для уплаты любой суммы от 1 до n использовать m конвертов с суммами 1, 2, 4, 8, ..., 2^m–1, где 2^m – 1 ≤ n < 2^m. Меньшего количества конвертов может не хватить, потому что с помощью k < m конвертов можно уплатить не более чем 2^k – 1 < 2^m – 1 ≤ n разных сумм, так как каждая сумма однозначно определяется ненулевым набором (a₁, ..., a_k), в котором каждое число a_i равно 1, если i-й конверт входит в эту сумму, и равно 0 в противном случае, а всего наборов длины k из нулей и единиц можно составить ровно 2^k.

3. Докажите последнее утверждение.

4.  Докажите, что если n = 2^m – 1, то минимальная система конвертов определяется однозначно, в противном случае — нет.

После упоминания десятичной системы сразу возникает идея, на первый взгляд, даже более простого решения задачи о конвертах. Надо просто заготовить конверты с суммами 1, 2, ..., 9, 10, 20, 30, ..., 90, 100, 200, 300, ..., 100 000 000, 200 000 000, ..., 900 000 000. Тогда для выплаты любой требуемой суммы не нужно искать ее двоичную запись, так как для выплаты, например, 123 456 789 у.е. нужно просто взять конверт с суммой 9, конверт с суммой 80, конверт с суммой 700 и т.д. Это действительно проще, но исключительно потому, что мы привыкли пользоваться десятичной системой и все расчеты ведутся с ее помощью. Если бы мы использовали в повседневной жизни только двоичную систему, то этот способ был бы сложнее, так как приходилось бы переводить данную сумму из двоичной системы в десятичную ². Поэтому простота десятичного способа решения задачи скорее мнимая.

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

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

5. Оцените приблизительно, во сколько миллионов тонн зерна обойдется магарадже его щедрость.

Из сказанного выше видно, что если бы на каждое поле шахматной доски не всегда класть столько зерен, сколько просил мудрец, а иногда вообще не класть, то можно получить таким образом любое число от 0 до 2⁶⁴ – 1. Поэтому, вероятно, таким образом можно представить любое число, которое может встретиться в каких-либо конкретных прикладных вычислениях.

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

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

6.  Пусть на каждой из n спиц находится по b костяшек (то есть счеты представляют числа в системе счисления с основанием b + 1) и поэтому они позволяют записать в этой системе любое число от 0 до N = (b + 1)ⁿ – 1 (число N характеризует «вместимость» счетов). Каким нужно выбрать b, чтобы суммарное количество костяшек на счетах («сложность» счетов) было минимальным при условии возможности указанного представления на счетах любого числа от 1 до N (то есть при заданной вместимости)?

Для прочитавших этот параграф ответ, конечно, очевиден. Для знающих логарифмы продолжение этой задачи: сравните сложности десятичных и двоичных счет одинаковой вместимости.

Приведенный выше алгоритм перевода из десятичной системы в двоичную вычислял цифры двоичной записи, начиная со старших цифр. Опишем теперь кратко возможно более удобный алгоритм, в котором цифры двоичной записи вычисляются, начиная с младших ³).

Очевидно, самая младшая цифра равна нулю, если число четное, и единице, если оно нечетное. Для нахождения остальных двоичных цифр надо от исходного числа отнять найденную младшую цифру, поделить разность пополам и к полученному числу применить описанный выше шаг алгоритма.

Например, у числа 300 последние две цифры нули, а для нахождения остальных цифр надо иметь дело с числом поэтому следующая цифра 1, и получаем промежуточный результат 37. Следующая далее цифра опять 1, и промежуточный результат 18, поэтому следующая цифра 0, а промежуточный результат 9, следующая цифра 1, а потом три нуля подряд, а старший разряд, как всегда, 1. В результате получается двоичная запись 1000101100.

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

§ 2. Взвешивание с помощью гирь и возведение в степень

Предлагаем читателю самому убедиться в том, что точно так же, как и в предыдущем разделе, можно доказать, что для отвешивания любого числа граммов песка — от 1 г до n г за одно взвешивание достаточно иметь гири 1 г, 2 г, 4 г, ..., 2^m г, где 2^m ≤ n < 2^m + 1, и меньшего числа гирь недостаточно, если песок лежит на одной чашке весов, а гири разрешается ставить на вторую чашку. На самом деле с математической точки зрения эта задача, известная со средневековых времен, ничем не отличается от рассмотренной выше задачи о конвертах с деньгами.

Часто новые и интересные задачи получаются, если в старой задаче наложить какие-нибудь естественные ограничения. Например, можно задать следующий вопрос: за какое наименьшее количество взвешиваний на чашечных весах можно отвесить килограмм сахарного песка, если имеется лишь одна однограммовая гирька?

На первый взгляд кажется, что единственный способ решения этой задачи — отвесить один грамм, положить в эту же чашку гирьку, отвесить в другой чашке два грамма, переложить гирьку в нее и т.д., добавляя по одному грамму, после тысячного взвешивания отмерить, наконец, килограмм.

Но есть и более быстрый способ. Нужно лишь заметить, что если мы научились отвешивать за n взвешиваний m г песка, то, сделав еще одно взвешивание, можно, даже не используя гирьки, отвесить еще m г и, ссыпав обе порции вместе, получить 2m г за 2n + 1 взвешивание. А если при этом взвешивании положить на одну из чашек гирьку, то за n + 1 взвешивание можно отмерить 2m ± 1 г песка.

Теперь воспользуемся двоичной записью числа 1000. Применяя любой из указанных выше алгоритмов, получаем равенство

1000 = 2⁹ + 2⁸ + 2⁷ + 2⁶ + 2⁵ + 2³.

Так как

2⁹ + 2⁸ + 2⁷ + 2⁶ + 2⁵ + 2³ = (((((2 + 1)2 + 1)2 + 1)2² + 1)2³,

то, последовательно отвешивая

1, 2 + 1 = 3, 23 + 1 = 7, 27 + 1 = 15, 215 + 1 = 31, 231 = 62,
262 + 1 = 125, 2125 = 250, 2250 = 500, получаем на десятом взвешивании 2500 =1000 г. Девяти взвешиваний не хватит:

за два взвешивания можно отмерить массу не более 3 = 2² – 1,

за три — не более 7 = 23 + 1 = 2³ – 1,

за четыре — не более 15 = 27 + 1 = 2⁴ – 1,

за девять — не более 511 = 2⁹ – 1.

Если нужно отмерить n г песка, то надо записать n в двоичном виде
a_m...a₁, где 2^m – 1 ≤ n < 2^m, a_m = 1, и воспользоваться формулой

n = a_m2^m – 1 + ... + a₂2 + a₁ =
= (...((2a_m + a_m – 1)2 + a_m – 2)...)2 + a₁,

последовательно отвешивая по b₁ = a_m,
b₂ = 2b₁ + a_m – 1, b₃ = 2b₂ + a_m – 2, ..., b_m = b_m – 12 +a₁ = n г.

В используемой формуле знающие читатели увидят так называемую схему Горнера. К ней мы еще вернемся в дальнейшем.

Идея, лежащая в основе этого метода взвешивания, стара, как сама математика. Ее применяли и древние египтяне, и древние индусы, но, конечно, не для взвешивания, а для умножения. Ведь алгоритм умножения столбиком был придуман не сразу, а до этого умножение сводилось к сложению. Например, чтобы умножить какое-нибудь число a на 1000, можно, используя только операции сложения, последовательно вычислить
a + a + a = 3a, 3a + 3a + a = 7a, 7a + 7a + a = 15a,
15a + 15a + a = 31a, 31a + 31a = 62a,
62a + 62a + a = 125a, 125a + 125a = 250a, 250a + 250a = 500a, 500a + 500a = 1000a.
Такой метод умножения дожил почти до нашего времени, он удобен при вычислениях на счетах. Сейчас он никому не нужен, так как все используют калькуляторы. Но как возвести на калькуляторе число a, например, в тысячную степень, если у него нет специальной операции возведения в произвольную степень? Умножать 999 раз не нужно, а можно применить тот же прием, последовательно вычисляя a³ = a²a, a⁷ = (a³)²a, a¹⁵ = (a⁷)²a,
a³¹ = (a¹⁵)²a, a⁶² = (a³¹)², a¹²⁵ = (a⁶²)²a, a²⁵⁰ = (a¹²⁵)², a⁵⁰⁰ = (a²⁵⁰)², a¹⁰⁰⁰ = (a⁵⁰⁰)².

Если вспомнить, что 1000 имеет двоичную запись 1111101000, то можно заметить, что если отбросить старший бит (всегда равный единице), то каждому следующему биту соответствует операция возведения в квадрат, если он нулевой, или, если он ненулевой, возведение в квадрат с последующим умножением на число a — основание степени (то есть делаются две операции). Кстати, число a не нужно каждый раз заново набирать на клавиатуре. Нужно в самом начале вычислений занести его в память калькулятора и, когда нужно, после нажатия кнопки для умножения просто вызывать его из памяти и потом нажимать кнопку «равно». Таким образом, возведение в квадрат требует двукратного нажатия кнопок, в возведение в квадрат и последующее умножение на основание степени — пятикратного. Для того, чтобы не запутаться в операциях, можно перед началом вычислений составить мнемоническое правило. Возведение в квадрат обозначим символом К, а возведение в квадрат и последующее умножение — символом КУ. Тогда, заменяя в двоичной записи единицы (кроме старшей) на КУ, а нули — на К, получим правило КУКУКУКУККУККК, или короче КУ ⁴ККУК³.

Посчитаем общее число операций умножения в рассмотренном вычислении. Число возведений в квадрат на единицу меньше длины двоичной записи показателя степени, а число умножений общего вида на единицу меньше суммы цифр двоичной записи.

Для любого n обозначим λ(n) уменьшенную на единицу длину двоичной записи числа n, а ν(n) — ее сумму цифр (другими словами, число единиц в ней). Тогда в общем случае число операций умножения, использованных в этом методе возведения в степень n, будет равно λ(n) + ν(n) – 1. Далее будет показано, что меньшим числом операций обойтись нельзя, если только не обновлять содержимое ячейки памяти.

Очевидно, что λ(n) + ν(n) – 1 ≤ 2λ(n).

Те, кто знают логарифмы, сообразят, что λ(n) = [log₂ n], где знак [x] означает целую часть числа x. Но можно вычислить обе возведенные функции, даже не упоминая о двоичной записи. Для этого надо воспользоваться следующими правилами:

ν(1) = 1, ν(2n) = ν(n), ν(2n + 1) = ν(n) + 1,
λ(1) = 0, λ(2n) = λ(2n + 1) = λ(n) + 1.

Однако для доказательства справедливости этих правил полезно, конечно, воспользоваться двоичной системой, после чего они становятся почти очевидными.

Докажем полезное и простое неравенство ν(n + 1) ≤ ν(n) + 1. Оно очевидно превращается в равенство, если n четно, так как тогда его двоичная запись заканчивается нулем. Если же эта двоичная запись заканчивается k единицами, перед которыми стоит нуль, то двоичная запись числа n + 1 заканчивается k нулями, перед которыми стоит единица (а старшие биты остаются без изменения, если они есть). Для того чтобы в этом убедиться, достаточно выполнить прибавление 1 к n в двоичной системе.
В обоих рассмотренных случаях ν(n + 1) ≤ ν(n) + 1.

Из доказанного неравенства следует, что

λ(n + 1) + ν(n + 1) ≤ λ(n) + ν(n) + 1.

Действительно, если 2^k – 1 < n + 1 < 2^k, то λ(n + 1) = k – 1 = λ(n), и из неравенства
ν(n + 1) ≤ ν(n) + 1 следует нужная нам оценка. Если же n + 1 = 2^k, то λ(n + 1) = k = λ(n) + 1,
ν(n + 1) = 1, ν(n) = k, откуда следует, что λ(n + 1) + ν(n + 1) = k + 1 ≤ 2k = λ(n) = ν(n) + 1.

Справедливо также равенство

λ(2n) + ν(2n) = λ(n) + ν(n) = 1,

которое сразу следует из равенства ν(2n) = ν(n), λ(2n) = λ(n) + 1.

Выше было показано, что число операций умножения, использованных для возведения в степень n на калькуляторе с одной ячейкой памяти, не больше чем λ(n) + ν(n) – 1.
При n = 1, 2 очевидно, что меньшим числом операций обойтись нельзя. Покажем, что и в общем случае это так, если только не обновлять содержимое ячейки памяти, то есть кроме возведения в квадрат всегда использовать только умножение на основание степени.

Допустим противное, а именно, что для вычисления указанным образом xⁿ при некотором n оказалось достаточно l < λ(n) + ν(n) – 1 операций. Выберем среди таких чисел n наименьшее число и обозначим его также n. Если последняя операция в рассматриваемом вычислении была возведение в квадрат, то n четно и для вычисления достаточно

операций, поэтому минимальным числом с рассматриваемым свойством не может быть n, что ведет к противоречию. Аналогично получается противоречие и в случае, когда последней операцией было умножение на x. Действительно, тогда, согласно доказанному выше неравенству, для вычисления x^n – 1 достаточно

l – 1 < λ(n) + ν(n) – 2 ≤ λ(n – 1) + ν(n – 1) – 1 операций.

Но если обновлять содержимое ячейки памяти, то указанный выше метод вычисления x¹⁰⁰⁰ можно улучшить. Для этого можно применить так называемый метод множителей. Идея этого метода заключается в следующем. Заметим, что если мы умеем возводить в степень n за l(n) операций и возводить в степень m за l(m) операций, то можно после того, как закончено вычисление xⁿ, занести его в ячейку памяти и далее вычислять x^mn = (xⁿ)^m за l(m) операций, используя тот же метод, что и для вычисления x^m. Тогда общее число операций будет равно l(nm) = l(n) + l(m).

Вычисляя x⁵ старым методом за λ(5) + ν(5) – 1 = 3 операции, с помощью последовательности x, x², x⁴ = (x²)², x⁵ = (x⁴)x и применяя два раза метод множителей, получаем, что l(125) = 3l(5) = 9. Выполняя еще три возведения в квадрат, получаем l(1000) = l(125) + 3 = 12. Старый же метод требовал λ(1000) + ν(1000) – 1 = 9 + 6 – 1 = 14 операций.

Читателю может показаться, что мы слишком много внимания уделили такому специальному и не слишком важному вопросу, как быстрое выполнение возведения в степень. Лет тридцать назад это замечание было бы справедливым. Но в середине 1970-х годов почти одновременно и независимо группой американских математиков (У. Диффи, М. Хеллман, Р. Ривест, А. Шамир, П. Адлеман) и группой английских криптографов (К. Кокс, М. Вильямсон, Д. Эллис) были открыты первые алгоритмы криптографии с открытым ключом ⁴. Благодаря этим алгоритмам теперь частные лица могут обмениваться секретной информацией по общедоступным каналам связи (например, по Интернету) без боязни, что их сообщения прочтут не только конкуренты, но и спецслужбы. Возникшее направление в криптографии быстро превратилось в популярную область математических исследований, которой уже посвящены многочисленные журналы и книги (см. например: Бауэр Ф. Расшифрованные секреты. — М.: Мир, 2007). И во многих самых распространенных алгоритмах важную роль играет операция возведения в степень.

§ 3. Аддитивные цепочки и фляги с молоком

Назовем аддитивной цепочкой любую начинающуюся с 1 последовательность натуральных чисел a₀ = 1, a₁, ..., a_m, в которой каждое число является суммой каких-то двух предыдущих чисел (или удвоением какого-то предыдущего числа). Обозначим l(n) наименьшую длину аддитивной цепочки, заканчивающейся числом n (длиной цепочки a₀ = 1, a₁, ..., a_m назовем число m).

Например,

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 —аддитивная цепочка, 1, 2, 3, 5, 7, 14 — минимальная цепочка для 14, то есть l(14) = 5. Аддитивные цепочки можно изображать в виде ориентированного графа, в котором в вершину a_i идут ребра от вершин a_j, a_k, если a_i = a_j + a_k (в случае, если такое представление неоднозначно, выбираем любое из них и рисуем только два ребра). Если из какой-то вершины выходит только одно ребро, то для краткости можно «склеить» эту вершину с той вершиной, в которую ведет это ребро. Граф для предыдущего примера показан на рисунке 1.

Рис. 1

Можно считать, что все числа в цепочке разные, так как этого легко достичь просто удаляя из нее повторяющиеся числа, и что эти числа расположены в цепочке в порядке возрастания.

Очевидно, что наименьшее число умножений, необходимых для возведения в n-ю степень, равно l(n).

Приведенный выше метод построения аддитивных цепочек называется двоичным (или бинарным). Фактически этим методом было доказано, что справедливо неравенство
l(n) ≤ l(n) + n(n) – 1. Методом множителей легко доказать неравенство l(nm) ≤ l(n) + l(m).

7.  Докажите нижнюю оценку: l(n) ≥ λ(n).

Из этой оценки следует, что l(2ⁿ) = n.

Известно, что бинарный метод был по существу известен древним индусам, потом был переоткрыт арабскими математиками, задача о точном вычислении функции l(n) появилась в одном французском журнале в 1894 г., потом заново была переоткрыта в 1930-е годы и неоднократно переоткрывалась в дальнейшем, но до сих пор в общем случае не решена.

По существу, наилучшая из известных общих верхних оценок была доказана в 1930-е годы А. Брауэром и имеет вид:

где C > 0 — некоторая константа.

Не каждую аддитивную цепочку можно вычислить на калькуляторе с одной ячейкой памяти, не используя для запоминания промежуточных результатов собственную голову (фактически, такие калькуляторы имеют две ячейки памяти, одна из них содержит число, изображаемое в данный момент на дисплее). Укажем, как можно определить необходимое число ячеек памяти для вычисления данной аддитивной цепочки. Для этого введем понятия ширины (а заодно и глубины) аддитивной цепочки.

Пусть дана произвольная цепочка a₀ = 1, a₁, ..., a_L = n. Сопоставим каждому ее элементу два числа. Первое из них назовем глубиной элемента, а второе — номером ячейки, хранящей это число. Для элемента a₀ первое число положим равным нулю, а второе — единице. Будем далее последовательно вычислять эти числа для элементов цепочки. Пусть они уже вычислены для всех элементов от a₀ до a_k. Составим список номеров ячеек, содержащих те элементы цепочки, которые еще могут быть использованы для вычисления последующих элементов. Найдем наименьшее число, не входящее в этот список, и присвоим его элементу a_k + 1 в качестве номера ячейки (возможно, она использовалась ранее, но теперь уже свободна). Пусть a_k + 1 = a_i + a_j, i, j ≤ k. Если D(a_i), D(a_j) — значения глубины элементов a_j, a_i, то положим D(a_k + 1) на единицу большим максимального из чисел D(a_i), D(a_j). Шириной S цепочки назовем число использованных ячеек (равное наибольшему из использованных номеров ячеек). Глубиной D цепочки назовем глубину ее последнего элемента.

8. Докажите, что и D ≥ λ(n). Докажите, что бинарный метод можно модифицировать так, чтобы длина цепочки не изменилась, а глубина стала бы равна λ(n).

Если цепочка имеет ширину S, то ее можно представить в виде вычисления на калькуляторе с S – 1 ячейками памяти (кроме основной, содержащей число, изображаемое в данный момент на дисплее) или в виде компьютерной программы, использующей S ячеек памяти.

Можно еще представить эту цепочку в виде способа, как налить в данную флягу n литров молока из цистерны, если первоначально в ней был один литр и кроме нее имеется S таких же пустых фляг и весы, способные только сравнивать веса двух фляг между собой. Для этого сопоставим S фляг ячейкам памяти рассматриваемой цепочки, а одну флягу оставим запасной. Тогда любую операцию с ячейками памяти вида x_k = x_i + x_j можно выполнить, выливая в случае необходимости k-ю флягу в цистерну, потом наливая запасную флягу до уровня i-й фляги и сливая ее содержимое в k-ю флягу, если k ≠ i, и делая аналогичную процедуру для индекса j.

Естественно, что аналогичным образом на языке «переливаний» можно представить и программу с командами, использующими не только сложение, но и вычитание x_k = x_i – x_j.
Поэтому понятие аддитивной цепочки можно обобщить, разрешив использовать вычитание. Для вычисления степеней такие цепочки также можно выполнять на калькуляторе, если кроме умножения использовать и деление. Известно, что в среднем это не дает существенной выгоды, но в некоторых случаях число используемых операций уменьшается.

Например, вычислить x¹⁰⁰⁰ можно с помощью следующей цепочки: 1, 2, 4, 8, 16, 32, 31, 62, 124, 134, 125, 250, 500, 1000.

§ 4. Краткая история двоичной системы

Некоторые идеи, лежащие в основе двоичной системы, по существу были известны в Древнем Китае. Об этом свидетельствует классическая книга «И-цин» («Книга Перемен»), о которой речь пойдет позже.

Идея двоичной системы была известна и древним индусам.

В Европе двоичная система, видимо, появилась уже в новое время. Об этом свидетельствует система объемных мер, применяемая английскими виноторговцами:

два джилла = полуштоф,
два полуштофа = пинта,
две пинты = кварта,
две кварты = потл,
два потла = галлон,
два галлона = пек,
два пека = полубушель,
два полубушеля = бушель,
два бушеля = килдеркин,
два килдеркина = баррель,
два барреля = хогсхед,
два хогсхеда = пайп, два пайпа = тан.

Читатели исторических романов, видимо, знакомы с пинтами и квартами. Частично эта система дожила и до нашего времени (нефть и бензин до сих пор меряются галлонами и баррелями).

И в английских мерах веса можно увидеть двоичный принцип. Так, фунт (обычный, не тройский) содержит 16 унций, а унция — 16 дрэмов. Тройский фунт содержит 12 тройских унций. В английских аптекарских мерах веса, однако, унция содержит восемь дрэмов.

Пропагандистом двоичной системы был знаменитый Г.В. Лейбниц (получивший, кстати, от Петра I звание тайного советника). Он отмечал особую простоту алгоритмов арифметических действий в двоичной арифметике в сравнении с другими системами и придавал ей определенный философский смысл. Говорят, что по его предложению была выбита медаль с надписью «Для того, чтобы вывести из ничтожества все, достаточно единицы». Известный современный математик Т. Данциг о нынешнем положении дел сказал: «Увы! То, что некогда возвышалось как монумент монотеизму, очутилось в чреве компьютера». Причина такой метаморфозы не только уникальная простота таблицы умножения в двоичной системе, но и особенности физических принципов, на основе которых работает элементарная база современных ЭВМ (впрочем, за последние 40 лет она неоднократно менялась, но двоичная система и булева алгебра по-прежнему вне конкуренции).

§ 5. Почему двоичная система удобна?

Главное достижение двоичной системы — простота алгоритмов сложения, вычитания, умножения и деления. Таблица умножения в ней совсем не требует ничего запоминать: ведь любое число, умноженное на нуль, равно нулю, а умножение на единицу равно самому себе. И при этом никаких переносов в следующие разряды, а они есть даже в троичной системе. Таблица деления сводится к двум равенствам благодаря чему деление столбиком многозначных двоичных чисел делается гораздо проще, чем в десятичной системе, и по существу сводится к многократному вычитанию.

Таблица сложения, как ни странно, чуть сложнее, потому что 1 + 1 = 10 и возникает перенос в следующий разряд. В общем виде операцию сложения однобитовых чисел можно записать в виде x + y = 2w + v, где w, v — биты результата. Внимательно посмотрев на таблицу сложения, можно заметить, что бит переноса w — это просто произведение xy, потому что он равен единице лишь когда x и y равны нулю. А вот бит v равен x + y, за исключением случая x = y = 1, когда он равен не 2, а 0. Операцию, с помощью которой по битам x, y вычисляют бит v, называют по-разному. Мы будем использовать для нее название «сложение по модулю 2» и символ . Таким образом, сложение битов выполняется фактически не одной, а двумя операциями.

Если отвлекаться от технических деталей, то именно с помощью этих операций и выполняются все операции в компьютере.

Для выполнения сложения однобитовых чисел делают обычно даже специальный логический элемент с двумя входами x, y и двумя выходами w, v, как бы составленный из элемента умножения (его часто называют конъюнкцией, чтобы не путать с умножением многозначных чисел) и элемента сложения по модулю 2. Этот элемент часто называют полусумматором.

§ 6. Ханойская башня, код Грея и двоичный n-мерный куб

Далее мы рассмотрим несколько интересных задач, в решении которых помогает знание двоичной системы. Начнем мы с задач, в которых используется только одна, самая простая из лежащих в ее основе идей — идея чисто комбинаторная и почти не связанная с арифметикой.

Первая из них — это «Ханойская башня». Головоломку под таким названием придумал французский математик Эдуард Люка в XIX веке.

На столбик нанизаны в порядке убывания размеров n круглых дисков с дырками в центре в виде детской игрушечной пирамидки. Требуется перенести эту пирамидку на другой столбик, пользуясь третьим вспомогательным столбиком (рис. 2). За один ход разрешается переносить со столбика на столбик один диск, но класть больший диск на меньший нельзя. Спрашивается, за какое наименьшее количество ходов это можно сделать. Ответом к этой задаче служит уже известное нам «индийское число» 2ⁿ – 1. Люка в своей книге приводит якобы известную легенду о том, что монахи в одном из монастырей Ханоя занимаются перенесением на другой столбик пирамидки, состоящей из 64 дисков. Когда они закончат работу, кончится жизнь Брахмы ⁵. Видно, ждать придется долго.

Рис. 2

Решение этой головоломки сильно облегчается, если знать, что такое код Грея. Кодом Грея порядка n называется любая циклическая последовательность всех наборов из нулей и единиц длины n, в которой два соседних набора отличаются ровно в одной компоненте. Примером кода Грея порядка 3 является последовательность трехразрядных наборов 000, 001, 011, 010, 110, 111, 101, 100.

9.  Докажите, что длина кода Грея порядка n равна 2ⁿ.

Если занумеровать компоненты каждого набора справа налево (при этом последняя, то есть самая правая компонента получит номер 1) и начинать код Грея с нулевого набора, то его можно записать короче, если вместо очередного набора писать только номер компоненты, в которой он отличается от предшествующего набора. Например, указанный выше код Грея можно коротко записать в виде последовательности семи чисел: 1, 2, 1, 3, 1, 2, 1. В общем случае длина подобной последовательности равна 2ⁿ – 1. Указанная краткая запись позволяет догадаться, как можно строить коды Грея дальше. Например, код Грея порядка 4 можно задать последовательностью 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1. Она получается, если мы повторим два раза последовательность, определяющую код Грея порядка 3, разделив оба экземпляра этой последовательности числом 4. Далее поступаем аналогично, то есть последовательность длины 2ⁿ – 1, определяющую код Грея порядка n, дублируем, разделив оба дубля числом n + 1. Полученная последовательность длины 2(2ⁿ – 1) + 1 = 2^n + 1 – 1 будет определять код Грея порядка n + 1.

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

А РОЗА УПАЛА НА ЛАПУ АЗОРА
АХ, У ЛЕШЕГО НА НОГЕ ШЕЛУХА
Я ИДУ С МЕЧЕМ, СУДИЯ (Г. Державин)
У ДЕВЫ В УМЕ РОЕТСЯ: «А Я-С ТЕОРЕМУ ВЫВЕДУ...» (Б. Левин)

Нам понадобится это свойство кода Грея порядка n + 1, а также то обстоятельство, что все числа этой последовательности, кроме среднего, не больше n. Это означает, что если с ее помощью мы начнем выписывать последовательность наборов длины n + 1, начиная с нулевого, то первые 2ⁿ – 1 наборов будут начинаться с нуля, так как (n + 1)-я компонента никогда в них не будет меняться. Остальные же компоненты будут образовывать наборы длины n, и они будут чередоваться в том же порядке, что и в коде Грея порядка n, поэтому получится некоторая перестановка всех 2ⁿ наборов длины n + 1, начинающихся с нуля. Потом в ее последнем наборе этот нуль будет заменен на единицу (это определяется тем, что в середине последовательности стоит число n + 1), далее эта единица меняться не будет, а будет меняться в каждом очередном наборе длины n + 1 только одна из последних n компонент, и эти компоненты образуют код Грея порядка n, выписанный в обратном порядке, и закончится он нулевым набором. Сама же построенная при этом последовательность наборов длины n + 1 будет образовывать перестановку всех наборов длины n + 1, начинающихся с единицы, а ее последним набором будет набор 10...0. Таким образом, построенная последовательность состоит из 2ⁿ различных наборов и может быть превращена в циклическую, то есть является кодом Грея порядка n + 1.

Код Грея можно наглядно изобразить на n-мерном двоичном кубе. Сам этот куб служит для наглядного представления множества всех наборов длины n из нулей и единиц. Наборы изображаются точками и называются вершинами куба. Два набора, отличающиеся только в одной компоненте, называются соседними и образуют ребро куба. Номер этой компоненты называется направлением ребра. Куб можно нарисовать на плоскости так, что все ребра будут изображены отрезками, соединяющими их вершины, причем ребра одного направления будут изображены равными и параллельными отрезками (поэтому такие ребра называются также параллельными). Например, четырехмерный куб можно изобразить на плоскости так, как показано на рисунке 3.

Рис. 3

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

Для того чтобы изобразить код Грея на приведенном на рисунке 3 изображении n-мерного куба, рядом с вершинами следует написать их имена — соответствующие им наборы из нулей и единиц. Сделать это можно, например, таким образом. Самой нижней вершине сопоставим набор из одних нулей. Ребрам сопоставим номера их направлений, — например, направлению самого правого ребра, выходящего из «нулевой» вершины, сопоставим номер 1 и т.д., а направлению самого левого такого ребра — номер n. Далее сопоставляем оставшимся вершинам куба имена с помощью следующего алгоритма. Если какой-то вершине имя уже присвоено и, поднимаясь из нее вверх по какому-нибудь ребру, скажем направления k, попадаем в новую, пока безымянную вершину, то ей присваиваем имя, которое уже получается из имени прежней вершины заменой k-й компоненты (которая была нулем) на противоположную (то есть единицу). Если же мы попали в вершину, имя которой уже было присвоено ранее, то можно ничего не делать, так как если мы попробуем все же сопоставить ей имя согласно указанному правилу, то оно совпадет с уже присвоенным именем. Очевидно, самой верхней вершине будет присвоен набор из одних единиц. Результат работы описанного алгоритма для четырехмерного куба показан на рисунке 4.

Читателю предоставляется возможность самому решить головоломку Люка и обнаружить ее связь с кодом Грея, а мы займемся другим вопросом.

Бросается в глаза на изображениях многомерного куба, что все вершины, имена которых содержат заданное число единиц, скажем k, лежат на одной прямой (рис. 5). Говорят, что эти вершины лежат на k-м слое куба. Очевидно, нулевой слой состоит из одной вершины — «нулевой», а n-й слой состоит только из «единичной» вершины.

Рис. 4

Рис. 5

10. Сколько различных «возрастающих» путей ведут из «нулевой» вершины в данную вершину k-го слоя?

Ответ:k(k – 1)(k – 2)...22. Это число называют «k-факториал» и кратко обозначают k!.

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

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

Поэтому множество всех возрастающих путей от нулевой вершины до единичной, проходящих при этом через заданную вершину k-го слоя, равно k!(n – k)!. Но всего возрастающих путей от нулевой вершины до единичной n!, поэтому число вершин в k-м слое равно Это число называется k-м биномиальным коэффициентом и обозначается кратко Далее оно нам понадобится.

На этом мы заканчиваем рассказ о n-мерном кубе и возвращаемся в заключение опять к коду Грея. Очевидно, что в нем несоседние вершины могут быть соседними на кубе, то есть соединяться в нем ребром. В некоторых приложениях, как теоретических, так и практических, представляет интерес построение цепи (или цикла) в n-мерном кубе, в которой несоседние вершины никогда не являются соседними в этом кубе. Такая цепь максимальной возможной длины называется «змеёй в ящике». Какова ее длина, до сих пор неизвестно. Наилучшие известные ей оценки принадлежат новосибирским математикам А.А. Евдокимову и А.Д. Коршунову.

Другой задачей, связанной с кодом Грея, но более простой, является его недвоичное обобщение. Например, как построить циклическую последовательность всех трехзначных десятичных чисел от 000 до 999, в которой каждые два соседних числа были бы соседними еще и в том смысле, что отличались бы ровно в одном разряде и ровно на единицу? Несколько проще построить такую последовательность, если считать цифры 0 и 9 также соседними, хотя разность между ними и не равна 1. Еще проще построить нециклическую последовательность с теми же свойствами.

Эта задача имеет приложение к алгоритму быстрейшего вскрытия кодового замка на дипломате, поэтому мы не приводим ее решения.

Заметим, что этим методом можно вскрыть, конечно, дипломат не только с десятичным, но и с любым k-ичным кодовым замком. Однако при нечетном k аналога циклического кода Грея не существует, а существует только «цепной» код Грея. Читателю предоставляется возможность самому это проверить.

¹ Шрифтом выделены тексты задач для самостоятельного решения.
² Иногда это приходится делать и в реальной жизни. Различные алгоритмы такого перевода будут изложены далее.
³ Кстати, кассиры в магазинах и на рынках предпочитают выдавать сдачу начиная с мелких купюр, вопреки инструкции. Причина понятная — надеются, что покупатель, получив сдачу, уйдет, забыв взять крупные.
⁴ Англичане сделали это раньше, но им, как сотрудникам секретной криптографической службы, было запрещено публиковать свои результаты в открытой печати.
⁵ Приблизительный западный аналог — это конец света, но на Востоке считают, что после этого рождается новый Брахма и всё циклически повторяется сначала, от Золотого века до нашей Кали-Юги, которой и заканчивается цикл.
⁶ Граф — это произвольное множество вершин, некоторые из которых соединены ребрами.
⁷ В честь ирландского математика, механика, физика и астронома У.Р. Гамильтона, подсказавшего одному книготорговцу идею головоломки — как обойти по ребрам все вершины правильного многогранника (например, додекаэдра) и вернуться в исходную вершину. Полученные от книготорговца десять фунтов были, вероятно, единственным гонораром знаменитого ученого за многочисленные научные труды, если не считать оклада профессора Дублинского университета.

Гашков С.