Джонатан М. Борвейн, Питер Б.Борвейн
Около 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
Периметр
описанного
многоугольника
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 лет назад.
МОДУЛЯРНЫЕ ФУНКЦИИ И ПРИБЛИЖЕНИЯ К p
Модулярная функция – это некоторая функция l(q), связанная алгебраическим соотношением, называемым модулярным уравнением, с той же функцией от той же переменной q, возведённой в некоторую целую степень p: l(qp). Эта степень p определяет «порядок» модулярного уравнения. Примером модулярной функции служит функция /> ¥ />
l(q) = 16q Õ (
1 + q2n
1 + q2n–1 )
8 . /> n=1 />
Отвечающее ей модулярное уравнение 7-го порядка, связывающее l(q) и l(q7), имеет вид
8 Ö
l(q)l(q7) +
8 Ö
[1 – l(q)][1 – l(q7)] = 1. Сингулярные решения модулярного уравнения – это такие решения, которые удовлетворяют некоторым дополнительным условиям. Один класс сингулярных решений получится, если вычислить последовательность значений k(p) = Ö
l(e–pÖ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 – 4X3 ). /> /> /> /> /> /> /> /> /> />
ПОЛУЧАЕМ число правильных десятичных знаков π:
· для 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 andapproximations 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: Mathematicsof 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 theAGM: A study in analytic number theory and computational complexity. John Wiley& Sons, Inc., 1986.
5. С. Г. Гиндикин. ЗагадкаРамануджана. Квант, 1987, № 10, с. 14.
Дляподготовки данной работы были использованы материалы с сайта ega-math.narod.ru/