Версия для печати темы

Автор: Vasya! 9.10.2006 20:21

Говорят, что копьютер вычислял-вычислял и вычислил (например за трое суток) 500 000 000 знаков.

А как вычисляется число Пи?

Автор: klem4 9.10.2006 20:23

А поискать не пробовал ?

http://forum.pascal.net.ru/index.php?showtopic=12884

Автор: Vasya! 9.10.2006 20:31

Это я видел. А я бы хотел понять алгоритм нахождения числа (и желательно больше 54 000).

Автор: volvo 9.10.2006 20:49

Переходи на 32 бита, где длина строки может достигать 2 Gb, и вычисляй сколько нужно знаков... В ДОС-овском Паскале ты ограничен размером сегмента, отсюда и ограничение на число символов...

Автор: Vasya! 9.10.2006 21:38

А как насчет принципа, алгоритма вычисления числа.

Автор: volvo 9.10.2006 22:22

Я же написал в теме по ссылке, что не имею понятия об алгоритме. Невнимательно читал?

Погугли на тему "BBP - Formula", "Bailey-Borwein-Plouffe Formula"... Что-нибудь да найдется

Автор: Vasya! 9.10.2006 22:28

Спасибо and sorry!!!

Автор: lapp 10.10.2006 5:59

Алгоритмов существет много разных. Самый простой и понятный - формула Лейбница:

П/4 = 1 - 1/3 + 1/5 - 1/7 + 1/9 - 1/11 + ..

Поскольку ряд знакопеременный с убывающим по модулю общим членом, то точность конечной суммы оценивается последним членом. То есть написанный выше кусок даст примерно точность до первого знака после запятой, а если нужно, например, точность до третьего знака, 0.001 (одна тысячная) , то нужно взять сумму, заканчивающуюся членом 1/1001, то есть примерно 500 членов ряда.

Извиняюсь в посте была ошибка. Сейчас исправлено (выделено зеленым цветом)

Автор: lapp 10.10.2006 10:03

Понятно, что формула Лейбница сходится очень медленно. Вот этот ряд сходится гораздо скорее:

П/(2*Sqrt(3) = 1 - (1/3)(1/3) + (1/5)(1/3)^2 - (1/7)(1/3)^3 + (1/9)(1/3)^4 - (1/11)(1/3)^5 + ...

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

Автор: Vasya! 11.10.2006 22:36

А если вычислять по формуле Лейбница, то этот процесс понятно, что долгий, но он точный?

Автор: lapp 12.10.2006 7:24

Я же написал оценку точности! Или ты думаешь, что это теория, которая типа сама по себе, а практика сама по себе?...
Повторяю: любой знакопеременный ряд с убывающим по модулю общим членом оценивается следующим образом (в предположении, что An<0, а A(n+1)>0 ) :

Sn < S < S(n+1) ,

где S - бесконечеая сумма. Вычитая из правого неравенства Sn, имеем:

S - Sn < S(n+1) - Sn = A(n+1)

Поскольку обе стороны положительны, можем поставить модули

|S - Sn| < |S(n+1) - Sn| = |A(n+1)|

Я не буду доказывать эту формулу для An>0, это практически очевидно.
Сказанное можно проиллюстрировать картинкой:

Короче, имеем следующее:
Несмотря на то, что мы не знаем бесконечной суммы и не можем ее узнать, мы можем сказать, что всякая n-ная конечная сумма отличается от нее по модулю не более, чем модуль следующего члена ряда. Иначе говоря, если мы знаем, что |An|=0.001, то для того, чтобы получить точность в одну тысячную, нам достаточно сложить n-1 членов ряда.

Теперь ясно?

Автор: Reflex 12.10.2006 10:54

есть еще алгоритм через арктангенсы как-то...

Автор: lapp 12.10.2006 11:07

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

Автор: Vasya! 17.10.2006 0:45

Огромное спасибо!!! Буду пока разбираться с тем что есть.

Кстати С Днем Рождения!!!

Автор: Vasya! 22.10.2006 16:54

Иначе говоря, если мы знаем, что |An|=0.001, то для того, чтобы получить точность в одну тысячную, нам достаточно сложить n-1 членов ряда.

Вот это не очень ясно! Пример какой-то можешь привести.

Автор: lapp 22.10.2006 18:09

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

А пример - ты, в конце концов его сам и делаешь. Так трудно закодировать несколько строк и убедиться?