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

[Oren Tirosh]

On Thu, Oct 03, 2002 at 12:00:51AM -0400, Tim Peters wrote:
> [Andrew Koenig]
> > ...
> > Seriously, I don't know whether it would help in practice.
> > It might be that normalizing rationals from time to time would
> > be enough.
> 
> Do check out Valérie Ménissier-Morain's work on exact rational arithmetic in
> Caml; I've referenced it several times before, and this discussion is always
> the same <wink>.  In real apps, the time it takes to normalize rationals can
> be a disaster (the gcd of two random ints is most likely to be 1, and
> longint gcds are very expensive).  In other real apps, not normalizing
> rationals can be a disaster.  There isn't a one-size-fits-all policy for
> this, and a serious implementation has to take that seriously (sorry, Scheme
> <wink>).

Here is a quick attempt at a one-size-fits-all policy:

Rationals have a denormalized internal representation but always appear to 
be normalized. Rationals may be normalized in-place and still be considered 
immutable because this is invisible to the user.

Rationals are normalized in-place in the following cases:

1. When the string representation of the rational number is required
2. When accessing the numerator or denominator explicitly
3. Occasionally, according to some magic heuristics to prevent growth

The price for trying to please everybody is complexity but performance 
does not have to suffer too much. 

	Oren