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