[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [srfi-70] Limit



 | From: Sebastian Egner <sebastian.egner@xxxxxxxxxxx>
 | Date: Wed, 25 May 2005 09:35:25 +0200
 | 
 | > LIMIT was created so that static choices for limit cases like:
 | > 
 | >   (expt 0 0)                                    ==> 1
 | > or
 | >   (expt 0 0)                                    ==> 0/0
 | > 
 | > don't necessitate workarounds when computing with functions like
 | > (lambda (x) (expt x x)):
 | >
 | >   (limit (lambda (x) (expt x x)) 0 1e-9)        ==> 1/0
 | 
 | Unfortunately, my experience is that this approach is highly
 | unreliable.  In the end, I spent more time doing analytical sanity
 | checks myself than it took to write the proper numerical code
 | directly after understanding the limits properly.
 | 
 | Example: An important function from information theory is
 | 
 |         f(x) =  -x log(x).
 | 
 | This function is in principle well behaved (smooth, analytic, etc.) on
 | (0,1], but its derivative does not exist at x = 0. Moreover, f(0)
 | cannot directly be computed numerically because the underflow from
 | log(x) is not cancelled by the multiplication with zero.  Practical
 | numerical code: IF x < xmin THEN 0 ELSE x log(x), where xmin is chosen
 | minimal such that log(xmin) is an ordinary number and not -infinity.
 | 
 | Using LIMIT in this case is not a good idea for two reasons:
 | a) It is expensive and unnecessary, except for very small x.

Its cost is a small multiple (currently 7) of the function call cost
plus constant overhead.  The multiple can be reduced; the effect will
be reduced detection of bad limits.

It would be straightforward to wrap a function so that LIMIT is called
only when the argument is within some given range (say 1e-50) of the
limit point; and otherwise the function is called directly.

 | b) At least the reference implementation of LIMIT doesn't get it right:
 | 
 |         (limit (lambda (x) (* -1 x (log x))) 0 1e-9) => -inf.0
 | 
 | This may be a bug in the reference implementation, but it is
 | certainly a violation of the new specification as f(x) is monotonic
 | on [0,1/e].

I have fixed the bug using the method described in
<http://swiss.csail.mit.edu/~jaffer/III/Limit.html>.

(limit (lambda (x) (* x (log x))) 0 1.0e-9)  ==>  -173.28679513998937e-12

I am working on improving the interpolation; and infinite limits must
be addressed separately.  I will update srfi-70 when it is complete.

 | When you try to fix the reference implementation, you will find
 | that it cannot be fixed because it comes from the "black box"
 | procedure: At a certain moment f(x) becomes -inf.0, so that must be
 | the limit.

The width is passed to the LIMIT procedure so that the overflow point
can be avoided.

 | I can relate another experience: The Mathematica system has an
 | operation Limit[], which finds limits symbolically, and a function
 | NLimit[] which finds limits numerically.  Limits[] turns out to be
 | useful sometimes, but it took many years and many releases until it
 | became something I nearly trust.  NLimits[] on the other hand is
 | tricky, even though it makes an effort to report when it fails,
 | e.g. NLimit[x Log[x], x -> 0.] => "cannot recognize limit".

(limit (lambda (x) (* x (log x))) 0 1e-200)  ==>  -1.7328679513992641e-201

 | Bottom line: In the end, LIMIT might do more harm than it is worth.
 | You might want to reconsider if it is a feature that is essential
 | for the Scheme programming language itself.

Rationalize, string->number, and number->string are precedents for
Scheme specifying very clean mathematical semantics at the possible
expense of efficiency.