# 2012/09/30

## (exact (/ 3.0)) => ?

Since Gauche's floating point numbers (flonums) have
limited precision, you can always calculate the exact
number the flonum represents. If a flonum *d* is finite,
it can be represented as follows:

d=s*m* 2^ewheres: 1 or -1m,e: integer

If *e* >= 0, *d* has no fractional part. If *e* < 0,
we can have an exact rational number for *d* as follows:

(s*m) / 2^(-e)

As of Gauche 0.9.3.3, `exact`

works exactly like this.
This is correct, but it has annoying behavior.

;; Gauche 0.9.3.3 gosh> (exact (/ 3.0)) 6004799503160661/18014398509481984 gosh> (exact 0.1) 3602879701896397/36028797018963968

Neither 1/3 nor 1/10 can be represented accurately by a flonum; internally we use the closest flonum, but whose exact value is such a gigantic rational number.

But does that make sense? An inexact number is, after all,
inexact. We can regard a flonum *d* as an approximation
of any real number within a certain range around *d*.
There are infinite number of rationals in the range.
Why don't we pick the simpler rational among them?

(Since I sometimes see the argument that floating point
numbers are inexact, I tempted to add a note. A floating point
number itself can be either inexact or exact; there's nothing
*inherently* inexact in the floating point number representation.
It is the operations on them, in general, that are inexact (when rounding,
overflow or underflow occur). If we use "exact floating point number",
then the above gigantic rational representation is *the* correct
answer. It is just that Gauche uses floating point representation
for inexact numbers, which allows us to choose alternative rational
representation.)

We already do similar sort of thing in printing flonums; we choose the shortest decimal representation that can uniquely identify given flonum.

Now we have rationalize, we can use the same algorithm to find out the simplest rational
number within the precision of a flonum. We can't use `rationalize`

directly, though, for the error range is more complicated.

In general, any real number *r* that falls between this range
will be represented by a flonum *d*:

d-q/2 <r<d+q/2 ;mis oddd-q/2 <=r<=d+q/2 ;mis even whered=s*m* 2^eandq= 2^e

That is, *q* is the least quantum representable with the current exponent.

Since Gauche adopts round-to-even rule, the value that exactly falls
between two floating point numbers would belong to the *even* flonum---
the one whose LSB of mantissa is zero.

This alone makes `rationalize`

short for our purpose, since
it always consider a closed range.

There are also two special cases we need to consider. If a flonum is a power of two, the flonums below is more "dense" than usual, so we have smaller lower error range:

d-q/4 <=r<=d+q/2

Also, if *d* falls under denormalized range, *q* is fixed to
to the smallest denormalized number.

So we implemented a new procedure `real->rational`

, which
can take individual upper and lower error boundary and a flag
to indicate whether the range is open or not.
Then `rationalize`

can be written on top of it.
Our new `exact`

and `inexact->exact`

calls `real->rational`

if the argument is inexact real. Here's what you get in HEAD:

gosh> (exact (/ 3.0)) 1/3 gosh> (exact 0.1) 1/10

If you need the exact rational representation of *d* itself,
you can call `real->rational`

with zero error tolerance.

gosh> (real->rational (/. 3) 0 0) 6004799503160661/18014398509481984 gosh> (real->rational 0.1 0 0) 3602879701896397/36028797018963968

Post a comment