«Краник», или алгоритм для поиска цифр числа Пи

[ZimM]

Интересно, откуда резкий скачок на 200000?

[yahorfilipcyk]

Спасибо за вопрос. Я сам в это раньше верил. Оказывается ошибка в делениях оси была, поэтому резкий скачок получился. Исправил

[lolmaus]

Википедия говорит, что spigot — это не отдельный алгоритм, а категория алгоритмов. Метафора с капающей из крана водой взята потому, что извлеченные знаки не используются (не требуются) для вычисления последующих знаков. Собственно, это и есть определение этого типа алгоритмов.

Автор использует безымянный алгоритм авторства Stan Wagon и Stanley Rabinowitz, первый из найденных «краниковых» алгоритмов для числа Пи. Этот алгоритм требует на входе указания количества знаков, которые необходимо вычислить.

Для полноты картины приведу другой алгоритм: «BBP» (назван по именам авторов: David H. Bailey, Peter Borwein и Simon Plouffe). Его уникальной особенностью является то, что он позволяет начинать вычисление с произвольного места, а не с начала. Таким образом можно за секунды вычислить любой знак числа Пи по желанию (сложность вычислений возрастает с увеличением порядкового номера знака). Этот алгоритм незаменим для проверки на верность рекордов вычисления числа пи, устанавливаемых более быстрыми алгоритмами. Алгоритм вычисляет знаки в шестнадцатеричной системе счисления. Для вычисления знаков в десятичной системе приходится переводить из шестнадцатеричной. Существуют вариации алгоритма и для других систем счисления, но только кратных двойке.

Вот тут BBP реализован на браузерном JavaScript (автор Andrew Collins). Вычисление 1'939'372-го десятичного знака на моем ноутбучном i7-3520M в Chrome заняло примерно десять секунд.

[yahorfilipcyk]

Согласен насчёт категории алгоритмов.
Есть отдельная статья Spigot algorithm на Википедии. Там упоминается, что название, судя по всему, было придумано Рабиновичем и Вэгоном.

[yahorfilipcyk]

Кстати, про «ВВР» был пост на Хабре.
Ещё есть формула Белларда, которая работает на 43% быстрее ВВР (она же является модификацией ВВР).

[Deeman]

Благодаря хабраэффекту мы помогли Эндрю Коллинзу вычислить ещё 4 тысячи знаков за один день! На что же способен целый пост, посвященный распределенным вычислениям на чьем-нибудь сервере?

[shagguboy]

а не проще было найти где нить число ПИ до энцатого знака, с запасом, а потом просто выдавать от него сколько надо?

[ZimM]

Гораздо проще. И гораздо скучнее.

[mynameco]

И написать сервис, предоставляя возможность брать всему миру из кеша уже посчитаные числа.

[Impuls]

А если так?

[domix32]

Или так

[yahorfilipcyk]

Добавил.

[Impuls]

Как-то очень медленно у Вас считается. Реализовывал когда-то в рамках лаб.работы параллельный расчет числа PI до n-цатого знака. Там все было гораздо веселее. На i3 процессоре 50 000 знаков считалось что-то около 8-ми секунд. Правда на фоне рекорда в 2.7 триллиона знков — моя программа считала бы их 13 лет (мдяяя...)

Если хотите могу дать исходник. Правда на C++ + MPI + gmp. Ууухх ну и связочка :-)

[yahorfilipcyk]

А какой Вы алгоритм использовали? Может в нём дело. Не думаю, что описанный мною алгоритм может претендовать на имя самого быстрого.

[Impuls]

Честно говоря я уже не помню. Помню что основано на расчете бесконечного ряда.

[Aivean]

длинную арифметику, которую мне реализовывать не очень-то хотелось

Вы же знаете про BigInteger, не правда ли?

[kentilini]

Многие алгоритмы по вычислению числа пи используют не целочисленную длинную арифметику, а заморачиваться с учетом количества знаков после запятой, как это делается в BigDecimal тоже не всегда удобно.

[sj314159]

Кстати, есть ли аналогичная статья в русскоязычной википедии?

[yahorfilipcyk]

Есть статьи про формулу Бэйли — Боруэйна — Плаффа (с которой нет ссылок на англоязычную версию, как и нет ссылок на русскоязычную с англоязычной), формулу Беллара ну и про само число Пи. Про «краниковые» алгоритмы — нету (не видел, по крайней мере, и прямых ссылок нету).

[jimpanzer]

Опытным путем заметил что после ввода количества знаков больше 100 000 резко падает скорость вычисления. Те. если ввожу 100, то считает мнгновенно, если ввожу 1 000 000, то теде первые 100 считает намного медленнее.
В связи с эим вопрос:
1) Это только у меня так, либо нет? Если у всех, то с чем это связано? Опять же если у всех, то второй вопрос.
2) Я так понимаю результаты на графике сделаны из одного эксперимента (с вводом 1 000 000). интересно былобы понаблюдать зависимость скорости подсчета первой тысячи относительно входных данных.

upd: AMD FX 4100, Quad 3.62. 8Gb

[jimpanzer]

Сорри, прочитал внимательнее, понял глупость своего комментария. Но

интересно былобы понаблюдать зависимость скорости подсчета первой тысячи относительно входных данных.

остается в силе. Ввести нейкую «удельную скорость» подсчета в зависимости от n.

[yahorfilipcyk]

Результаты на графике именно с разных экспериментов. Самые большие результаты как раз таки на значениях n, больших 200 000. До этого график как-то неуверенно идёт вверх.
Всё верно, скорость вычисления тех же цифр при значительном возрастании n должна падать, потому что для нахождения одной цифры нужно пройтись по массиву размером n*10 / 3. Соответственно, чем больш n, тем больше времени уходит на вычисление одной цифры.