How does RATIONALIZE determine "the accuracy of the underlying
floating-point representation"? I thought for a moment that
FLOAT-PRECISION would tell me but I don't see how to combine that with
the results of INTEGER-DECODE-FLOAT to reimplement RATIONALIZE. So
either I'm missing something (likely) or there's some piece of
information about the floating point representation of a number that I
don't have access to via standard Common Lisp functions.
-Peter
--
Peter Seibel ·····@javamonkey.com
Lisp is the red pill. -- John Fraser, comp.lang.lisp
Peter Seibel <·····@javamonkey.com> writes:
> How does RATIONALIZE determine "the accuracy of the underlying
> floating-point representation"? I thought for a moment that
> FLOAT-PRECISION would tell me but I don't see how to combine that with
> the results of INTEGER-DECODE-FLOAT to reimplement RATIONALIZE. So
> either I'm missing something (likely) or there's some piece of
> information about the floating point representation of a number that I
> don't have access to via standard Common Lisp functions.
1- It's in the implementation, it just *knows*.
2- (defun my-rationalize (f)
(multiple-value-bind (signif expon sign) (integer-decode-float f)
(* signif (expt 2 expon) sign)))
;; not the same result as rationalize, but coerce to the same float
3- there are also the various *-epsilon constants, but they are tricky:
they are valid for floats near 1.0.
--
__Pascal Bourguignon__ http://www.informatimago.com/
The world will now reboot; don't bother saving your artefacts.
>>>>> "Peter" == Peter Seibel <·····@javamonkey.com> writes:
Peter> How does RATIONALIZE determine "the accuracy of the underlying
Peter> floating-point representation"? I thought for a moment that
Peter> FLOAT-PRECISION would tell me but I don't see how to combine that with
Peter> the results of INTEGER-DECODE-FLOAT to reimplement RATIONALIZE. So
Peter> either I'm missing something (likely) or there's some piece of
Peter> information about the floating point representation of a number that I
Peter> don't have access to via standard Common Lisp functions.
The ones that I've looked at use a continued fraction and they keep
adding terms to the continued fraction until the difference is close
enough to the float.
Here are some comments from cmucl, borrowed with permission from clisp:
;;; Algorithm (recursively presented):
;;; If x is a rational number, return x.
;;; If x = 0.0, return 0.
;;; If x < 0.0, return (- (rationalize (- x))).
;;; If x > 0.0:
;;; Call (integer-decode-float x). It returns a m,e,s=1 (mantissa,
;;; exponent, sign).
;;; If m = 0 or e >= 0: return x = m*2^e.
;;; Search a rational number between a = (m-1/2)*2^e and b = (m+1/2)*2^e
;;; with smallest possible numerator and denominator.
;;; Note 1: If m is a power of 2, we ought to take a = (m-1/4)*2^e.
;;; But in this case the result will be x itself anyway, regardless of
;;; the choice of a. Therefore we can simply ignore this case.
;;; Note 2: At first, we need to consider the closed interval [a,b].
;;; but since a and b have the denominator 2^(|e|+1) whereas x itself
;;; has a denominator <= 2^|e|, we can restrict the seach to the open
;;; interval (a,b).
;;; So, for given a and b (0 < a < b) we are searching a rational number
;;; y with a <= y <= b.
;;; Recursive algorithm fraction_between(a,b):
;;; c := (ceiling a)
;;; if c < b
;;; then return c ; because a <= c < b, c integer
;;; else
;;; ; a is not integer (otherwise we would have had c = a < b)
;;; k := c-1 ; k = floor(a), k < a < b <= k+1
;;; return y = k + 1/fraction_between(1/(b-k), 1/(a-k))
;;; ; note 1 <= 1/(b-k) < 1/(a-k)
(There comments also include an equivalent iterative algorithm, from
which you can easily write your own version.)
Ray
Here's a good article about rationalize:
http://google.com/groups?selm=87oer5ws7k.fsf%40g.mccaughan.ntlworld.com
--
Lars Brinkhoff, Services for Unix, Linux, GCC, HTTP
Brinkhoff Consulting http://www.brinkhoff.se/
Lars Brinkhoff <·········@nocrew.org> writes:
> Here's a good article about rationalize:
> http://google.com/groups?selm=87oer5ws7k.fsf%40g.mccaughan.ntlworld.com
Note that what I talk about there is *one way* of converting
numbers to rationals. There is no requirement for what CL:RATIONALIZE
does to be much like it; it could instead always produce a rational
number with denominator a power of 2.
--
Gareth McCaughan
.sig under construc