Linux вычисление числа пи

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

Вот через википедию нашёл ссылку на это — http://www.lacim.uqam.ca/

plouffe/articles/BaileyBorweinPlouffe.pdf
. но чего-то я там совсем ничего не понял( Наверное потому что на английском. Помогите плиз.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Источник

Как заставить ПК вычислить число пи максимально точно?

Привет ЛОР. Как вычислить точное число Пи? Зачем? Да интересно стало сколько его будет вычислять мой ПК (cpu точнее, расчеты на gpu не берем). В идеале хотелось бы задать много-много знаков, ну хотя бы 20к знаков числа Пи как вычислить? В программировании я ноль.

Линукс тут при том, что вычисления будут вестись в нем, ведь всем известно, что все супер-пупер компьютеры работают на Линуксе.

Его нельзя вычислить максимально точно, оно иррациональное.

Можно, если работать с системой счисления с подходящим основанием — например, с пи-ической.

Выбирай свой любимый язык программирования:

П.С. Гугл знает всё!

В идеале хотелось бы задать много-много знаков, ну хотя бы 20к знаков числа Пи как вычислить?

Прекрати прогуливать уроки. Твой учитель математики вам об этом рассказывал.

ты ноль не только в программировании.

Математику я прогуливал когда она была в школе, мне она не нравилась. А сейчас на заочке на вышмате упомянули про число Пи, вот я и задумался.

вычисляй сразу pi^e

А чем это круче чем вычисление числа Пи? Я помню что это как то связано с Эйлером.

Забавный факт. При попытке открыть в браузере файл с числом Пи вычисленным с точностью до миллиарда ПК завис. Файрфокс последний, cpu ryzen 1500x. Пишу с xiaomi.

одно трансцендентное иррациональное число в степени другого иррационального трансцендентного числа — это разве не весело?

Мда, выглядит мощно.

Так ты мазохист?

Почему ты так решил?

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

Или я что не понял.

Я вот в школе терпеть не мог только одну вещь — русский язык и литературу. Как вспомню про сочинения, аж в дрожь с тошнотой бросает. Вот бы поступил на филологический 😀

Хах, у меня наоборот. Я был самый читающий в школе, меня даже награждали за это, книгу подарили из библиотеки, лол, поэтому русский язык и литература были вообще не проблемой, я их тупо знал, даже не учил. А вот математику я быстро освоить не могу как это требовали на уроке, а дома изучать скучно было, компа и интернета к тому же не было, я просто обкладывался книгами и читал. Фантастику всегда любил, научную, про космос там, будущее.

Это инцест, если учесть, насколько эти два числа тесно связаны.

Продолжаю наблюдение. ПК так и не отвис, черный экран и курсор. Курсор еле-еле шевелится и тормозит при движении. Математика мощная штука ;).

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

Это да, но тогда было бы неясно над чем трудится ПК, глазами не увидеть.

Источник

Считаем Пи параллельно. Часть 1

