Implementation limitations of float.as_integer_ratio()

Question

Recently, a correspondent mentioned float.as_integer_ratio(), new in Python 2.6, noting that typical floating point implementations are essentially rational approximations of real numbers. Intrigued, I had to try π:

>>> float.as_integer_ratio(math.pi);
(884279719003555L, 281474976710656L)

I was mildly surprised not to see the more accurate result due to Arima,:

(428224593349304L, 136308121570117L)

For example, this code:

#! /usr/bin/env python
from decimal import *
getcontext().prec = 36
print "python: ",Decimal(884279719003555) / Decimal(281474976710656)
print "Arima:  ",Decimal(428224593349304) / Decimal(136308121570117)
print "Wiki:    3.14159265358979323846264338327950288"

produces this output:

python:  3.14159265358979311599796346854418516
Arima:   3.14159265358979323846264338327569743
Wiki:    3.14159265358979323846264338327950288

Certainly, the result is correct given the precision afforded by 64-bit floating-point numbers, but it leads me to ask: How can I find out more about the implementation limitations of as_integer_ratio()? Thanks for any guidance.

Additional links: Stern-Brocot tree and Python source.

Anatol

The accepted answer is misleading. The as_integer_ratio method returns the numerator and denominator of a fraction whose value exactly matches the value of the floating-point number passed to it. If you want a perfectly accurate representation of your float as a fraction, use as_integer_ratio. If you want a simplified approximation with smaller denominator and numerator, look into fractions.Fraction.limit_denominator. IOW, math.pi is an approximation to π. But 884279719003555/281474976710656 is not an approximation to math.pi; it's exactly equal to it. – Evildoer

@MarkDickinson: Your point is well-taken; it clarifies this related answer. Although the accepted answer could use some maintenance, it helped me see where my thinking had gone awry. – Anatol

Answer 1

The algorithm used by as_integer_ratio only considers powers of 2 in the denominator. Here is a (probably) better algorithm.

Doctrine

Aha, 281474976710656 = 2^48. Now I see where the values came from. Interesting to compare implementations: svn.python.org/view/python/trunk/Objects/… – Anatol

Saying the algorithm is not accurate is a flawed explanation. float.as_integer_ratio() simply returns you a (numerator, denominator) pair which is rigorously equal to the floating-point number in question (that's why the denominator is a power of two, since standard floating-point numbers have a base-2 exponent). The loss in accuracy comes from the floating-point representation itself, not from float.as_integer_ratio() which is actually lossless. – Shepperd

IIUC, the algorithm is sufficiently accurate for a given floating-point precision. The genesis of the denominator is what puzzled me. The algorithm would never produce Arima's unique result, and there would be no point given the required precision. – Anatol

Other algorithm you mentioned runs indefinitely for input 0.1 16 (link to run) – Applecart

Well, the problem was in the absence of check whether m[0][0] / m[1][0] is equal to original number. Here is a fixed algorithm written in python. You may easily add a limit to denominator as shown in the original algorithm. – Applecart

Answer 2

You get better approximations using

fractions.Fraction.from_float(math.pi).limit_denominator()

Fractions are included since maybe version 3.0. However, math.pi doesn't have enough accuracy to return a 30 digit approximation.

Fomentation

Fraction.from_float() uses float.as_integer_ratio() under the hood. Both are exact, so both will give you the same answer. limit_denominator is only capable of decreasing precision, not increasing it. – Diaphysis

Answer 3

May I recommend gmpy's implementation of the Stern-Brocot tree:

>>> import gmpy
>>> import math
>>> gmpy.mpq(math.pi)
mpq(245850922,78256779)
>>> x=_
>>> float(x)
3.1415926535897931
>>> 

again, the result is "correct within the precision of 64-bit floats" (53-bit "so-called" mantissas;-), but:

>>> 245850922 + 78256779
324107701
>>> 884279719003555 + 281474976710656
1165754695714211L
>>> 428224593349304L + 136308121570117
564532714919421L

...gmpy's precision is obtained so much cheaper (in terms of sum of numerator and denominator values) than Arima's, much less Python 2.6's!-)

Seignior

I see the benefit. I've used GMP from Ada before, so gmpy will be handy. code.google.com/p/adabindinggmpmpfr – Anatol