Приближение числа Пи в виде отношения двух натуральных чисел

[Nadir Zaitov]

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

Предлагаю тут написать алгоритм как это сделать без использования длинных циклов. Все циклы (или итерации испольльзования одного и того же кода) не должны превосходить по длинне число знаков в искомых натуральных числах. Ясно, что использовать вложенные циклы тоже нельзя.

Предполагается, что число Pi нам известно точно.

ЦУ. Кстати, такое приближение (в виде двух дробей) использовалось в часовых механизмах, и вообще в точной механике весьма своеобразно.

[Evgeniy Sklyarevskiy]

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


Так в Древней Греции вскоре после Архимеда было получено более точное приближение к числу "пи" - 355/113. ( http://arbuz.uz/x_pi.html )

[Nadir Zaitov]

Да мне все равно. Сколько влезит в разряд длинного целого числа.
Например, пара 80 143 857 и 25 510 582 дает точность в 16 знаков и получена на 13-й итерации за доли секунды и это уже предел для действительных чисел двойной точности. Дальнейшие изыскания (в Excel) мне ничего не дали - так как точность введенного в Excel числа "Пи" ниже :).

[Nadir Zaitov]

ЦУ (2): число Пи разлагается в цепную дробь так:

π = [3; 7, 15, 1, 292, 1, 1, 1, 2, 1, 3, 1, 14, 2, 1, 1, 2, 2, 2, 2, 1, 84, 2, 1, 1, 15,…]

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

Я тут подсчитал, что указанных цифр достаточно, чтобы получить точночть в 27 знаков.

[Georgick]

Предполагается, что число Pi нам известно точно.

80 143 857 и 25 510 582 дает точность в 16 знаков


Да, пожалуйста - вам выше точность в виде дроби (31 знак)

31415926535897932384626433832795/10000000000000000000000000000000

могу и больше дать по этой формуле :)

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

[Shuhrat Ismailov]

Предлагаю тут написать алгоритм как это сделать без использования длинных циклов. Все циклы (или итерации испольльзования одного и того же кода) не должны превосходить по длинне число знаков в искомых натуральных числах. Ясно, что использовать вложенные циклы тоже нельзя.
Откопал небольшой обзор (http://www.levvol.ru/ar41.php) об истории проблемы, содержит результат 2010 года.

Француз Фабрис Беллар вычислил число Пи с рекордной точностью. Об этом сообщается на его официальном сайте. Новый рекорд составляет около 2,7 триллиона (2 триллиона 699 миллиардов 999 миллионов 990 тысяч) десятичных знаков. Предыдущее достижение принадлежит японским ученым, которые посчитали константу с точностью до 2,6 триллиона десятичных знаков. Беллар потратил на вычисления около 103 дней.

Евгений Семенович, там написано, что приближение к числу "пи" - 355/113 получено в Китае. Почему?

[Shuhrat Ismailov]

ЦУ. Кстати, такое приближение (в виде двух дробей) использовалось в часовых механизмах, и вообще в точной механике весьма своеобразно.
Например, так?
https://img.uforum.uz/images/trijnny8796659.jpg

[Evgeniy Sklyarevskiy]

Евгений Семенович, там написано, что приближение к числу "пи" - 355/113 получено в Китае. Почему? Раньше Древняя Греция и Древний Китай были ближе друг у другу и часто обменивались значениями числа Пи в рамках культурного обмена.

[Nadir Zaitov]

31415926535897932384626433832795/10000000000000000000000000000000Хорошо. Оптимизировать нужно по числу знаков. Более формально нужно найти такие натуральне числа A и B. Чтобы |A/B-π|<=|M/N-π| для всех N<=B<=1 000 000 000 000 000
Такого разряда числа и дадут вам точность в частном в 30-31 знак.

[Rooslan Khayrov]

Ну, собственно, задавшись значением π с точностью до 50-го знака после запятой из Википедии, и имея в распоряжении длинную арифметику…

Вот программка, которая печатает последовательные приближения вместе с погрешностями:
import Data.Ratio

rationalPi = 31415926535897932384626433832795028841971693993751 0 % (10^50)

contFrac [x] = x
contFrac (x:xs) = x + 1 / contFrac xs

next x = 1 / frac x where frac x = x - realToFrac (floor x)

chain = map floor $ iterate next rationalPi

approx n = contFrac $ map toRational $ take n chain

maxDenom = 10^15

answer = takeWhile ((< maxDenom) . denominator) [approx n | n <- [1..]]

main = mapM_ print $ map (\x -> (x, abs $ realToFrac $ x - rationalPi)) answer
Вот вывод:
(3 % 1,0.14159265358979323)
(22 % 7,1.2644892673496187e-3)
(333 % 106,8.321962752908752e-5)
(355 % 113,2.667641890624223e-7)
(103993 % 33102,5.778906343903818e-10)
(104348 % 33215,3.3162780624607254e-10)
(208341 % 66317,1.223565329421886e-10)
(312689 % 99532,2.914338493485692e-11)
(833719 % 265381,8.715467258224077e-12)
(1146408 % 364913,1.6107400198990309e-12)
(4272943 % 1360120,4.040669189560616e-13)
(5419351 % 1725033,2.2144779300394028e-14)
(80143857 % 25510582,5.790870164375673e-16)
(165707065 % 52746197,1.6408351553695507e-16)
(245850922 % 78256779,7.817936619907544e-17)
(411557987 % 131002976,1.9363804773134898e-17)
(1068966896 % 340262731,3.0700784537985835e-18)
(2549491779 % 811528438,5.513663759200879e-19)
(6167950454 % 1963319607,7.626587688912332e-20)
(14885392687 % 4738167652,3.123167473205774e-20)
(21053343141 % 6701487259,2.616405046338706e-22)
(1783366216531 % 567663097408,1.2277497763340362e-24)
(3587785776203 % 1142027682075,3.1477698144543726e-25)
(5371151992734 % 1709690779483,1.9738318673456688e-25)
(8958937768937 % 2851718461558,7.721593980075975e-27)
(139755218526789 % 44485467702853,1.6110953015863004e-28)
(428224593349304 % 136308121570117,3.8054497280286666e-30)
Отрабатывает за сотые доли секунды.

[Nadir Zaitov]

Отрабатывает за сотые доли секунды. Так и должна работать сотые доли секунды. Спасибо.

[Наташа]

Ну, собственно, задавшись значением π с точностью до 50-го знака после запятой из Википедии, и имея в распоряжении длинную арифметику… Видимо, здесь что то интересное, но к сожалению совершенно не понимаю, того, что здесь написано...:) -для меня это просто абра-кадабра получилась:) -а нельзя ли как нибудь попроще написать, например в виде блок-схем?:)

