Помогите понять алгоритм вычисления Пи

[Alexu007]

Здравствуйте.

Есть программа, написанная Диком Т. Винтером (Dik T. Winter at CWI) на Си всего 160-ю символами, но вычисляющая 800 знаков Пи, вот оригинал ее текста:

int a=10000,b,c=2800,d,e,f[2801],g;main(){for(;b-c;)f[b++]=a/5; for(;d=0,g=c*2;c-=14,printf("%.4d",e+d/a),e=d%a)for(b=c;d+=f[b]*a, f[b]=d%--g,d/=g--,--b;d*=b);}

в таком виде мало что понятно, я переписал в более доступной форме:

int a = 10000;
int b = 0;
int c = 2800;
int d = 0;
int e = 0;
int f[2801];
int g = 0;


int main()
{

//заполняет массив значением à/5 = 2000
for (b = 0; b < c; b++) f[b] = a/5;

   //цикл вычислений
   while (g = c * 2)
     {
     d = 0;

     for (b = c; b > 1; b--)
       {
       d += f[b] * a;

       --g; f[b] = d % g;

       d /= g; g--;

       d *= b;
       }
    
     //выводит на экран по 4 цифры, например: 3141
     printf("%.4d", e + d/a);

     c -= 14;
     e = d % a;
     }

getch();
return 0;
} 

Программа работает и за время менее секунды вычисляет все свои положенные 800 знаков:



Если кто может, объясните, на чем основан принцип действия данного алгоритма, какой у него физический смысл - почему он вообще вычисляет Пи, почему именно 800 знаков, а не 1000 например и т.д.

[Padawan]

В ряд поди какой-нибудь раскладывает

[Alexu007]

Если вы имеете ввиду: Pi/4 = 1 - 1/3 + 1/5 - 1/7 + 1/9...и так далее до бесконечности, то ошибаетесь. Этот алгоритм медленный, на вычисление каждого следующего знака затрачивается в 10 раз больше вычислительных ресурсов. Вычисление с точностью до 6-го знака на моем компьютере занимает около 3 сек, до 7 - 30, до 8 - 300 и так далее.

[Padawan]

нет, я имею ввиду какой-нибудь другой ряд. А их можно придумать кучу, и быстро сходящихся тоже. Может даже и не сходящийся ряд, а обертывающий. Т.е. ряд расходится, но конечный отрезок этого ряда дает хорошее приближениее для $\pi$. Надо смотреть существующие методы вычисления числа $\pi$.

[Maslov]

Судя по всему, это что-то из spigot-вариаций:

$\pi = 2 + \dfrac 1 3 \cdot (2 + \dfrac 2 5 \cdot (2 + \dfrac 3 7 \cdot (...)))$

Вот здесь можно посмотреть: http://www.matpack.de/Info/Mathematics/Pi.html
Или здесь: http://www.mathpropress.com/stan/biblio ... spigot.pdf

[Padawan]

Посмотрел в википедии [url]http://ru.wikipedia.org/wiki/Пи_(число)[/url]

Оказывается,

Цитата:

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

[venco]

Я такой использовал лет 15 назад, чтобы посчитать 10 миллионов знаков:
http://en.wikipedia.org/wiki/Gauss%E2%80%93Legendre_algorithm

[Профессор Снэйп]

Где-то тут была на форуме тема про вычисление $\pi$. Правда, не помню где. Там на несколько страниц обсуждение.

[Alexu007]

Синусы, косинусы, корни и дроби наверное отпадают - программа работает только с целыми числами.

Очевидно это программная реализация какой-нибудь хитрой математической формулы.

Пи - геометрическая константа, должны ли алгоритмы вычисления Пи иметь наглядное геометрическое объяснение?

[Виктор Ширшов]

Alexu007 в сообщении #295570 писал(а):

Есть программа, написанная Диком Т. Винтером (Dik T. Winter at CWI) на Си всего 160-ю символами, но вычисляющая 800 знаков Пи, вот оригинал ее текста:

venco в сообщении #295613 писал(а):

Я такой использовал лет 15 назад, чтобы посчитать 10 миллионов знаков:

