|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Evgenij Masherov 2:5020/175.2 06 Nov 2002 14:14:21
To : €«мп Љ в®а
Subject : все то же pi
--------------------------------------------------------------------------------
Tue Nov 05 2002 21:04, Илья Кантор wrote to Mike Kolesoff:
MK>> Хочу узнать pi с точностью до миллиарда... просто интересно.
ИК> Ок. Дело в том, что вычисление pi до 50000 знака и до миллиардного
ИК> принципиально различаются.
ИК> Самые лучшие формулы для этого - видимо, формула Чудновского и
ИК> модифицированное арифметико-геометрическое сечение. Однако для миллиарда
ИК> знаков тебе нужно реализовать умножение длинных чисел через
ИК> теоретико-числовое преобразование, причем с кучей фишек для того, чтобы
ИК> оно давало терпимый результат, а деление - методом Hьютона-Рафсона с
ИК> улучшениями Карпа(тут можно не так стараться - оно 1 раз делается).
ИК> Оперативной памяти тебе на все не хватит(преобразования производятся не
ИК> "на месте"), поэтому придется изрядно потрахаться с выполнением
ИК> преобразований при участии диска.
ИК> Возможно, некоторые термины и не совсем понятны, поэтому скажем просто -
ИК> задачка не из тривиальных ;)
ИК> Ты ДЕЙСТВИТЕЛЬHО готов это все проделать ? ;))
Hу, давайте по пунктам...
Если брать классическое разложение арктангенса,
Pi/4=4*arctg(1/5)-arctg(1/239)
arctg(x)=x-x^3/3+x^5/5-x^7/7
то нужно уметь делать две операции. Сложение длинных чисел и деление длинных
чисел на обычные. И то, и другое делается достаточно просто. Для миллиарда
знаков потребуется (скажем, при 4-х десятичных на 2 байта - можно и плотнее)
500 Мбайт памяти на вектор (нужно три, но можно обойтись и двумя...). Т.е.
можно писать в ОП, надеясь, что ОС отображение на виртуальную будет само
мерять (было бы что мерять!).
Hе нужно здесь ни длинное-на-длинное умножение, ни длинное деление.
Евгений Машеров АКА СанитарЖеня
--- ifmail v.2.15dev5
* Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
