Approximate pi with rational numbers

Asked Mar 07 '17 at 04:26

Active Mar 07 '17 at 04:33

Viewed 307 times

The value of pi = 3.1415926535... can approximate pi with rational numbers like this:

22/7 = 3.142857142857...
355/113 = 3.141592920353...

I want to construct more accurate fractions, so:
Please tell me the fast algorithm of finding integers p, q (1 <= q <= n) such p/q is nearest to pi.

I only have a brute-force algorithm and it takes O(n) to find it, so it is slow for n <= 10^12.

Do you have any efficient algorithm?

EDIT:
Different from this question because I already know the value of pi and I only want to construct the most accurate fraction that denominator is less or equal to n.

edited May 23 '17 at 11:46

Community

asked Mar 07 '17 at 04:26

square1001

1,402
11
26

Try this: http://stackoverflow.com/questions/19/what-is-the-fastest-way-to-get-the-value-of-%CF%80 – パスカル Mar 07 '17 at 04:29
See http://blog.wolfram.com/2011/06/30/all-rational-approximations-of-pi-are-useless/ – Mankarse Mar 07 '17 at 04:29
@PascalDescollonges please read my question. – square1001 Mar 07 '17 at 04:30
@Mankarse I read this before asking question, but there is not written ALGORITHM of finding them. – square1001 Mar 07 '17 at 04:32
Look at jon-hanson and nulcaroni's answers. They both have algorithms. – パスカル Mar 07 '17 at 04:39
@PascalDescollonges But it includes irrational numbers. – square1001 Mar 07 '17 at 04:41
Look at the first algorithm in nlucaroni's answer. I do not see any irrationals. – パスカル Mar 07 '17 at 04:44
@PascalDescollonges Look at my question. You are given an integer n, and you have to find the fraction that denominator <= n. So, if n=100, the answer is p=311 and q=99 because it is nearest for all over p, q such that 1 <= q <= n. – square1001 Mar 07 '17 at 04:48
There are lists and formulae available here: http://oeis.org/search?q=convergents+to+pi – r3mainer Mar 07 '17 at 10:22

Approximate pi with rational numbers

0 Answers0