Статья: Рамануджан и число 960
Ö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 и
|
ПОЛУЧАЕМ число правильных десятичных знаков π: · для 1/a1 – 0; К-во Просмотров: 371
Бесплатно скачать Статья: Рамануджан и число 960
|