Рамануджан и число π

Джонатан М. Борвейн, Питер Б. Борвейн

Около 75 лет назад гениальный индийский математик придумал невероятно эффективные способы вычисления числа π . Созданные сейчас на той же основе алгоритмы для компьютеров позволяют найти миллионы десятичных знаков числа π

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

Тяга к вычислению π с миллионами десятичных знаков может показаться довольно бессмысленной, а само это занятие – лишь ареной для установления рекордов. Действительно, уже 39 знаков π достаточно для вычисления окружности, опоясывающей наблюдаемую Вселенную, с погрешностью, не превышающей радиуса атома водорода. Трудно вообразить физические ситуации, которые потребовали бы большей точности. Почему же математики и вычислители не удовлетворятся, скажем, 50 знаками π?

Этомy есть несколько причин. Во-первых, вычисление π стало чем-то вроде эталона: по нему оценивается совершенство и надежность применяемого компьютера. Вдобавок погоня за всё более точным значением π позволяет математикам проникнуть в таинственные и малодоступные закоулки теории чисел. Другая, более простая причина – «потому что оно всегда с нами». И в самом деле, π является неотъемлемой частью математической культуры вот уже более двух с половиной тысячелетий.

Кроме того, всегда есть шанс, что такие вычисления прольют свет на некоторые загадки, связанные с π. Ведь эта универсальная постоянная, несмотря на сравнительно простую природу, не так уж хорошо понята. Например, хотя и доказано, что π – трансцендентное иррациональное число, никому ещё не удалось доказать, что десятичные знаки π распределены случайно, т.е. каждая цифра от 0 до 9 появляется с одинаковой частотой. Возможно, хотя и в высшей степени маловероятно, что, начиная с какого-то места, все остальные знаки π состоят только из 0 и 1 или проявляют какую-то другую закономерность. Более того,число π внезапно появляется в самых неожиданных задачах, не имеющих никакого отношения к окружностям. Так, допустим, что из множества целых чисел наугад выбирается какое-то число. Тогда вероятность того, что оно не имеет повторяющихся (кратных) простых делителей, равна 6/π2. Как и многие другие выдающиеся математики, Рамануджан был пленён волшебной силой этого числа.

Построенные недавно алгоритмы для вычисления π придали новый блеск математическим сокровищам, извлечённым благодаря возрождению интереса к работам Рамануджана. Однако большая часть того, что он сделал, всё ещё недоступна исследователям. Основные его работы содержатся в «Тетрадях», где он вёл личные записи, пользуясь собственной терминологией и обозначениями. Ещё огорчительнее для математиков, изучивших «Тетради» Рамануджана, то, что он обычно не записывал доказательств своих теорем. Расшифровка и редактирование «Тетрадей», предпринятые Брюсом К. Берндтом из Иллинойсского университета в Эрбана-Шампейн, только сейчас близятся к завершению.

Насколько нам известно, никто и никогда ещё не брался за работу по математическому редактированию такого объёма и такой трудности. Но усилия наверняка будут вознаграждены. Наследие Рамануджана, содержащееся в «Тетрадях», обещает не только обогатить чистую математику, но и найти применения в разных областях математической физики. Например, Родни Дж. Бакстер из Австралийского национального университета признаёт, что открытия Рамануджана помогли ему решить некоторые задачи статистической физики, относящиеся к поведению системы взаимодействующих частиц, рассматриваемых как твердые шарики в гексагональной решётке наподобие медовых сотов. А Карлос Дж. Морено из Университета г. Нью-Йорка и Фримен Дж. Дайсон из Института высших исследований отметили, что физики начинают применять результаты Рамануджана в теории суперструн.