В этой серии постов мы попробуем решить одну простую задачу с помощью более-менее актуальных технологий параллельного программирования (Нативные потоки, OpenMP, TBB, MPI, CUDA, OpenCL, OpenACC, Chapel может быть еще что-нить экзотическое. Как бы сравнительно и в hands-on ключе.

Чтобы все влезло в один пост (в нескольких частях) и вообще могло быть совокупно охвачено вниманием проблема была выбрана умышленно тривиальная. Поэтому многие аспекты упомянутых технологий и главное трудности которые возникают при реальном прграммировании современных массивно-параллельных систем останутся за кадром. Также не стоит пользоваться приведённым и примерами в качестве бенчмарка «GPU против CPU» или что-то в этом духе. Единственная цель — показать «как оно работает». Пост рассчитан на людей с параллельным программированием не очень знакомых. Под катом будет много кода. Собственно считать мы будем число Пи путем численного интегрирования

Исходные коды также доступны на github.com/undertherain/pi (будут пополнятся по мере написания следующих частей поста).

Последовательная версия.

Давайте для начала сделаем последовательную версию. Т.е. такую, которая использует одно ядро обычного центрального процессора. Возьмем самый простой из методов численного инетгрирования — метод прямоугольников и закодим его на языке Си (вообще дальше будем пользоваться Си\С++-ным суржиком в виду ряда причин.
Объявим некоторое количество cntSteps прямоугольников на которые мы разобъем нашу площадь под интегралом, посчитаем основание:

и всю площадь, посчитав значение функии в каждом прямоугольнике и домножив на основание.

Впрочем, домножим на основание step мы лучше «за скобками», т.е. за циклом — вот в принципе и все.

Вот полный код программы:

Native Threads

Самая, пожалуй, доступная простым пользователям параллельная архитектура — это обычный многоядерный процессор (кажется сейчас уже трудно найти процессор с одним ядром) или несколько процессоров на одной материнской плате. В принципе и одно ядро способно исполнять параллельно несоколько потоков — такой режим называется псевдо-параллельным или конкурентным. Ядро переключается между процессами (процесс — это грубо говоря находящаяся в памяти программа), выделяя каждому квант времени. В принципе такой режим выполнения уже может привести к росту производительности за счет сокрытия латентности памяти, если не на обычных «домашних» процессорах, то на специализированных многопоточных, но об этом позже. В нашем случае избыточное количество потоков привело бы к замедлению из-за накладных расходов на переключение между потоками.

Самый «исторический» способ исползьовать сразу несколько ядер на процессоре — это механизм потоков операционной системы, который сущесвовал задолго до истинно-параллельных процессоров для конкуренности хотя бы ради более удобного написания программ. С точки зрения программиста важно то, что параллельные потоки, исполняемые на разных ядрах или процессорах видят одно и то же адресное пространство, т.е нет нужды явно передавать данные между потоками. Зато если вдруг разные потоки пишут\читают одну и ту же переменную — то придётся озаботиться синхронизацией.

Ладно, давайти ближе к коду: с точки зрения языка Си поток — это обычная функция или метод класса, удовлетворяющая определённому прототипу. Давайте назовём ее static void * worker ( void * ptrArgs ) , аргументом она получает указатель на структуру, в которой можно сделать полей сколько нужно чтобы передать потоку его аргументы. В нашем случае мы скажем потоковой функии в каком диапазоне считать наш интеграл. В теле потоковой функции — уже известный нам цикл, собсно и считающий по диапазону который мы ему передали в параметрах.

Интервал интегрирования для каждого потока мы заранее вычислим изходя из его порядкового номера. Если один из потоков посчитает свою часть раньше — то соответсвующее ядро будет простаивать, т.е. мы потеряем производительность. Идеально было бы разделить интервал на много маленьих участков и раздавать потокам по мере того как они справляются со своей работой. Но пока оставим как есть.

На исполнение отдельным потоком функция запускается через системный вызов pthread_create в случае POSIX (в линуксе, например) или в случае windows этто будет аналогичный вызов из Win32 API, вуглядеть будет немного по-другому, но в целом похоже.

Результат будем из каждого потока прибавлять к общем перменной pi += sum * step ; (помним что мы находимся в общем адресном пространстве).

Чтобы память не испортилась в случае если два потока будут одновременно изменять одну ячейко нам надо как-то гарантировать что в один момент времени только один поток получает доступ к переменной pi, т.е. создать так называемую «критическую секцию». Для это можно воспользовться специальным механизмом операционной системы под названием мьютекс (от слова mutual exclusion) — если один поток заблокировал мьютекс, другой поток будет ждать (на попытке получить мьютекс самому) пока первый поток его не «освободит».

Итого выходит как-то так:

Копия на http://dumpz.org/195404/ на случай если у кото-то моё адово форматироваие неровно отображается.

На самом деле конкретно в этом примере (но так везти будет не всегда) можно было обойтись без мьютексов вообще если сохранять в каждом потоке результат в отдельную переменную (элемент массива ArgsThread arrArgsThread [ cntThreads ];
) а потом, дождавшись завершения всех потоков — просуммировать что получилось.

Вот код без мьютексов:

Как видите, код получилася довольно громоздкий и некросплатформенный. Если последнее решается отчасти с помощью boost::threads(но не все хотят ставить boost) или в новом C++11 потоки вообще стали частью языка (очень здорово вышло на самом деле) — но большая часть софта пока еще использует старый C++. Но проблема громоздкости кода всё равно остается.

OpenMP

OpenMP — это расширение языка (C/C++/Fortran) позволяющее делать примерно то же самое что мы делали с помощью API потоков операционной системы — но гораздо проще и лаконичней с помощью так называемых прагм. Прагма как бы говорит компилатору «взять вот этот код и исполнять параллельно» — и копмилятор делает все остальное.
Для распараллеливания цикла for в нашем первом последовательном примере достаточно добавить туда одну строчку:

эта прагма говорит, что нужно распараллелить витки цикла, переменную x сделать приватной для каждого потока, по переменной sum потом провести редукцию (или как это по-русски?) по суммированию. Т.е. сначала создать для каждого потока по копии — а потом их сложить. Примерно то же самое, что мы сделали в прошлом примере без мьютекосв. Также OpenMP предоставляет небольшой API для сервисных нужд.

Копия http://dumpz.org/195550/.
Компилировать с опцией -fopenmp в случае g++, с случае другого компилятора обратитесь к руководству пользователя.

Вопросы и комментарии приветсвуются, продолжение — следует!

Источник