Бизенц Торра - Том 15. От абака к цифровой революции. Алгоритмы и вычисления

• Название: Том 15. От абака к цифровой революции. Алгоритмы и вычисления
• Автор: Бизенц Торра
• Издательство: «Де Агостини»
• Жанр: Математика
• Год: 2014
• ISBN: 978-5-9774-0710-6

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

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

---

Египетская система счисления была аддитивной, в отличие от нашей системы счисления, которая, подобно вавилонской, является позиционной. В аддитивной системе счисления, например, число 3204 представляется в виде 1000 + 1000 + 1000 + 100 + 100 + 1 + 1 + 1 + 1. В виде египетских иероглифов оно записывается так:

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

Рассмотрим, как выполнялось умножение, на примере чисел 17 и 53. Нужно взять пару чисел 1 и 53 и удвоить их. Результатом удвоения будут числа 2 и 106. Повторив эту операцию, получим 4 и 212. Нужно удваивать числа до тех пор, пока первое из них не превысит 17. После этого процесс прекращается, а результат, полученный на последнем шаге, игнорируется. Результатом этих действий в нашем примере будут следующие пары чисел.

Теперь нужно определить, как можно получить 17 путем сложения чисел из первого столбца. Единственный возможный способ получить 17 — сложить 1 и 16. Следовательно, для получения результата умножения нужно сложить значения, записанные справа от 1 и 16, то есть 53 и 848. Их сумма равна 901. Таким образом, результат умножения 17 на 53 равен 901.

Можно заметить, что число 17 рассматривается как сумма степеней двойки, а те, в свою очередь, умножаются на 53. Так, разложение числа 17 выглядит следующим образом: 17 = 20 + 24. При сложении в качестве слагаемых выбираются значения (20  + 24)·53, остальные произведения, 21·53, 22·53 и 23·53, не используются, так как не входят в разложение числа 17. Этот алгоритм аналогичен тому, что используется в компьютерах. Результат этого алгоритма верен, поскольку представить любое число в виде суммы степеней двойки можно единственным образом. Следовательно, в нашем примере существует единственное множество значений, сумма которых равна 17. Поэтому значения из правого столбца таблицы, которые мы складываем, также можно выбрать только одним способом. Этот метод умножения известен под названием египетского умножения.

Деление выполнялось как операция, обратная умножению. В качестве примера приведем те же числа. Попробуем разделить 901 на 17. Результат должен равняться 53. Результатом деления является целое число без знаков после запятой.

В качестве исходных берется знаменатель 17 и 1. Далее аналогично прошлому примеру оба эти числа удваиваются. Результатом будет 34 и 2. Далее это действие повторяется, результат будет равен 68 и 4. Эти действия повторяются до тех пор, пока первое значение не станет больше числителя, который в нашем примере равен 901. Когда первое значение становится больше числителя (901), полученная пара чисел игнорируется. Результат алгоритма приведен ниже.

Следующая пара чисел — 1088 и 64 — отбрасывается, так как первое число больше 901. Далее нужно подобрать такие числа из первого столбца, чтобы их сумма равнялась 901. В нашем примере это 544, 272, 68 и 17 (так как 544 + 272 + 68 + 17 = 901). Сумма соответствующих им чисел из правого столбца и будет результатом деления. Результат равен 32 + 16 + 4 + 1 = 53.

Как и в случае с умножением, разложение числа 901 является единственным. Мы представили 901 как сумму степеней двойки, умноженных на 17, при этом сумма этих степеней двойки равна 53. Результатом деления в этом случае является целое число. В случаях когда это невозможно и результат содержит несколько знаков после запятой, в этом алгоритме учитываются дроби. Однако алгоритм работы с дробями, который использовали египтяне, был намного сложнее современного. За некоторыми исключениями, рассматривались только дроби вида 1/n, то есть дроби, числитель которых равен 1. Любопытно, что причиной этому было ограничение, вызванное способом записи дроби: сначала записывался символ для обозначения дроби, затем — символы, соответствующие числу в знаменателе. Информация о числителе не записывалась, поэтому он мог равняться только единице.