Фигура Рамануджана как математика тем более удивительна, что его формальное образование было весьма ограниченным. Он родился 22 декабря 1887 г. в небогатой семье касты браминов в местечке Эрод на юге Индии и вырос в городке Кумбаконаме, где его отец служил бухгалтером в небольшой текстильной лавке. Его математический талант был замечен очень рано, и в возрасте 7 лет он получил право на стипендию для учёбы в средней школе Кумбаконама. Он поражал одноклассников тем, что помнил наизусть сложные математические формулы и много знаков числа π.

В 12 лет Рамануджан изучил обширный труд С. Л. Лоуни «Плоская тригонометрия», включая рассмотренные там суммы и произведения бесконечных последовательностей, которым суждено было занять важное место в его последующих работах. Через три года Рамануджан достал книгу «Сборник элементарных результатов чистой математики» (Synopsis of Elementary Results in Pure Mathematics), содержащий свыше 6000 теорем (большей частью без доказательств) и составленный преподавателем Кембриджского университета Дж. Ш. Карром. Две эти книги и стали основой математической подготовки Рамануджана.

В 1903 г. Рамануджан был принят в местный колледж (входивший в состав Мадрасского университета. – Перев.). Однако поглощённый своими математическими изысканиями в ущерб всему остальному, он провалился на экзаменах; то же самое повторилось четыре года спустя в другом колледже в Мадрасе. После женитьбы в 1909 г. Рамануджан на время оставил своё увлечение и попробовал найти работу. К счастью, в 1910 г. по pекомендации многих сочувствующих Рамануджану индийских математиков на него обратил внимание богатый любитель и покровитель математики Р. Рамачандра Рао. Под впечатлением открытий, законспектированных Рамануджаном в его «Тетрадях», Рамачандра Рао предоставил ему ежемесячное пособие.

В 1912 г., желая всё-таки иметь работу, Рамануджан устроился бухгалтером в Трест мадрасского порта, который возглавлял английский инженер Френсис Спринг. Вместе с основателем Индийского математического общества В. Рамасвами Айяром они уговорили Рамануджана сообщить свои результаты трём известным английским математикам. Двое из них, по-видимому, не отозвались. Третьим был Г. Г. Харди из Кембриджского университета, признанный теперь самым выдающимся английским математиком того времени.

Харди, привыкший к письмам от всякого рода «умников», получив послание Рамануджана 16 января 1913 г., сначала был склонен его проигнорировать. Однако вечером того же дня он решил вместе с коллегой и близким другом Джоном И. Литлвудом поломать голову над списком из 120 формул и теорем, которые Рамануджан приложил к своему письму. Через несколько часов они «вынесли приговор» – перед ними работа не маньяка, а гения. (По составленной Харди позднее «шкале чистого таланта» для математиков Рамануджан получил 100 баллов, Литлвуд – 30, а себе Харди поставил 25. Немецкий математик Давид Гильберт, самая влиятельная фигура в математике того времени, заслужил только 80.) Этот эпизод и то, что за ним последовало, по словам Харди, было единственным романтическим событием его жизни. Он писал, что некоторые формулы Рамануджана его совершенно ошеломили, но тем не менее «они, несомненно, верны, ибо если бы они были неверны, ни у кого не хватило бы воображения их выдумать».

Харди немедленно пригласил Рамануджана приехать в Кембридж. Но серьезные возражения со стороны матери и собственные колебания задержали его отъезд до марта 1914 г. В течение следующих пяти лет Харди и Рамануджан работали совместно в Тринити-Колледже Кембриджского университета. Сочетание блестящего мастерства Харди-аналитика и фантастической интуиции Рамануджана привело к необычайно плодотворному сотрудничеству. Они опубликовали серию основополагающих работ о свойствах различных теоретико-числовых функций, открывавших путь для ответа на вопросы типа: каково наиболее вероятное число простых делителей у данного целого числа? Сколькими способами можно выразить натуральное число в виде суммы меньших натуральных чисел?

