[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.