86377 (Рамануджан и число π), страница 2

Связь между тригонометрическими функциями и алгебраическими выражениями станет понятней, если рассмотреть окружность единичного радиуса с центром в начале координат на декартовой плоскости х-у. Уравнение этой окружности (её площадь численно совпадает с π) имеет вид х² + y² = 1; оно получается по теореме Пифагора для прямоугольного треугольника с гипотенузой 1. Синус и косинус угла между положительной полуосью х и радиусом, проведённым в любую точку окружности, равны соответственно координатам y и x этой точки, а его тангенс равен y/x.

Однако для вычисления π гораздо важнее тот факт, что обратную тригонометрическую функцию можно разложить в ряд, члены которого выражаются через её производные. Сам Ньютон нашёл 15 знаков π, суммируя несколько первых членов ряда для арксинуса. Позднее он писал одному из коллег: «Мне стыдно сказать вам, до скольких знаков я выполнил эти вычисления, не занимаясь больше ничем».

В 1674 г. Лейбниц вывел формулу 1 – 1/3 + 1/5 – 1/7 + ... = π/4 (арктангенс единицы). (Общий ряд для арктангенса был открыт в 1671 г. шотландским математиком Джеймсом Грегори, хотя аналогичные выражения, по-видимому, были получены в Индии на несколько столетий раньше.) Погрешность этого приближения, определяемая как разность между суммой n членов ряда и точным значением π/4, приблизительно равна (n+1)-му члену. Так как знаменатель каждого следующего слагаемого возрастает лишь на два, то, чтобы получить приближение с точностью до двух знаков, приходится суммировать около 50 членов, с точностью до трех знаков – около 500 и т. д. Таким образом, этот ряд практически непригоден для нахождения более чем нескольких первых знаков π.

Спасла положение формула Джона Мэчина: π/4 = 4 arctg(1/5) – arctg(1/239). Поскольку ряд для арктангенса при заданном значении переменной сходится тем быстрее, чем меньше это значение, благодаря этой формуле вычисления сильно упростились. Пользуясь своей формулой и рядом для арктангенса, Мэчин в 1706 г. вычислил 100 знаков π. Его метод оказался столь мощным, что с начала XVIII в. и до самого недавнего времени все вычисления π с большим числом знаков были выполнены с помощью тех или иных вариантов этого метода.

Из вычислений, проведённых в XIX в., два следует упомянуть особо. В 1844 г. Иоганн Дазе нашёл 205 знаков π в течение нескольких месяцев, вычисляя значения трех арктангенсов и пользуясь формулой, аналогичной формуле Мэчина. Дазе был чудо-вычислителем: он мог примерно за 8 часов перемножать в уме стозначные числа. (Его, наверное, можно считать предтечей современного суперкомпьютера, по крайней мере по объему памяти.) В 1853 г. Уильям Шенкс обошел Дазе, опубликовав полученное им значение π с 607 знаками, хотя начиная с 528-го все остальные оказались неверными. Шенкс потратил на свой труд многие годы – это было рутинное, хотя и трудоёмкое применение формулы Мэчина. Своеобразным рекордом стало и то, что ошибка Шенкса была обнаружена только через 92 года при сравнении его значений с приближением π до 530 знаков, вычисленным Д. Ф. Фергюсоном с помощью механического калькулятора.

С появлением цифровых вычислительных машин попытки найти ещё больше десятичных знаков π возобновились, так как машина идеально приспособлена к долгому и упорному «перемалыванию» чисел. В июне 1949 г. Джон фон Нейман и его сотрудники применили один из первых цифровых компьютеров ENIAC. Машина выдала 2037 знаков за 70 часов. В 1957 г. Г. Э. Фелтон пытался вычислить 10 000 знаков π, но из-за ошибки компьютера только первые 7480 знаков оказались правильными. Рубеж в 10 000 знаков был достигнут годом позже Ф. Женюи с помощью компьютера IBM 704. В 1961 г. Дэниел Шенкс (по утверждению М. Гарднера, не имеющий отношения к Уильяму Шенксу. – Перев.) и Джон У. Ренч-младший вычислили 100 000 знаков π с помощью компьютера IBM 7090 менее чем за 9 часов. Отметка в миллион знаков была пройдена в 1973 г. Жаном Гийу и М. Буйе. Это заняло чуть меньше одного дня работы компьютера CDC 7600. (Вычисления Шенкса–Ренча и Гийу–Буйе были проделаны дважды при помощи двух разных выражений для π через арктангенсы. С учётом всех ошибок, допущенных в подобных вычислениях как человеком, так и машиной, только после такой проверки современные «охотники за знаками» считают рекорд официально установленным.) Главная причина, по которой стало возможным всё более точное вычисление π, состояла в увеличении быстродействия компьютеров. Однако вскоре выявились серьезные препятствия к дальнейшему росту точности. При традиционных способах выполнения на компьютере арифметических действий, если бы мы захотели удвоить число знаков, нам пришлось бы увеличить время вычисления по крайней мере вчетверо. Таким образом, даже при стократном увеличении быстродействия программе Гийу и Буйе для получения миллиардного знака π понадобилось бы четверть века машинного времени. В 70-е годы казалось, что такое вычисление практически невыполнимо.

Однако теперь эта задача осуществима, причём не только благодаря появлению «скоростных» компьютеров, но и благодаря применению новых методов умножения чисел. Решающим было и третье нововведение – итерационные алгоритмы, быстро сходящиеся к π. (Итерационный алгоритм можно реализовать в виде программы, которая повторно выполняет одни и те же арифметические действия, используя выход одного цикла в качестве входа для следующего.) Эти алгоритмы (некоторые из них построены нами) во многих отношениях предвосхищены Рамануджаном, хотя он и не знал ничего о программировании. Компьютеры не только позволили применить результаты Рамануджана, но и помогли разгадать их. Совершенное программное обеспечение, предусматривающее сложные алгебраические манипуляции, позволило уверенно двигаться по дороге, по которой в одиночку, лишенный помощи пробирался Рамануджан 75 лет назад.

Теоретическая информатика научила нас тому, что многие привычные алгоритмы, например способ умножения чисел, которому обучают в школе, весьма далеки от оптимальных. В информатике эффективность алгоритма измеряют его так называемой бит-сложностью: числом сложений и умножений отдельных цифр при выполнении алгоритма. Так, сложение двух n-значных чисел обычным способом имеет бит-сложность, которая растёт как n, a вот бит-сложность умножения двух n-значных чисел обычным способом растёт как n². Таким образом, умножение при традиционных методах намного «труднее», чем сложение, т.е. поглощает намного больше времени.

Однако в 1971 г. А. Шёнхаге и Ф. Штрассен показали, что теоретически бит-сложность умножения двух чисел может быть лишь ненамного больше бит-сложности их сложения. Один из способов добиться этого потенциального уменьшения состоит в том, чтобы реализовать так называемые быстрые преобразования Фурье. Основанное на таком преобразовании умножение двух больших чисел позволяет организовать промежуточные действия над отдельными цифрами столь искусно, что дублирование исключается. Поскольку деление и извлечение корня можно свести к последовательности умножений, их бит-сложность тоже может стать ненамного большей, чем у сложения. В результате получится огромная экономия бит-сложности, а значит, и машинного времени. По этой причине в последнее время все попытки вычисления π основывались на тех или иных вариантах умножения с применением быстрых преобразований Фурье.