все то же pi

From

Evgenij Masherov (2:5020/175.2)

To

Илья Кантор

Date

2002-11-06T13:14:21Z

Area

RU.ALGORITHMS

From: "Evgenij Masherov" <EMasherow@nsi.ru>

Tue Nov 05 2002 21:04, Илья Кантор wrote to Mike Kolesoff:

 MK>> Хочу узнать pi с точностью до миллиарда... просто интересно.

 ИК> Ок. Дело в том, что вычисление pi до 50000 знака и до миллиардного
 ИК> принципиально различаются. 
 ИК> Самые лучшие формулы для этого - видимо, формула Чудновского и
 ИК> модифицированное арифметико-геометрическое сечение. Однако для миллиарда
 ИК> знаков тебе нужно реализовать умножение длинных чисел через
 ИК> теоретико-числовое преобразование, причем с кучей фишек для того, чтобы
 ИК> оно давало терпимый результат, а деление - методом Ньютона-Рафсона с
 ИК> улучшениями Карпа(тут можно не так стараться - оно 1 раз делается).

 ИК> Оперативной памяти тебе на все не хватит(преобразования производятся не
 ИК> "на месте"), поэтому придется изрядно потрахаться с выполнением
 ИК> преобразований при участии диска.

 ИК> Возможно, некоторые термины и не совсем понятны, поэтому скажем просто -
 ИК> задачка не из тривиальных ;)

 ИК> Ты ДЕЙСТВИТЕЛЬНО готов это все проделать ? ;))

Ну, давайте по пунктам...
Если брать классическое разложение арктангенса, 
Pi/4=4*arctg(1/5)-arctg(1/239)
arctg(x)=x-x^3/3+x^5/5-x^7/7
то нужно уметь делать две операции. Сложение длинных чисел и деление длинных
чисел на обычные. И то, и другое делается достаточно просто. Для миллиарда
знаков потребуется (скажем, при 4-х десятичных на 2 байта - можно и плотнее)
500 Мбайт памяти на вектор (нужно три, но можно обойтись и двумя...). Т.е.
можно писать в ОП, надеясь, что ОС отображение на виртуальную будет само
мерять (было бы что мерять!).
Не нужно здесь ни длинное-на-длинное умножение, ни длинное деление.

Евгений Машеров АКА СанитарЖеня

--- ifmail v.2.15dev5
 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)