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

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.