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

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

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

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

---

Система вычислений с помощью палочек также появилась в Корее и Японии (точный период неизвестен). Известно, что эта система применялась в Японии в период правления императрицы Суйко (593–628) под названием санги.

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

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

Китайский абак появился в Японии примерно в XVI веке и был известен как соробан. Он появился благодаря торговцам, однако его распространение было непростым. Лишь спустя много лет он был введен в школах и начал использоваться для решения сложных математических задач. В торговле соробан быстро заменил ранее применявшиеся устройства, однако они по-прежнему использовались в высшей математике.

Для обозначения цифр и в Китае, и в Японии (системы счисления в этих странах очень похожи) использовались девять идеограмм.

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

При записи чисел использовались символы от 1 до 9 вместе с символами десятков, сотен и так далее. Например, число 10563 записывалось следующим образом:

что расшифровывается так:

Следует упомянуть, что в отличие от системы, используемой в большинстве европейских языков, в основе которой лежит тысяча (103), в китайской системе в основе кратных величин лежит 104. Следовательно, 132000 записывается как 13·(104) + 2000.

В виде идеограмм это число будет представлено так:

Число π в Китае

Китайцы разработали алгоритмы для вычисления числа π. Великий математик Лю Хуэй, живший около 300 года во времена царства Вэй, возникшего после распада империи Хань, первым создал метод вычисления числа π. Живший до него ученый и изобретатель Чжан Хэн (78—139), который создал прибор для определения землетрясений за 1700 лет до появления первого сейсмографа, получил приближенное значение π, равное 3,1724. Также использовались значения 3,162 (корень из 10) и 3,156. В III веке астроном Вань Фань, живший в царстве У, использовал последнее значение, равное дроби 142/45.

Первый метод, использованный Лю Хуэем для нахождения приближенного значения π, заключался в бисекции многоугольников. С помощью многоугольника с 96 сторонами он вычислил, что π лежит в интервале между 3,141024 и 3,142708. Он использовал приближенное значение, равное 157/50, так как считал значение 3,14 достаточно точным.

Китайские марки, посвященные ученым Лю Хуэю (слева) и Чжану Хэну (справа).

Лю Хуэй использовал шестиугольник со стороной L, вписанный в окружность. Далее число сторон многоугольника последовательно удваивалось. Иными словами, сначала рассматривался шестиугольник, затем 12-угольник, далее — 24-угольник (24 = 12·2), 48-угольник (48 = 24·2) и так далее. На каждом шаге Лю Хуэй вычислял площадь многоугольника с N сторонами и длину стороны многоугольника с числом сторон, равным 2N.

Будем обозначать за l длину стороны многоугольника с 2N сторонами. Используем теорему Пифагора: для данного прямоугольного треугольника с гипотенузой h и двумя катетами длиной с1 и с2 выполняется равенство h2 = с12 + с22.

Вычисление длины стороны l по известному значению L, где L — длина стороны шестиугольника, I — длина стороны 12-угольника,

О — центр окружности, А и В — две вершины шестиугольника, С — новая вершина, Р — точка на стороне шестиугольника, равноудаленная от А и В. Радиус окружности равен r, расстояние от центра до Р равно R.

На рисунке обозначены центр окружности О и сторона шестиугольника (длиной L). Ее концы обозначены А и В. Точки ОАВ определяют треугольник. Далее вычисления выполняются следующим образом.

Шаг 0. Будем рассматривать многоугольник с N = 6 сторонами, длина его стороны L известна.

Шаг 1. Разделим сторону АВ на две равные части. Обозначим середину стороны АВ точкой Р.

Шаг 2. Вычислим длину отрезка ОР и обозначим ее длину за R. Для этого применим теорему Пифагора. Нам известно, что гипотенуза треугольника ОАР равна r, один из катетов равен L/2, длина другого, которую мы хотим вычислить, равна R. По теореме Пифагора г2 = R2 + (L/2)2. Отсюда имеем R2 = r2 — (L/2)2, следовательно

Шаг 3. Рассмотрим радиус окружности, который проходит через точку Р. Точка пересечения этого радиуса и окружности будет вершиной многоугольника с 2N сторонами. Обозначим эту точку С. Зная R, мы можем вычислить длину отрезка PC. Обозначим ее за р. Так как длина ОС равна r, длина PC равна

Шаг 4. Длину отрезка АС можно определить по теореме Пифагора. Как мы уже говорили, будем обозначать длину этого отрезка за l. В рассматриваемом прямоугольном треугольнике гипотенуза равна l, катеты — L/2 и р. Следовательно,

Шаг 5. Выразив l из последнего равенства, получим длину многоугольника с 2N сторонами:

Шаг 6. Площадь многоугольника с N сторонами можно вычислить на основе площади треугольника ОАВ. Площадь многоугольника будет в N раз больше площади этого треугольника. Площадь треугольника ОАВ, очевидно, равна половине произведения его основания на высоту. Длина основания АВ равна L, высота равна R (это значение мы уже вычислили). Следовательно, площадь многоугольника равна

N·площадь треугольника ОАВ = N·(L·R)/2.

Шаг 7. Далее нужно вернуться к шагу 2 и принять N = 2N, L = l. Чтобы определить значение π, нужно учесть, что площадь круга равна π·r2. Следовательно, для r = 10 площадь круга равна π·100.

Если начать с r = 10 (в этом случае L = 10), с помощью вышеприведенного алгоритма мы получим значения площадей, представленные в таблице ниже. В этой таблице используется современная нотация, Лю Хуэй в своих расчетах применял дроби. Он заметил, что для данного многоугольника с 2N сторонами длиной l, построенного на основе многоугольника с N сторонами длиной L, площадь круга (обозначим ее за С) удовлетворяет следующему неравенству:

площадь (2N) < С < площадь (2N) + избыток.

Избыток в этом неравенстве соответствует 2N треугольникам площадью р·(L/2)/2. Напомним, что р = r — R. Получим значение избытка, равное 2·N·(р·(L/2))/2. Эти значения также приведены в таблице. Разница между площадью 96-угольника и 192-угольника очень мала, поэтому Лю Хуэй счел π = 3,14 достаточно точным.

Лю Хуэй заметил, что между последовательными избытками наблюдается определенное соотношение. В частности, он установил, что отношение между данным и следующим избытком примерно равно 1/4 = 0,25. Эти отношения представлены в таблице ниже. Используя это отношение, он вычислил приближенное значение площади 3072-угольника и с его помощью получил более точную оценку числа π.