method float.as_integer_ratio() always ...

[Skaperen]

method float.as_integer_ratio() always gives a power of two for the denominator of the ratio. it does not implement the algorithm to find the lowest integers that can give that ratio at that precision.

Output:
>>> (245850922/78256779).as_integer_ratio()
(884279719003555, 281474976710656)

[Gribouillis]

You can get rational approximates with smaller denominators by using the fractions module

>>> from fractions import Fraction
>>> Fraction(245850922,78256779).limit_denominator(1000)
Fraction(355, 113)
>>> Fraction(245850922,78256779).limit_denominator(10000)
Fraction(355, 113)
>>> Fraction(245850922,78256779).limit_denominator(100000)
Fraction(312689, 99532)
>>> Fraction(245850922,78256779).limit_denominator(50000)
Fraction(104348, 33215)

[Skaperen]

those are less accurate approximations for Pi than the ratio i showed, which give the full precision that C double on x86 can represent, which is the type that Python uses.

[Gribouillis]

those are less accurate approximations for Pi than the ratio i showed, which give the full precision that C double on x86 can represent, which is the type that Python uses.

If you want a better approximation of pi than the double precision constant math.pi, you can use a multiprecision library such as gmpy2 and/or a known numerical algorithm converging to pi. Many of the existing algorithms give rational approximations which could be passed to Fraction.limit_denominator(). You can also find easily millions of digits of pi directly on the web. A simple search points to a file suposedly from the MIT with 1 billion digits.

[Skaperen]

my point is that both 245850922/78256779 and 884279719003555/281474976710656 give an accurate value of Pi, as precise as double type (53 bit mantissa on x86) can hold. the 2nd one is what float.as_integer_ratio() returns, but the 1st ratio is a better one because it is the smallest that can give a ratio that good. apparent float.as_integer_ratio() just uses power of two scaling. 281474976710656 == 2**48. it probably just scales the float value up until it is a whole number without any fractional part and includes the corresponding power of 2 in the tuple.

[Gribouillis]

This approximate is also given by the Fraction module

>>> from fractions import Fraction as F
>>> y = F(884279719003555,281474976710656)
>>> y.limit_denominator(100000000)
Fraction(245850922, 78256779)

The purpose of float.as_integer_ratio() is to give an integer ratio that is exactly equal to the real number stored in memory (which is not pi but an approximation of pi). It is a different problem from approximating pi with shorter fractions. The IEEE754 format indeed implies that the actual denominator is a power of two.

Note that for most floating numbers, you cannot expect a significant reduction of the size of the integers by doing this because the global number of bits needed to distinguish these numbers is fixed.

[Skaperen]

but the smaller ratio gives a value that is exactly equal to the larger one. the smaller ratio can be transported to non-Pike non-Python 32-bit integer environments, if ever needed. or why does fractions.Fraction().limit_denominator() work out the smaller one? i'd like to see which algorithm it uses.

[Gribouillis]

but the smaller ratio gives a value that is exactly equal to the larger one.

This is not true. It is exactly equal to the larger one when you convert it to a 64 bits floating number, because some information is lost in the conversion process, but it is a different real number, mathematically speaking.

The algorithm is a classical mathematical algorithm based on continued fractions. You can see the algorithm if you look at the code of limit_denominator() in fractions.py.
I modified this code below to generate the sequence of best approximations of a fraction with smaller denominators

from fractions import Fraction

def best_fractions(f):
    # this code is based on fractions.limit_denominator's code
    """Generate the best approximations of a fraction
    by using the algorithm of continued fractions.
    
    see http://en.wikipedia.org/wiki/Continued_fraction
    """
    p0, q0, p1, q1 = 0, 1, 1, 0
    n, d = f._numerator, f._denominator
    while d:
        a = n//d
        q2 = q0+a*q1
        p0, q0, p1, q1 = p1, q1, p0+a*p1, q2
        n, d = d, n-a*d
        yield Fraction(p1, q1)

def main():
    import math
    f = Fraction(math.pi)
    for q in best_fractions(f):
        print(q)
        
if __name__ == "__main__":
    main()

Output:
3
22/7
333/106
355/113
103993/33102
104348/33215
208341/66317
312689/99532
833719/265381
1146408/364913
4272943/1360120
5419351/1725033
80143857/25510582
245850922/78256779
817696623/260280919
1881244168/598818617
2698940791/859099536
9978066541/3176117225
32633140414/10387451211
238410049439/75888275702
509453239292/162164002615
747863288731/238052278317
1257316528023/400216280932
4519812872800/1438701121113
10296942273623/3277618523158
436991388364966/139098679093749
884279719003555/281474976710656

Note that these are not the best rational approximations of the mathematical number pi but the best rational approximations of the built-in constant math.pi.

[Skaperen]

looks like an increasing precision. but it missed some in the middle. i put my list on my web site since it is so big. the code that did this used ints based on 32769 digits of Pi. the original Pike code is there, too. my very first Python code was a translation of this Pike code, but i can't find it, right now. the 1864 ratios in that list were calculated in around 87 milliseconds of CPU on an i7 at 2.5 GHz under Pike 8.0. the Python version is slower because Python ints are slower than Pike ints. i'll look for that code so i can time it and put it online.

http://ipal.net/pi.ratios
http://ipal.net/intfrac.pike

---

calculating both ratios in the 54 bit mantissa of type double on x86, results in exactly the same value. doing it in the 65 bit mantissa of type long double on x86 may well have different results. have not tested that but a somewhat larger ratio can produce the maximum precision possible in long double. i tested this in C many years ago. on an IBM S/370 it can be much different. double has a 56 bit mantissa (less exponent range) and long double has twice that ... 112 bit mantissa (and uses 16 bytes of space). my first fractal code was done in S/370 assembler. since then i have used libgmp in C to do extremely deep Mandelbrot sets.

[Gribouillis]

The links are broken, I get a 404...