Книга: Этюды для программистов

22. ? эр Квадрат, или Арифметические вычисления с высокой точностью

22.

? эр Квадрат,

или Арифметические вычисления с высокой точностью

Математику часто считают сухой наукой, однако и математику творили люди. Одной из самых печальных была судьба Уильямса Шенкса, жившего в девятнадцатом веке и посвятившего себя вычислению числа ? с высокой точностью. Закончив многолетний труд, Шенкс в 1837 г. опубликовал значение ? до 707-го десятичного знака, впоследствии исправив некоторые знаки. Может быть, надо счесть за благо, что Шенкс умер в 1882 г., поскольку в 1946 г. было показано, что его вычисления ошибочны начиная с 528-го десятичного знака. Фактически Шенкс не продвинулся дальше своих предшественников.

Полученное Шенксом значение было проверено, вероятно, с помощью механических устройств, а компьютер был впервые использован для вычисления ? только в 1949 г.; это была машина ENIAC. Даже тогда проект был монументальным. Джорж У. Рейтуиснер писал: «Поскольку получить машину в рабочее время было практически невозможно, мы воспользовались разрешением выполнить эту работу за 4 выходных дня в период летних отпусков, когда ENIAC стоял без дела». Собственно вычисления (не программирование!) заняли 70 часов: было получено несколько больше 2 000 цифр. Все это время приходилось постоянно обслуживать компьютер, поскольку из-за ограниченности его возможностей требовались постоянная перфорация и ввод промежуточных результатов. Те первые программисты так же далеки от нынешних, как Шенкс далек от них.

Как бы мы стали вычислять ?? Во-первых, необходимо выражение, которое можно вычислять. Ряд

?/4 = 1 ? 1/3 + 1/5 ? 1/7 + 1/9 ? …

довольно прост для понимания, но он ужасно медленно сходится. Гораздо лучше ряд для арктангенса

arctg x = x ? х3/3 + х5/5 ? х7/7 + …, |x| ? 1

Объединим его с формулой сложения для тангенса

tg (a + b) = (tg a + tg b)/(1 ? tg a · tg b)

и выберем а и b так, чтобы tg (a + b) = 1 = tg ?/4. (Учитывая, что tg (arctg x) = х для ??/2 < х < ?/2, можно взять, например, а = arctg (1/2), b = arctg (1/3).)

Тогда

arctg (tg (a + b)) = a + b = arctg 1 = ?/4,

и теперь можно использовать приведенный выше ряд для нахождения a и b. На практике чаще всего используются следующие суммы:

?/4 = 4 arctg (1/5) ? arctg (1/239),

?/4 = 8 arctg (1/10) ? 4 arctg (1/515) ? arctg (1/239),

?/4 = 3 arctg (1/4) + arctg (1/20) + arctg (1/1985).

Теперь мы собираемся просуммировать эти ряды на ЭВМ. Как известно, все, что нужно для суммирования, — это простой итерационный цикл, но тут возникает одна проблема. Точность вычислений на ЭВМ ограничена, а весь смысл этого упражнения в том, чтобы найти много-много цифр числа ?, значительно превзойдя обычную точность. Первое, что приходит в голову, — промоделировать ручные методы выполнения арифметических действий. Будем представлять числа очень большими целочисленными массивами (по одной десятичной цифре в каждом элементе), тогда ясно, как составить программы сложения, вычитания и умножения. Запрограммировать ручной метод деления несколько сложнее, но все же возможно. Неприемлемым, однако, оказывается время выполнения алгоритмов. Хотя на это редко обращают внимание, но при ручных методах для умножения или деления n-значных чисел требуется время, пропорциональное n?. Если речь идет об операциях над числами из тысяч цифр, то такие расходы будут нам не по карману. К счастью, имеются лучшие алгоритмы.

Оглавление книги