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

Re: [srfi-70] Limit

This page is part of the web mail archives of SRFI 70 from before July 7th, 2015. The new archives for SRFI 70 contain all messages, not just those from before July 7th, 2015.

 | 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

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