The gee-whiz feature is the new approx method, which permits cutting back
a rational with sharp control over the accuracy of, and/or the number of
bits used by, the approximation. E.g., as worked out in the example
below, you can ask for the most space-efficient rational approximation to
pi good to at least one part in N (your choice), or the most accurate
rational approximation to pi that fits in B (your choice) bits; etc.
think-of-it-as-a-memory-aid-for-335/113<snort>-ly y'rs - tim
Tim Peters tim@ksr.com
not speaking for Kendall Square Research Corp
# add support for rat(rational) (a nop)
# add functions shortrat and longrat
# add .copy() method
# add .__abs__() method
# add .approx(maxbits,minp) method
...
# rat(rational r) returns r unchanged
#
# Function shortrat takes the same arguments as rat, but always returns a
# short rat (however, it may overflow!).
#
# Function longrat takes the same arguments as rat, but always returns a
# long rat.
#
# If shortrat or longrat are passed an RNO, the RNO itself is changed.
# However, the mathematical _value_ of the RNO does not change, and
# neither does its hash value.
#
# Method r.copy() returns a copy s, such that r == s.
#
# Method r.approx(maxbits, minp) returns a triple (a,n,p). a is a Rat
# approximation to r that may take less storage (and hence run faster in
# subsequent computations, provided that the loss of accuracy can be
# tolerated). The approximation is the best possible such that
#
# 1) the numerator and denominator each take no more than `maxbits' bits
#
# 2) if #1 allows it, the approximation is no worse than 1 part in `minp'
# (in other words, abs((a-r)/r) <= 1/minp)
#
# `maxbits' and `minp' must be numeric types, and both must be >= 0.
# Intuitively, minp is a bound on the worst relatively accuracy you're
# willing to accept, but in no case will you accept more than maxbits
# bits. In more detail:
#
# A sequence of approximations, a1, a2, a3, ..., r, of increasing storage
# size and accuracy, is generated internally. Note that this sequence is
# finite, since r itself "approximates" r with perfect accuracy.
#
# If maxbits == 0, condition #1 is ignored, and if minp > 0 the first
# approximation in the list meeting the accuracy request is used.
# If minp == 0, condition #2 is ignored, and if maxbits > 0 the last
# approximation in the list of size <= maxbits is used.
# If both are 0, a == r (albeit after extensive computation ...).
# If both are nonzero, if the first approximation in the list meeting
# condition #2 also meets #1, that's the one that's used; else the last
# one in the list meeting #1 is used.
#
# As mentioned above, approx returns a triple (a,n,p):
# a is the rational approximation described above.
# n is max( number_of_bits_in(a.num), number_of_bits_in(a.den) ).
# If p is 0, a == r. Else p is an integer > 0 such that
# abs((a-r)/r) <= 1/p
# (so the approximation is no worse off than 1 part in p).
#
# An example should help:
#
# >>> import math, Rat
# >>> p = Rat.rat(math.pi) # the exact machine value (NOT exact pi!)
# >>> p # this may differ on your machine, & some numbers later too
# rat(884279719003555L, 281474976710656L)
# >>> p.approx(0,4) # get an approximation good to 1 part in 4
# (rat(3L), 2, 22L)
# >>> # 3/1 is the smallest-size approximation good to 1 part in 4;
# ... # its biggest piece takes 2 bits (for the numerator, 3);
# ... # it's actually good to 1 part in 22 (and note that
# ... # 1/abs((pi-3)/pi) ~= 22.19, so 3/1 is indeed good to 1 part in
# ... # 22 -- but not to 1 part in 23)
# ... p.approx(0,1000000) # get one good to one part in a million
# (rat(355L, 113L), 9, 11776665L)
# >>> # the 9-bit rat 335/113 does the trick, and note that
# ... # 1/abs((pi-355/113)/pi) ~= 11776665.62
# ... p.approx(0,11776665), p.approx(8,11776665)
# ((rat(355L, 113L), 9, 11776665L), (rat(22L, 7L), 5, 2484L))
# >>> # note that the second one could not meet the accuracy request,
# ... # because the limit on the number of bits would not allow it;
# ... # note too that 22/7 is in fact the best possible rational
# ... # approximation with numerator and denominator no more than 8 bits
# ... p.approx(128,11776666) # slightly tighter accuracy request
# (rat(103993L, 33102L), 17, 5436311184L)
# >>> # 335/113 wasn't quite good enough to meet the accuracy request,
# ... # and we need 8(!) additional bits to get a better rational
# ... # approximation (335/113 is indeed a very good approximation)
# ... p.approx(31,0) # find best approx that fits in Python ints
# (rat(1881244168L, 598818617L), 31, 1955598078002080795L)
# >>> Rat.shortrat(p.approx(31,0)[0]) # proving it does fit <wink>
# rat(1881244168, 598818617)
# >>> Rat.shortrat(p.approx(32,0)[0]) # and 32-bit approx doesn't
# Stack backtrace (innermost last):
# File "<stdin>", line 1
# File "./Rat.py", line 200
# a.num, a.den = int(a.num), int(a.den)
# ValueError: long int too long to convert
# >>>
end of msg