Для обозначения дроби египтяне использовали этот символ:

Рядом с ним записывался знаменатель, в нашем примере это 21:

Так египтяне записывали дробь 1/21.

Мы упомянули, что существовали дроби с числителем, отличным от 1. Речь идет о дроби 2/3, которая обозначалась отдельным символом, и о дроби вида n/(n + 1), обратной дроби (1 + 1/n). Иными словами, 1/(1 + 1/n) = 1/((n + 1)/n) = n/(n + 1).

Важность дробей и действий с ними четко прослеживается в папирусе Ахмеса, который начинается с представления дроби 2/n в виде суммы 1/x + 1/y + … + 1/z для всех нечетных n от 5 до 101. Далее приводятся аналогичные представления для дробей вида n/10 при n от 2 до 9.

* * *

ПАПИРУС АХМЕСА

В этом знаменитом египетском папирусе длиной 6 метров приводится 87 разнообразных задач с решениями. Он был написан в период с 2000 по 1800 год до н. э. Его автор Ахмес указывает, что он воспроизводит знания, насчитывающие более двух сотен лет, необходимые для будущих писцов. Таким образом, папирус Ахмса можно считать примитивным учебником по математике. В настоящее время папирус хранится в Британском музее, куда он поступил из коллекции Генри Райнда в 1858 году. (По имени владельца его еще называют папирусом Райнда.) В нем также объясняются действия с дробями.

* * *

Папирус Ахмеса содержит информацию о выполнении действий с дробями, а также позволяет получить представление о типичных задачах, которые решали египтяне, и о способах их решения. Первые задачи папируса Ахмеса — это задачи о делении чисел на 10. При их решении использовалась уже упомянутая таблица чисел вида п/10. Далее приводятся некоторые задачи из арифметики и геометрии, а также задачи, которые можно решить с помощью линейных уравнений вида ах + Ьх = с. Некоторые из задач папируса Ахмеса содержат неизвестные, возведенные в квадрат (в современной нотации), однако, несмотря на это, считается, что египтяне не умели решать уравнения второй и третьей степени.

Большинство задач решаются методом, который сейчас известен как метод ложного положения. Лишь задача 30 решается современным способом — с помощью факторизации и деления. Чтобы объяснить метод ложного положения, рассмотрим в качестве примера задачу 24, которая в наши дни решается с помощью линейного уравнения. Задача звучит так:

«Определите цену кучи, если куча и седьмая часть кучи стоит 19».

В современной нотации условие задачи записывается так: х + 1/7х = 19.

Метод ложного положения заключается в следующем. Мы предполагаем, что неизвестная равна определенному числу, и вычисляем результат для этого значения неизвестной. Так как выбранное нами значение неверно, результат также будет ошибочным, поэтому мы скорректируем значение переменной так, чтобы получить верный результат. Допустим, что цена кучи в нашей задаче равна 7, то есть х = 7. Цена кучи и ее седьмой части будет равна 8. Иными словами, при х = 7х + 1/7x = 8. Далее нужно определить, как следует изменить выбранное нами значение 7, чтобы результат выражения был равен 19, а не 8. Нужно умножить 8 или х на 19/8. Используя только дроби с числителем, равным 1, получим, что 2 + 1/4 + 1/8 = 19/8. Умножив 7 на (2 + 1/4 + 1/8), получим 16 + 1/2 + 1/8. В папирусе также показывается, что это решение верно, так как это значение и его седьмая часть в сумме дают 19.

* * *

ЧИСЛО τ В ЕГИПТЕ

В папирусе Ахмеса приводится древнейшее приближенное значение числа τ, которое несколько больше известного нам: оно равняется 256/81, то есть 3,1604. Возможно, эта оценка является самой древней, но не самой точной. В последующих документах приводятся более точные значения. Из них наиболее близко к истинному 3 + 1/7.

* * *

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