[Python-Dev] Re: PEP239 (Rational Numbers) Reference Implementation and new issues (original) (raw)

Tim Peters tim.one@comcast.net
Wed, 02 Oct 2002 21:44:27 -0400

[Andrew Koenig]

By the way, has anyone considered the idea of making operations on rationals faster by never storing any trailing zeroes in the numerator or denominator? Instead, strip them and store the (signed) difference between the number of zeroes you've stripped from the numerator and the number you've stripped from the denominator.

In other words, instead of storing (num, denom) and having the number be the (exact) value of num/demon, store (num, denom, exp) and have the number be the (exact) value of (2**exp)*num/denom.

How many trailing zeroes do you expect to save this way? "On average", a random int has exactly n (>= 0) trailing zero bits with probability 1/2**(n+1). Then how expensive is it for operations to keep track of them appropriately (esp. + and -, where the split representation seems offhand (to me) unnatural to work with)? My FixedPoint.py does a variation of this for a form of unnormalized rational, except the "trailing zeroes" there are wrt base 10. But it wasn't to save time (heh) in that context, it was to create a faithful illusion of exact decimal arithmetic.