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

Oren Tirosh oren-py-d@hishome.net
Thu, 3 Oct 2002 02:10:45 -0400

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

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