Path: utzoo!attcan!uunet!snorkelwacker!bu.edu!mirror!ima!haddock!karl
From: karl@haddock.ima.isc.com (Karl Heuer)
Newsgroups: comp.lang.c
Subject: Re: Inherent imprecision of floating point variables
Message-ID: <16987@haddock.ima.isc.com>
Date: 28 Jun 90 22:27:51 GMT
References: <1015@swan.ulowell.edu> <7060007@hpfcso.HP.COM> <4169@jato.Jpl.Nasa.Gov>
Reply-To: karl@haddock.ima.isc.com (Karl Heuer)
Organization: Interactive Systems, Cambridge, MA 02138-5302
Lines: 20

In article <4169@jato.Jpl.Nasa.Gov> kaleb@mars.UUCP (Kaleb Keithley) writes:
>I once wrote a rational number package...  All numbers are held in
>numerator/denominator form in a struct.

Certain operations, addition in particular, will quickly cause the denominator
to exceed the range of an integral type.  To avoid this, you have to combine
this with an expandable-int package.  And you still have a problem if you
apply a math function: sqrt(2) can only be approximated, not represented
exactly, by this mechanism.

Several people have posted to say that the exact-representation problem is
"unsolvable" because of this.  This is not necessarily true.  You could use
continued fraction representation, for instance.  sqrt(2) still has no finite
representation, but by using lazy evaluation you don't *need* to have the
whole thing in hand at once: it suffices to have a generator object that will
emit the next term on request.

There's a good discussion of this in HAKMEM, item #101.

Karl W. Z. Heuer (karl@kelp.ima.isc.com or ima!kelp!karl), The Walking Lint