| Члены математических последовательностей можно складывать и перемножать, иногда получая при этом ряды или бесконечные произведения, сходящиеся к π (делённому на константу) или к 1/π. Первые две последовательности, открытые математиками Джоном Валлисом и Джеймсом Грегори, широко известны, однако для вычислительных целей практически бесполезны. Для нахождения ста знаков π не хватило бы и ста лет работы суперкомпьютера, запрограммированного на сложение или умножение членов любой из этих последовательностей. Формула, открытая Джоном Мэчином, сделала вычисление π выполнимым, так как из анализа известен способ представлять арктангенс числа x в виде ряда, который сходится к значению арктангенса тем быстрее, чем меньше x. Все известные вычисления π с начала XVIII в. и до начала 70-х годов нашего века опирались на варианты формулы Мэчина. Сумма последовательности Рамануджана сходится к истинному значению 1/π гораздо быстрее: каждый очередной член последовательности добавляет, грубо говоря, восемь новых правильных цифр. Самая нижняя последовательность, найденная авторами, добавляет около 25 цифр с каждым новым членом. Первый член (соответствующий n = 0) дает число, совпадающее с π в 24 десятичных знаках. |
Из вычислений, проведённых в 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 лет назад.
| Отвечающее ей модулярное уравнение 7-го порядка, связывающее l(q) и l(q7), имеет вид |
| Сингулярные решения модулярного уравнения – это такие решения, которые удовлетворяют некоторым дополнительным условиям. Один класс сингулярных решений получится, если вычислить последовательность значений |
| |
| для целых p. Эти значения обладают замечательным свойством: логарифмическое выражение |
| |
| имеет много первых десятичных знаков, общих с π, причем число их тем больше, чем больше значение p. Рамануджан не имел себе равных в способности находить эти сингулярные значения. Одно из самых известных, когда p = 210, содержалось в его первом письме к Харди. Вот оно: |
| k(210) = (Ö2 – 1)2(2 – Ö3)(Ö7 – Ö6)2(8 – 3Ö7)(Ö10 – 3)2(Ö15 – Ö14)(4 – Ö15)2(6 – Ö35). |
| Если подставить его в логарифмическое выражение, получится число, которое совпадает с π в первых 20 десятичных знаках. Для сравнения, k(240) приводит к числу, которое совпадает с π в более чем 1 млн. знаков. Пользуясь этим общим приёмом, Рамануджан построил много замечательных рядов для π, включая тот, что приведён на вкладке [2]. Тот же общий подход лежит в основе двухшагового итерационного алгоритма, показанного на вкладке [4]. Первый шаг каждой итерации (вычисление yn) соответствует нахождению одного из последовательности сингулярных значений путём решения модулярного уравнения подходящего порядка, второй шаг (вычисление an) отвечает взятию логарифма этого сингулярного значения. |
Теоретическая информатика научила нас тому, что многие привычные алгоритмы, например способ умножения чисел, которому обучают в школе, весьма далеки от оптимальных. В информатике эффективность алгоритма измеряют его так называемой бит-сложностью: числом сложений и умножений отдельных цифр при выполнении алгоритма. Так, сложение двух n-значных чисел обычным способом имеет бит-сложность, которая растёт как n, a вот бит-сложность умножения двух n-значных чисел обычным способом растёт как n2. Таким образом, умножение при традиционных методах намного «труднее», чем сложение, т.е. поглощает намного больше времени.
Однако в 1971 г. А. Шёнхаге и Ф. Штрассен показали, что теоретически бит-сложность умножения двух чисел может быть лишь ненамного больше бит-сложности их сложения. Один из способов добиться этого потенциального уменьшения состоит в том, чтобы реализовать так называемые быстрые преобразования Фурье. Основанное на таком преобразовании умножение двух больших чисел позволяет организовать промежуточные действия над отдельными цифрами столь искусно, что дублирование исключается. Поскольку деление и извлечение корня можно свести к последовательности умножений, их бит-сложность тоже может стать ненамного большей, чем у сложения. В результате получится огромная экономия бит-сложности, а значит, и машинного времени. По этой причине в последнее время все попытки вычисления π основывались на тех или иных вариантах умножения с применением быстрых преобразований Фурье.
Однако для практического вычисления сотен миллионов десятичных знаков π пришлось «переоткрыть» одну красивую формулу, известную полтора столетия назад Карлу Фридриху Гауссу. В середине 70-х годов Ричард П. Брент и Юджин Саламин независимо обнаружили, что эта формула дает для π квадратично сходящийся алгоритм, т.е. при каждой итерации число знаков удваивается. С 1983 г. Ясумаса Канада из Токийского университета и его сотрудники с помощью этого алгоритма установили несколько мировых рекордов по числу знаков для π. [Мелкая статья с некоторыми подробностями типа «набор 0123456789 встречается первый раз в разложении числа π на 17 387 594 880-м знаке (цифра 0) после десятичной точки». — E.G.A.]