Секреты числа Пи. Почему неразрешима задача о квадратуре круга - [23]
* * *
Вычисление первых 2037 знаков π на компьютере ENIAC заняло 70 часов. В таблице ниже указано рассчитанное количество знаков π и год, чтобы дать представление о том, какие изменения вызвало появление компьютеров:
1947 ∙ Д. Фергюсон и Джон Ренч с использованием механического калькулятора ∙ 808
1949 ∙ Джон Ренч-младший и Леви Смит с помощью ENIAC ∙ 2037
1958 ∙ Франсуа Женюи ∙ 10 000
1961 ∙ Дэниел Шенке и Джон Ренч ∙ 100 265
1973 ∙ Жан Гийу и Мартин Буйе ∙ 1001 250
1983 ∙ Ясумаса Канада и Ясунори Уширо ∙ 10 013 395
1987 ∙ Ясумаса Канада, Йошияки Тамура и Йошинобу Кубо ∙ 134 214 700
1989 ∙ Григорий и Давид Чудновские ∙ 1011196 691
2002 ∙ Ясумаса Канада с группой из девяти специалистов ∙ 1241100 000 000
2009 ∙ ДайсукеТакахаши и группа программистов ∙ 2576 980 370 000
2011 ∙ Сигеру Хондо ∙ 10 000 000 000 050
В 1973 году старинная формула Эйлера вкупе с формулой Мэчина позволила Гийу и Буйе вычислить миллион знаков π:
Любопытно, что для вычисления второго слагаемого достаточно вычислить первое и перенести запятую на несколько позиций. Вне зависимости от их абсолютной величины два первых слагаемых будут отличаться только количеством нулей.
В 1976 году Юджин Саламин и Ричард Брент предложили алгоритм, основанный на давней гипотезе Гаусса и Лежандра о последовательном вычислении средних арифметических и средних геометрических. Суть алгоритма непросто описать вкратце. Алгебраический алгоритм — это метод расчета некой величины, в данном случае Я. Саламин и Брент использовали следующие исходные равенства:
a>0 = 1; b>0 = 1/√2; t>0 = 1/4; p>0 = 1,
затем рекуррентным способом вычислили
a>n+1 = (a>n + b>n)/2;
b>n+1 = √(a>nb>n);
t>n+1 = t>n — p>n(a>n - a>n + 1)>2;
p>n+1 = 2p>n.
В пределе справедливо следующее соотношение:
π ~ (a>n + b>n)>2/4t>n.
Этот алгоритм, который было бы невозможно использовать без помощи компьютера, обладает квадратичной скоростью сходимости, то есть на каждом шаге число знаков, полученное на предыдущем, удваивается. С использованием этого алгоритма было получено 206158430000 знаков π.
Но и это еще не все: в 1980-е годы Петер и Джонатан Борвейны создали алгоритм со скоростью сходимости четвертой степени, с помощью которого было рассчитано 1241100 000 000 знаков. Мы не станем приводить его здесь, так как он будет понятен лишь узким специалистам.
ВЕЛИКОЛЕПНАЯ ЧЕТВЕРКА
Любой специалист, интересующийся вычислением я, знаком с выдающейся канадской семьей Борвейнов. Отец, Давид Борвейн (род. в 1924 году), литовец по происхождению, — известнейший математик своей страны. Он изучал многие разделы математики, особое внимание уделяя теории рядов. Его старший сын Джонатан (род. в 1951 году), автор множества книг, известных в компьютерном мире, отличается особым отношением к числу я. Он увлекается преподаванием математики и разрабатывает специальные обучающие программы. Питер (род. в 1953 году) — один из создателей формул ВВР для расчета числа я, названных так в честь их создателей — Бэйли, Борвейна и Плуффа. Он также достиг выдающихся результатов в информатике. Мать Джонатана и Питера, супруга Давида Борвейна, тоже известна в научных кругах, но не математических, а анатомических.
* * *
В конце 2002 года группа японских специалистов, возглавляемая Ясумасой Канадой, достигла результата, который теперь уже не так удивляет научный мир. Тем не менее последняя страница в этой истории еще не написана. Прогресс в этой области, кажется, не прекращается: в 2011 году был получен 10 000 000 000 050 знак числа π.
Сколь далек этот результат от предсказания Дэниела Шенкса (не путать с Уильямом Шенксом), который в 1983 году заявил, что вычисление миллиарда знаков π станет неприступной задачей! Сохраним для истории две формулы Мэчина, которые использовал Канада:
π/4 = 12∙arctg (1/49) + 32∙arctg (1/57) — 5∙arctg (1/239) + 12∙arctg (1/110443)'
π/4 = 44∙arctg (1/57) + 7∙arctg (1/239) — 12∙arctg (682) + 24∙arctg (1/12943).
Первая формула была открыта в 1982 году, а вторая была найдена Фредериком Карлом Штермером еще в 1896 году (опубликована в журнале Французского математического общества). Кто бы мог подумать, что эта формула будет использована для подобной задачи спустя столько лет! В математике никогда нельзя загадывать наперед: то, что сегодня кажется несущественным, завтра может стать основополагающим.
Возможно, помимо рекордных вычислений читателя заинтересуют не совсем традиционные вычислительные методы. Применение формулы
позволяет вычислить любой n-й знак π без необходимости рассчитывать все предыдущие. Увы, но результатом является только двоичное или шестнадцатеричное число. Формулы, подобные этой, создали Дэвид Бэйли, Питер Борвейн и Симон Плуфф. Они известны как формулы ВВР (по первым буквам фамилий их создателей). Считается, что эти формулы указывают на наступление новой эпохи в вычислениях.
Формула Фабриса Беллара (род. в 1972 году)
является производной от формул ВВР, и с ее помощью вычисления выполняются на 43 % быстрее.
При расчетах в двоичной системе находятся значения битов (0 или 1). Уже вычислен квадриллион знаков числа π. Используя эту формулу, мы можем определить, находится ли на определенной позиции 0 (возможны лишь два варианта: 0 или 1), не зная при этом предшествующих знаков. Совершенству нет предела, хотя реальная полезность подобной формулы представляется сомнительной.