В 1917 г. Рамануджан стал действительным членом Лондонского королевского общества и профессором Кембриджского университета. Впервые индиец был удостоен того и другого звания. Слава его росла, однако здоровье резко ухудшилось. В военное время, когда в Великобритании остро ощущалась нехватка продовольствия, трудно было придерживаться вегетарианской диеты, которую он строго соблюдал. Рамануджан не раз попадал в больницу, но поток его новых результатов не иссякал. В 1919 г., когда война закончилась и путешествия за границу снова стали безопасными, он вернулся в Индию. Ставший кумиром молодых индийских интеллектуалов 32-летний Рамануджан умер 26 апреля 1920 г., как тогда думали, от туберкулёза, но, скорее, как считают теперь, от острого недостатка витаминов. [Это было в 1987 г. В 1994 г. произошёл новый поворот. Проанализировав симптомы и историю болезни Рамануджана Д. Янг поставил свой диагноз: гепатический амёбиаз; см. подробности на второй странице статьи Б. Берндта «An Overview of Ramanujan's Notebooks». Кстати, эту весьма интересную публикацию можно рассматривать как продолжение статей В.И.Левина. – E.G.A.] До конца преданный математике Рамануджан и в последние месяцы жизни, измученный болезнью, продолжал свой труд и создал замечательную работу, записанную в его так называемой «Потерянной тетради».

Результаты Рамануджана, касающиеся числа π, связаны большей частью с его исследованиями модулярных уравнений – темы, наиболее подробно раскрытой в «Тетрадях». Грубо говоря, модулярное уравнение – это алгебраическое соотношение между функцией от некоторой переменной x, т.е. f (x), и той же функцией от переменной x, возведенной в некоторую целую степень, например f (x2), f (x3) или f (x4). Эта целая степень задает «порядок» модулярного уравнения. Простейшим модулярным уравнением является уравнение 2-го порядка

f (x) =

2√f (xІ) 1 + f (xІ)

.

Конечно, не всякая функция удовлетворяет какому-нибудь модулярному уравнению. Но существует класс функций, обладающих этим свойством. Они называются модулярными функциями. Кроме того, модулярное уравнение выполняется только при определённых значениях x, а именно тех, которые являются «решениями» данного уравнения.

Рамануджан не имел себе равных в умении «откапывать» решения модулярных уравнений, удовлетворяющие также некоторым другим условиям. Такие решения называются сингулярными. Оказывается, поиски сингулярных решений в некоторых случаях приводят к числам, натуральные логарифмы которых совпадают с π (умноженным на константу) в поразительно большом числе десятичных знаков. Виртуозно пользуясь этим общим приемом, Рамануджан построил для приближения π много замечательных бесконечных рядов и одночленных формул. Некоторые из них приведены в его единственной формальной статье на эту тему «Модулярные уравнения и приближения к π», опубликованной в 1914 г.

Своими попытками вычислять π Рамануджан отдал дань древней традиции. Уже в самых ранних индо-европейских цивилизациях было известно, что площадь круга пропорциональна квадрату его радиуса, а длина окружности пропорциональна её диаметру. Правда, не совсем ясно, когда впервые было осознано, что отношение длины любой окружности к её диаметру и отношение площади любого круга к квадрату его радиуса равны одной и той же постоянной, которую принято обозначать символом π. (Сам этот символ был введен гораздо позднее – в 1706 г. английским математиком-любителем Уильямом Джонсоном и стал широко употребляться благодаря поддержке крупнейшего математика XVIII в. Леонарда Эйлера.)

Величайший математик древности Архимед из Сиракуз строго доказал равенство двух указанных отношений в своем трактате «Измерение круга». Он вычислил и приближённое значение π, причём на основе математических принципов, а не прямых измерений длины окружности, площади круга и диаметра. Архимед вписывал в окружность и описывал около неё правильные многоугольники (т.е. многоугольники со сторонами одинаковой длины). Диаметр окружности принимался за единицу, а периметры описанного и вписанного многоугольников рассматривались как приближения соответственно сверху и снизу к длине окружности, которая в данном случае численно совпадала с π (см. вкладку [1]).

Этот метод приближения π не был новшеством: ещё раньше вписывать многоугольники с возрастающим числом сторон предложил Антифон, а его современник Брисон из Гераклеи дополнительно ввёл описанные многоугольники. Новшеством был выполненный Архимедом правильный расчет результата удвоения числа сторон как вписанного, так и описанного многоугольников. Тем самым он разработал процедуру, повторение которой достаточное число раз в принципе позволяет вычислить π с любым количеством знаков. (Следует заметить, что периметр правильного многоугольника легко вычисляется с помощью простых тригонометрических функций: синуса, косинуса и тангенса, однако во времена Архимеда, т.е. в III в. до н.э., эти функции ещё не были полностью изучены и вычисление периметров было далеко не таким легким делом, как может сейчас показаться.

Архимед начал с вписанного и описанного шестиугольников и получил неравенство 3 < π < 23. Четырежды удвоив число сторон (т.е. доведя его до 96), он сузил интервал для π: 310/71 < π < 31/7 и получил приближённое значение  3,14. Есть некоторые основания предполагать, что дошедший до нас текст трактата «Измерение круга» представляет собой часть более обширного труда, в котором Архимед объясняет, как, начав с десятиугольников и применив шесть раз операцию удвоения, он получил приближение с пятью знаками:  3,1416. Сам по себе метод Архимеда прост, но при отсутствии готовых таблиц тригонометрических функций требует извлечения корней; выполнение этой операции вручную занимает довольно много времени. Кроме того, приближения сходятся к π очень медленно: с каждой итерацией погрешность уменьшается лишь вчетверо. Тем не менее до середины XVII в. все попытки европейских учёных вычислить π так или иначе опирались на этот метод. Голландский математик XVI в. Лудольф ван Цейлен посвятил вычислению π большую часть своей научной деятельности. К концу жизни он нашёл приближение с 32 десятичными знаками, вычислив периметры вписанного и описанного многоугольников с 262 (т.е. порядка 1018) сторонами. Говорят, полученное им значение π, которое в некоторых европейских странах называют в его честь числом Лудольфа, высечено на его надгробном камне.

Периметр описанного многоугольника Pc = n tg(180°/n)		Периметр вписанного многоугольника Pi = n sin(180°/n)
где n – число сторон
	n = 6
Pc = 3,464...		Pi = 3,000...
	n = 12
Pc = 3,215...		Pi = 3,105...
	n = 24
Pc = 3,159...		Pi = 3,132...
Метод Архимеда приближения к π состоял в том, что в окружность диаметра 1 вписывались и около неё описывались правильные многоугольники. Периметры вписанных многоугольников служат соответственно нижними и верхними границами для значения π. Для нахождения периметров можно, как здесь показано, воспользоваться синусами и тангенсами, однако Архимеду пришлось изобретать эквивалентные соотношения на основе геометрических построений. С помощью 96-угольника он установил, что π больше, чем 310/71, и меньше, чем 31/7.

Развитие анализа в основном трудами Исаака Ньютона и Готфрида Вильгельма Лейбница позволило намного ускорить вычисление приближённых значений π. В анализе существуют эффективные методы нахождения для функции её производной и интеграла. С помощью этих методов можно показать, что обратные тригонометрические функции представляются в виде интегралов от квадратичных функций, связанных с окружностью.

Связь между тригонометрическими функциями и алгебраическими выражениями станет понятней, если рассмотреть окружность единичного радиуса с центром в начале координат на декартовой плоскости х-у. Уравнение этой окружности (её площадь численно совпадает с π) имеет вид х2 + y2 = 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 в. и до самого недавнего времени все вычисления π с большим числом знаков были выполнены с помощью тех или иных вариантов этого метода.

ПРОИЗВЕДЕНИЕ ВАЛЛИСА (1665)  π 2 = 22 13  44 35  66 57  88 79  ... =  4n2 4n2 – 1 . n=1

РЯД ГРЕГОРИ (1671)  π 4 = 1 – 1 3 + 1 5 – 1 7 + ... =  (–1)n 2n + 1 . n=0

ФОРМУЛА МЭЧИНА (1706)  π 4 = 4 arctg(1/5) – arctg(1/239), где arctg x =  (–1)n x2n+1 2n + 1 . n=0

РАМАНУДЖАН (1914)  1 π = 22 9 801  (4n)! [1103 + 26 390n] (n!)4 3964n . n=0

ДЖ.БОРВЕЙН и П.БОРВЕЙН (1987)  1 π = 12  (–1)n(6n)! [212 175 710 91261 + 1 657 145 277 365 + n(13 773 980 892 67261 + 107 578 229 802 750)] (n!)3 (3n)! [5 280(236 674 + 30 30361]3n + 3/2 . n=0

Члены математических последовательностей можно складывать и перемножать, иногда получая при этом ряды или бесконечные произведения, сходящиеся к π (делённому на константу) или к 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 лет назад.

МОДУЛЯРНЫЕ ФУНКЦИИ И ПРИБЛИЖЕНИЯ К 

Модулярная функция – это некоторая функция (q), связанная алгебраическим соотношением, называемым модулярным уравнением, с той же функцией от той же переменной q, возведённой в некоторую целую степень p: (qp). Эта степень p определяет «порядок» модулярного уравнения. Примером модулярной функции служит функция  (q) = 16q  ( 1 + q2n 1 + q2n–1 ) 8 . n=1

Отвечающее ей модулярное уравнение 7-го порядка, связывающее (q) и (q7), имеет вид 8  (q)(q7) + 8  [1 – (q)][1 – (q7)] = 1.

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

k(p) =  (e–p)

для целых p. Эти значения обладают замечательным свойством: логарифмическое выражение

–2 p ln ( k(p) 4 )

имеет много первых десятичных знаков, общих с π, причем число их тем больше, чем больше значение 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.]

Нас заинтересовали причины столь быстрой сходимости алгоритма Гаусса–Брента–Саламина. Исследуя их, мы разработали общую методику построения аналогичных алгоритмов, быстро сходящихся к π, a также к некоторым другим величинам. Основываясь на теории, в общих чертах описанной в 1829 г. немецким математиком Карлом Густавом Якобом Якоби, мы поняли, что в принципе значения π можно вычислять при помощи одного класса интегралов, называемых эллиптическими интегралами – они позволяют находить периметр эллипса.

Эллиптические интегралы обычно не берутся, но могут быть легко аппроксимированы при помощи итерационных процедур, опирающихся на модулярные уравнения. Мы обнаружили, что алгоритм Гаусса–Брента–Саламина представляет собой частный случай нашего более общего метода, связанный с модулярным уравнением второго порядка. Используя модулярные уравнения более высоких порядков, можно добиться более быстрой сходимости к значению интеграла, а значит, и получить лучший алгоритм для вычисления π. Поэтому мы тоже построили различные алгоритмы на основе модулярных уравнений третьего, четвёртого и более высоких порядков.

В январе 1986 г. Дэвид X. Бейли из Исследовательского центра Национального управлении но аэронавтике и исследованию космического пространства, пользуясь одним из наших алгоритмов, после 12 итераций на суперкомпьютере Cray-2 получил 29 360 000 десятичных знаков π. Основанный на модулярном уравнении 4-го порядка этот алгоритм более чем вчетверо увеличивает количество знаков после каждой итерации. Год спустя Я. Канада и его сотрудники выполнили ещё одну итерацию на суперкомпьютере NEC SX-2 и получили 134 217 000 знаков, проверив тем самым свой более ранний такой же результат, полученный с помощью алгоритма Гаусса–Брента–Саламина. Ещё две итерации нашего алгоритма – дело нехитрое, если бы удалось как-нибудь на несколько недель заполучить суперкомпьютер в монопольное пользование, – дали бы более двух миллиардов знаков π.

(a)	ПОЛАГАЕМ y0 = 1/2, a0 = 1/2 и yn+1 = 1 – 1 – y n 2 an+1 = [(1 + yn+1)2 an] – 2n+1yn+1. 1 + 1 – y n 2	ПОЛУЧАЕМ число правильных десятичных знаков π: для 1/a1 – 0; для 1/a2 – 3; для 1/a3 – 8; для 1/a4 – 19.
(b)	ПОЛАГАЕМ y0 = 2 – 1, a0 = 6 – 42 и yn+1 = 4 1 – 1 – y n 4 an+1 = [(1 + yn+1)4 an] – 22n+3yn+1(1 + yn+1 + yn+1). 2 4 1 + 1 – y n 4	ПОЛУЧАЕМ число правильных десятичных знаков π: для 1/a1 – 8; для 1/a2 – 41; для 1/a3 – 171; для 1/a4 – 694.
(c)	ПОЛАГАЕМ s0 = 55 – 10, a0 = 1/2 и sn+1 = 25 sn(Z + X/Z + 1)2 an+1 = 2 sn an – 5n 2 sn – 5 2 + 2  sn (sn – 2sn + 5) , где X = 5 sn – 1, Y = (X – 1)2 + 7 и Z = 5  Ѕ X (Y +  Y 2 – 4X 3 ).	ПОЛУЧАЕМ число правильных десятичных знаков π: для 1/a1 – 5; для 1/a2 – 31; для 1/a3 – 166; для 1/a4 – 848.
Итерационные алгоритмы, разработанные авторами, позволяют вычислять π с невероятной точностью. Алгоритм (a) квадратично сходится к 1/π: число правильных цифр, определяемых величиной an увеличивается более чем вдвое всякий раз, когда n увеличивается на 1. Алгоритм (b) при каждой итерации увеличивает количество правильных цифр более чем вчетверо, а алгоритм (c) – более чем впятеро. Алгоритм (b), возможно, самый эффективный из всех известных алгоритмов вычисления π: три последних рекордных вычисления выполнены на суперкомпьютерах с помощью именно этого алгоритма. Когда авторы работали над своими алгоритмами, им стало ясно что Рамануджан при построении своих приближений к π следовал аналогичным методам. Так, вычисление sn в алгоритме (c) основано на замечательном модулярном уравнении пятого порядка, открытом Рамануджаном.
Число десятичных знаков π 100 000 000 10 000 000 1 000 000 100 000 10 000 1 000 100 10 1 1450 1706 1949 1957 1961 1973 1985 1987
Число известных знаков π за последние 10 лет выросло на два порядка благодаря разработке итерационных алгоритмов и их реализации на суперкомпьютерах, снабжённых новыми эффективными методами умножения.

Итерационные методы лучше всего приспособлены для вычисления π именно с помощью компьютера, поэтому не удивительно, что Рамануджан никогда не пытался им следовать. Однако главные составляющие итерационных алгоритмов для π, и в частности модулярные уравнения, следовало искать в работах Рамануджана. Оригинальный путь, которым он шёл к бесконечным рядам и приближённым формулам для π более чем три четверти века назад, в чём-то наверняка совпадал с нашими собственными усилиями вывести алгоритмы для вычисления π. И действительно, формулы, приведенные в его статье, посвященной π, и в «Тетрадях», во многом помогли нам при построении некоторых алгоритмов. Например, хотя мы могли доказать существование алгоритма 11-го порядка и знали его общую формулировку, только натолкнувшись на модулярные уравнения этого порядка у Рамануджана, мы сумели открыть неожиданно простую форму этого алгоритма.

С другой стороны, из полученных нами общих формул удалось вывести все ряды Рамануджана для π. При выводе одного из них, который сходился к π быстрее любого другого известного нам в то время ряда, небольшая помощь пришла с неожиданной стороны. Мы проверили все величины, входящие в выражение этого ряда, кроме одной – коэффициента 1103 в числителе (см. вкладку [2]), поскольку были уверены, как, должно быть, и сам Рамануджан, что это правильное число. Для доказательства требовалось либо упростить некое устрашающего вида уравнение, в котором переменные возводились в степени с показателями, равными нескольким тысячам, либо погрузиться в малодоступные глубины теории чисел.

По счастливому совпадению Р. Уильям Госпер-младший из фирмы Symbolics, Inc., в 1985 г. решил провести испытание именно этого ряда Рамануджана на точность приближения к значению π. Он довёл вычисления более чем до 17 млн. знаков (в то время это было рекордом), однако само по себе это не могло служить доказательством, что сумма ряда действительно равна π. Конечно, Госпер знал, что миллионы знаков полученного им числа совпадают с найденными ранее Я. Канадой при помощи алгоритма Гаусса–Брента–Саламина, и понимал, что вероятность ошибки Рамануджана ничтожно мала.

Но как только Госпер закончил свои вычисления и сверил их с результатом Канады, мы получили всё, что требовалось для обоснования числа 1103, а именно что ряд дает верное значение с точностью до 10–10 000 000. Этот результат на основании примерно тех же соображений, из которых следует, что два целых числа с разностью меньше 1 обязательно совпадают, позволяет точно установить, что упомянутый коэффициент равен 1103. Таким образом, проведённое Госпером вычисление стало частью нашего доказательства. Нам было известно, что этот ряд (и соответствующий алгоритм) столь чувствителен к малейшим неточностям, что если бы Госпер взял какой-нибудь другой коэффициент, а компьютер в процессе вычисления допустил ошибку хотя бы в одной цифре, то получилось бы не значение π, а бессмысленный набор цифр.

Можно показать, что алгоритмы рамануджановского типа очень близки к наилучшим возможным. Если собрать все операции, которые производятся при выполнении подобных алгоритмов (с применением наилучших известных методов сложения, вычитания и умножения), то окажется, что бит-сложность вычисления n знаков π ненамного больше бит-сложности перемножения двух n-значных чисел, а последняя, когда умножение выполняется с применением быстрых преобразований Фурье, ненамного превосходит бит-сложность сложения двух n-значных чисел – простейшей возможной арифметической операции, выполняемой при помощи компьютера.

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

Титанический труд по редактированию «Тетрадей», начатый 60 лет назад английскими аналитиками Дж. Н. Ватсоном и Б. Н. Уилсоном и завершаемый ныне Брюсом Берндтом, требует поисков доказательств, источников, а иногда небольших исправлений каждого из многих тысяч содержащихся в них утверждений и тождеств. Одна строчка в «Тетрадях» легко может вызвать многие страницы комментариев. Задача дополнительно затруднена нестандартными математическими обозначениями, в которых записаны формулы. Поэтому большая часть работы Рамануджана останется недоступной математическим кругам до тех пор, пока Берндт не закончит свой труд.

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

Список литературы

1. S. Ramanujan. Modular equations and approximations to π. In: The Quarterly Journal of Pure and Applied Mathematics, 1914, v. 45, pp. 350–372.

2. E. Salamin. Computation of π using arithmetic-geometric mean. In: Mathematics of Computation, 1976, v. 30, No. 135, pp. 565–570.

3. P. Beckmann. A history of π. The Golem Press, 1977.

4. J. M. Borwein, P. B. Borwein. Pi and the AGM: A study in analytic number theory and computational complexity. John Wiley & Sons, Inc., 1986.

5. С. Г. Гиндикин. Загадка Рамануджана. Квант, 1987, № 10, с. 14.