Re: dependent and independent intervals, proposal to toss out text2interval. Was re: about emp (was: Motion 42:no)
On 2013-02-20 08:56:39 -0700, Kreinovich, Vladik wrote:
> Minor word of caution: while arithmetic of rational numbers is
> easily decidable, once we start adding constants like pi etc.
> (especially with special functions like exp and sin added) we run
> into situations where there is no known algorithm for deciding
> equality, or where algorithms are known but are unrealistically
> long. For example, as we mention in Chapter 4 of our 1997 book on
> computational complexity of interval computations, even algorithmic
> decidability of exp-polynomials (i.e., functions obtained by
> compositions of exp and polynomials) is based on an unproven
> hypothesis, and if we add sin to the mix, we get problems which are
> either undecidable or require exponential time in some cases.
Note that problems like that are not specific to irrational numbers.
They can also occur in floating-point (e.g. correct rounding of some
transendental functions, sin of a large argument when the exponent
range is large, typically in multiple precision).
--
Vincent Lefèvre <vincent@xxxxxxxxxx> - Web: <http://www.vinc17.net/>
100% accessible validated (X)HTML - Blog: <http://www.vinc17.net/blog/>
Work: CR INRIA - computer arithmetic / AriC project (LIP, ENS-Lyon)