Comments 23
Интересно, откуда резкий скачок на 200000?
+1
Википедия говорит, что spigot — это не отдельный алгоритм, а категория алгоритмов. Метафора с капающей из крана водой взята потому, что извлеченные знаки не используются (не требуются) для вычисления последующих знаков. Собственно, это и есть определение этого типа алгоритмов.
Автор использует безымянный алгоритм авторства Stan Wagon и Stanley Rabinowitz, первый из найденных «краниковых» алгоритмов для числа Пи. Этот алгоритм требует на входе указания количества знаков, которые необходимо вычислить.
Для полноты картины приведу другой алгоритм: «BBP» (назван по именам авторов: David H. Bailey, Peter Borwein и Simon Plouffe). Его уникальной особенностью является то, что он позволяет начинать вычисление с произвольного места, а не с начала. Таким образом можно за секунды вычислить любой знак числа Пи по желанию (сложность вычислений возрастает с увеличением порядкового номера знака). Этот алгоритм незаменим для проверки на верность рекордов вычисления числа пи, устанавливаемых более быстрыми алгоритмами. Алгоритм вычисляет знаки в шестнадцатеричной системе счисления. Для вычисления знаков в десятичной системе приходится переводить из шестнадцатеричной. Существуют вариации алгоритма и для других систем счисления, но только кратных двойке.
Вот тут BBP реализован на браузерном JavaScript (автор Andrew Collins). Вычисление 1'939'372-го десятичного знака на моем ноутбучном i7-3520M в Chrome заняло примерно десять секунд.
Автор использует безымянный алгоритм авторства Stan Wagon и Stanley Rabinowitz, первый из найденных «краниковых» алгоритмов для числа Пи. Этот алгоритм требует на входе указания количества знаков, которые необходимо вычислить.
Для полноты картины приведу другой алгоритм: «BBP» (назван по именам авторов: David H. Bailey, Peter Borwein и Simon Plouffe). Его уникальной особенностью является то, что он позволяет начинать вычисление с произвольного места, а не с начала. Таким образом можно за секунды вычислить любой знак числа Пи по желанию (сложность вычислений возрастает с увеличением порядкового номера знака). Этот алгоритм незаменим для проверки на верность рекордов вычисления числа пи, устанавливаемых более быстрыми алгоритмами. Алгоритм вычисляет знаки в шестнадцатеричной системе счисления. Для вычисления знаков в десятичной системе приходится переводить из шестнадцатеричной. Существуют вариации алгоритма и для других систем счисления, но только кратных двойке.
Вот тут BBP реализован на браузерном JavaScript (автор Andrew Collins). Вычисление 1'939'372-го десятичного знака на моем ноутбучном i7-3520M в Chrome заняло примерно десять секунд.
+8
Согласен насчёт категории алгоритмов.
Есть отдельная статья Spigot algorithm на Википедии. Там упоминается, что название, судя по всему, было придумано Рабиновичем и Вэгоном.
Есть отдельная статья Spigot algorithm на Википедии. Там упоминается, что название, судя по всему, было придумано Рабиновичем и Вэгоном.
+1
Кстати, про «ВВР» был пост на Хабре.
Ещё есть формула Белларда, которая работает на 43% быстрее ВВР (она же является модификацией ВВР).
Ещё есть формула Белларда, которая работает на 43% быстрее ВВР (она же является модификацией ВВР).
+4
Благодаря хабраэффекту мы помогли Эндрю Коллинзу вычислить ещё 4 тысячи знаков за один день! На что же способен целый пост, посвященный распределенным вычислениям на чьем-нибудь сервере?
+3
а не проще было найти где нить число ПИ до энцатого знака, с запасом, а потом просто выдавать от него сколько надо?
+5
UFO just landed and posted this here
Как-то очень медленно у Вас считается. Реализовывал когда-то в рамках лаб.работы параллельный расчет числа PI до n-цатого знака. Там все было гораздо веселее. На i3 процессоре 50 000 знаков считалось что-то около 8-ми секунд. Правда на фоне рекорда в 2.7 триллиона знков — моя программа считала бы их 13 лет (мдяяя...)
Если хотите могу дать исходник. Правда на C++ + MPI + gmp. Ууухх ну и связочка :-)
Если хотите могу дать исходник. Правда на C++ + MPI + gmp. Ууухх ну и связочка :-)
0
длинную арифметику, которую мне реализовывать не очень-то хотелось
Вы же знаете про BigInteger, не правда ли?
0
Кстати, есть ли аналогичная статья в русскоязычной википедии?
0
Есть статьи про формулу Бэйли — Боруэйна — Плаффа (с которой нет ссылок на англоязычную версию, как и нет ссылок на русскоязычную с англоязычной), формулу Беллара ну и про само число Пи. Про «краниковые» алгоритмы — нету (не видел, по крайней мере, и прямых ссылок нету).
+1
Опытным путем заметил что после ввода количества знаков больше 100 000 резко падает скорость вычисления. Те. если ввожу 100, то считает мнгновенно, если ввожу 1 000 000, то теде первые 100 считает намного медленнее.
В связи с эим вопрос:
1) Это только у меня так, либо нет? Если у всех, то с чем это связано? Опять же если у всех, то второй вопрос.
2) Я так понимаю результаты на графике сделаны из одного эксперимента (с вводом 1 000 000). интересно былобы понаблюдать зависимость скорости подсчета первой тысячи относительно входных данных.
upd: AMD FX 4100, Quad 3.62. 8Gb
В связи с эим вопрос:
1) Это только у меня так, либо нет? Если у всех, то с чем это связано? Опять же если у всех, то второй вопрос.
2) Я так понимаю результаты на графике сделаны из одного эксперимента (с вводом 1 000 000). интересно былобы понаблюдать зависимость скорости подсчета первой тысячи относительно входных данных.
upd: AMD FX 4100, Quad 3.62. 8Gb
0
Сорри, прочитал внимательнее, понял глупость своего комментария. Но
интересно былобы понаблюдать зависимость скорости подсчета первой тысячи относительно входных данных.остается в силе. Ввести нейкую «удельную скорость» подсчета в зависимости от n.
0
Результаты на графике именно с разных экспериментов. Самые большие результаты как раз таки на значениях n, больших 200 000. До этого график как-то неуверенно идёт вверх.
Всё верно, скорость вычисления тех же цифр при значительном возрастании n должна падать, потому что для нахождения одной цифры нужно пройтись по массиву размером n*10 / 3. Соответственно, чем больш n, тем больше времени уходит на вычисление одной цифры.
Всё верно, скорость вычисления тех же цифр при значительном возрастании n должна падать, потому что для нахождения одной цифры нужно пройтись по массиву размером n*10 / 3. Соответственно, чем больш n, тем больше времени уходит на вычисление одной цифры.
0
Sign up to leave a comment.
«Краник», или алгоритм для поиска цифр числа Пи