А собственно зачем, если для математических расчётов, достаточно 3,1416.
Но если Вам интересно, можете заодно подсчитать и "перевёрнутую" пропорцию (1/∏) американского математика Джона Паркера, который был хорошо известен в научных кругах и среди любителей оккультных наук во второй половине XIX столетия. "Перевёрнутая" пропорция для шотландского королевского астронома Пиацци Смита была основой для измерений пирамиды Хеопса, при которых он сделал ряд «открытий» соотносительного характера. «Пропорция Паркера» равняется 6561 к 20612 или 0.3183… По моему, программу этого ряда ещё никто не написал. Может быть, он будет короче.
Однако известность Д. Паркеру принесла не эта пропорция, а его математические взгляды, навязывавшие культ круга. О математических пристрастиях Паркера я узнал из книги Е.П. Блаватской «Тайная доктрина», где нашёл несколько интересных теорем математика.

[AD]

(оффтоп: а еще вот так можно ...)

Используется синтаксис C

#define _ -F<00||--F-OO--;
int F=00,OO=00;main&#40;&#41;{F_OO&#40;&#41;;printf&#40;"%1.3f\n",4.*-F/OO/OO&#41;;}F_OO&#40;&#41;
{
            _-_-_-_
       _-_-_-_-_-_-_-_-_
    _-_-_-_-_-_-_-_-_-_-_-_
  _-_-_-_-_-_-_-_-_-_-_-_-_-_
 _-_-_-_-_-_-_-_-_-_-_-_-_-_-_
 _-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
 _-_-_-_-_-_-_-_-_-_-_-_-_-_-_
 _-_-_-_-_-_-_-_-_-_-_-_-_-_-_
  _-_-_-_-_-_-_-_-_-_-_-_-_-_
    _-_-_-_-_-_-_-_-_-_-_-_
        _-_-_-_-_-_-_-_
            _-_-_-_
}

[Alexu007]

Виктор Ширшов в сообщении #295986 писал(а):

А собственно зачем, если для математических расчётов, достаточно 3,1416.

Да я понимаю, что практического смысла в этом нет. Мне интересно другое, почему в результате неких манипуляций с цифрами получается Пи? Понятно, что так программист Винтер придумал, но должно быть и какое-то физическое или геометрическое объяснение. Например, если мы используем ряд 1-1/3+1/5-1/7..., то мы берем квадрат, в который вписан круг, отнимаем пятиугольник прибавляем шестиугольник и так далее все ближе и ближе к кругу. Чем больше углов в многоугольнике - тем ближе к кругу и соответственно с большей точностью вычисляется Пи. Программа Винтера явно работает по другому принципу.

Если можно вычислить Пи практически с любой точностью, то можно ли сделать то же с другой константой, например вычислить постоянную Планка или постоянную тонкой материи - или Пи является исключением?

[faruk]

Alexu007 в сообщении #296025 писал(а):

Если можно вычислить Пи практически с любой точностью, то можно ли сделать то же с другой константой, например вычислить постоянную Планка или постоянную тонкой материи - или Пи является исключением?

Пи – это число. "Вычисление числа Пи" – это не что иное, как попытка записать это число с помощью цифр.

Постоянная Планка – это физическая величина. http://www.rfbr.ru/default.asp?doc_id=4508

[Alexu007]

Разве пи - не физическая величина: отношение длинны окружности к диаметру?

[faruk]

Alexu007 в сообщении #296054 писал(а):

Разве пи - не физическая величина: отношение длинны окружности к диаметру?

Это отношение длины окружности к диаметру, но это не физическая величина. Нам не нужно чертить на бумаге круг и замерять длину окружности.

Хотя, конечно, всё зависит от терминологии – что считать физической величиной.

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

http://en.wikipedia.org/wiki/Mathematical_constant
http://en.wikipedia.org/wiki/Physical_constant

Мировые константы пи и е в основных законах физики и физиологии:
http://www.arbuz.uz/t_e_pi.html



Кстати, как, исходя из того, что $\pi$ – это отношение длины окружности к диаметру, объяснить следующее равенство:
$\int_{-\infty}^\infty e^{-x^2}\,dx = \sqrt{\pi}$ ?