float.as_integer_ratio() 的实现限制

Question

最近，有位朋友提到了在Python 2.6中新增的一个功能 float.as_integer_ratio()，他说一般的浮点数实现其实是对真实数字的一个理性近似。我对此很感兴趣，于是决定试试π（圆周率）：

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

我有点惊讶没有看到更准确的结果，这和Arima有关：

(428224593349304L, 136308121570117L)

比如，这段代码：

#! /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"

输出了这个结果：

python:  3.14159265358979311599796346854418516
Arima:   3.14159265358979323846264338327569743
Wiki:    3.14159265358979323846264338327950288

当然，考虑到64位浮点数的精度，这个结果是正确的，但这让我想问：我怎么才能了解更多关于as_integer_ratio()的实现限制呢？谢谢任何指导。

附加链接：Stern-Brocot树和Python源代码。

Answer 1

我想推荐一下gmpy对斯特恩-布罗科特树的实现：

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

再次强调，结果在64位浮点数的精度范围内是“正确的”（53位的所谓“尾数”；-），但是：

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

...gmpy的精度在分子和分母值的总和上要比Arima的实现便宜得多，远远低于Python 2.6的实现！-)

Answer 2

你可以通过以下方式获得更好的近似值：

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

从大约3.0版本开始，分数也被包含在内。不过，math.pi的精度不够，无法返回30位数字的近似值。

Answer 3

as_integer_ratio这个函数使用的算法只考虑了分母是2的幂次方的情况。这里有一个（可能更好的）算法。