[Rooslan Khayrov]

Видимо, здесь что то интересное, но к сожалению совершенно не понимаю, того, что здесь написано...:) -для меня это просто абра-кадабра получилась:) -а нельзя ли как нибудь попроще написать, например в виде блок-схем?:)
Это дословное переложение алгоритма, на который намекнул Надир Заитов. Сначала раскладываем Пи в цепную дробь по простой рекуррентной формуле:
http://latex.codecogs.com/gif.latex?\pi&space;=&space;x_0&space;&plus;&space;\frac{1}{x_1&space;&plus;&space;\frac{1}{x_2&space; &plus;&space;\ldots}}
http://latex.codecogs.com/gif.latex?x_n&space;=&space;\lfloor&space;y_n&space;\rfloor
http://latex.codecogs.com/gif.latex?y_{n&space;&plus;&space;1}&space;=&space;\frac{1}{\{y_n\}},&space;y_0&space;=&space;\pi
Соответствующий участок кода:
next x = 1 / frac x where frac x = x - realToFrac (floor x)

chain = map floor $ iterate next rationalPi
Семантика встроенных функций:
iterate f x0 = [x0; f(x0); f(f(x0); f(f(f(x0))); ...]
map f [x0; x1; x2; ...; xn] = [f(x0); f(x1); f(x2); ...; f(xn)]
Таким образом, chain — потенциально бесконечный список, но поскольку вычисляется он лениво (только та часть, которая нам понадобится), беспокоиться не о чем.
Дальше мы просто вычисляем последовательные приближения получившейся цепной дроби. У нас есть тип рациональных чисел (из модуля Data.Ratio), в котором и в числителе и в знаменателе используется длинная арифметика, так что потери точности не происходит. Функция вычисления конечной цепной дроби:
contFrac [x] = x
contFrac (x:xs) = x + 1 / contFrac xs
Следующая функция вычисляет n-ю подходящую дробь:
approx n = contFrac $ map toRational $ take n chain
Потом мы выбираем значения из списка последовательных приближений до тех пор, пока знаменатель не превысит заданное значение.
answer = takeWhile ((< maxDenom) . denominator) [approx n | n <- [1..]]
Оператор точка (.) означает композицию функций. Если h = f . g, то h(x) = f(g(x)).
А это просто вывод:
main = mapM_ print $ map (\x -> (x, abs $ realToFrac $ x - rationalPi)) answer
Ах да, язык Haskell называется :-)

[Shuhrat Ismailov]

Сначала раскладываем Пи в цепную дробь по простой рекуррентной формуле:
Обратите внимание, как Руслан использовал сервис по latex
http://www.codecogs.com
и красиво формулы оформил. Примечательно, что каратинка-формула при этом нигде не сохраняется.
Нестандартный для юфорума ход!

[Nadir Zaitov]

Обратите внимание, как Руслан использовал сервис по latex Здорово. Я даже не сразу заметил это. И как это делается? В двух словах расскажите?

[Rooslan Khayrov]

Nadir Zaitov, идёте сюда: http://www.codecogs.com/latex/eqneditor.php
Пишете форумулу в поле, получаете превьюшку и URL картинки для вставки. Даже те, кто не знает LaTeX, пожалуй, смогут что-то набрать, пользуясь панелью инструментов.