Как быстро вычислить произвольную цифру числа Pi?

самое быстрое это:

1 вычисть число до компиляции

2 положить каждую цифру в отдельную ячейку массива

3 далее вычисляем любую цифру методом: цыфра = PI[номерЦыфры];

итоговая трудоемкость: O(N) где N это колличество нужных цифр

а какая цыфга вам нужна?

Нет... ну это конечно хорошо, а если мне надо знать например 1ю...50ю.. и 3х-милионную цифру, создавать для этого массив... кароче нужно именно вычислять :)

Берешь gmp и вычисляешь pi с необходимой тебе точностью, юзая для этого ряд Лейбница. Хотя я сомневаюсь, конечно, что это быстро. =]

http://elephant.linux.net.cn/articles/pi.php

Вообще говоря, никак!

Бейли в статье по ссылке говорит, что почти все верят, что вычисление очередной цифры не проще чем вычисление всех предыдущих, но им _вроде бы_ удалось построить подходящий алгоритм, который они доказать не могут, но численно оно пока работает. Причем, сложность их алгоритма не лучше, чем у известных, но он не требует арифметики произвольной точности.

Вообще, Бейли -- признанный эксперт в этой области, ему можно верить.

отсюда бери: http://aaaq.ru/pi.html

Так как пи всё же константа, можно его один раз посчитать(до максимально нужной точности), и хранить в программе как строку, беря, при необходимости лишь нужную часть. Всё же, точность выше 10000 знаков после запятой вряд-ли нужна даже для запуска межзвёздных кораблей. :)

Вообще-то, помню, была формула, позволяющая вычислить нужную цифру.

> Вообще-то, помню, была формула, позволяющая вычислить нужную цифру.

Это хорошо. Не напомните, с какого знака в числе PI "Воина и мир" в koi8-r начинается?

>Вообще говоря, никак!

В десятичной [вроде], никак.

А вот в 16-ричной, как ни парадоксально, несколько лет назад вывели формулу по вычислению n-й цифры :) Пруфлинк искать влом, но формулу видел.

>> Вообще-то, помню, была формула, позволяющая вычислить нужную цифру.

> Это хорошо. Не напомните, с какого знака в числе PI "Воина и мир" в koi8-r начинается?

- Я знаю метод, как узнать, какой жилец проживает в заданной квартире [например, позвонить в звонок и спросить].

- Не подскажите, в какой квартире живёт Иванов П.С.?

wget http://3.141592 (штук 30 цифр).jp | perl -e "print $_[$n]";

> А вот в 16-ричной, как ни парадоксально, несколько лет назад вывели формулу по вычислению n-й цифры :) Пруфлинк искать влом, но формулу видел.

Топикстартер САМ и приводит тот пруфлинк! Это был Бейли с коллегами.

Еще раз:

1. Там не формула, там алгоритм, причем НЕ доказанный. Хотя нынче все в него верят. Алгоритм довольно простой и основывается на открытой ими формуле представления числа Пи, т.н. BBP формуле.

Вот, со страницы Бейли http://crd.lbl.gov/~dhbailey/ :

In 1996, Peter Borwein (brother of Jonathan Borwein), Simon Plouffe and I co-authored a paper that presents a new formula for pi... This formula, now known as the "BBP formula for pi", permits one to compute the n-th binary or hexadecimal digit of pi, without computing the first n-1 digits, by means of a simple scheme that requires very little memory. It was discovered by Simon Plouffe using a computer program of mine that implements Helaman Ferguson's "PSLQ" algorithm.

2. Сложность этого алгоритма (по времени) не ниже уже известных алгоритмов вычисления всех n цифр, но по пространству он очень эффективен.

> В десятичной [вроде], никак.

Бейли утверждает, что недавно было доказано, что не существует подобной BBP формулы для степеней счисления, отличных от n = 2^m. http://indico.cern.ch/materialDisplay.py?contribId=166&sessionId=23&m... страница 14

>Берешь gmp и вычисляешь pi с необходимой тебе точностью, юзая для этого ряд Лейбница. Хотя я сомневаюсь, конечно, что это быстро. =]

Это один из самых тормозных методов, существуют ряды, которые сходятся значительно быстрее.

>> 3 далее вычисляем любую цифру методом: цыфра = PI[номерЦыфры];
>> итоговая трудоемкость: O(N) где N это колличество нужных цифр

А разве не O(1)?

>А разве не O(1)?

O(1) это если тебе нужно одну цыфру постчитать. А если например тебе нужно первую вторую и пяти тысячную получится O(3), все будет зависеть от скорости индексации в массиве и колличества нужных тебе цыфр.

> получится O(3)

/me тихо сполз под стол =]

пушистый умир в припадке хохота

>> O(1) это если тебе нужно одну цыфру постчитать. А если например тебе нужно первую вторую и пяти тысячную получится O(3), все будет зависеть от скорости индексации в массиве и колличества нужных тебе цыфр.

Эм... Скорость доступа к произвольному элементу обычного линейного массива - O(1), так как реализуется сложением и доступом по адресу. В определённых случаях это одна ассемблерная операция (на x86).

> ...А если например тебе нужно первую вторую и пяти тысячную получится O(3), ...

Честное слово, O(1) == O(3) == O(1000000000000000000000000) ....

O(1) = O(3)
O(1) = 3*O(1)
1 = 3

Ох, черт.