Guaranteed correct digits of elementary expressions

Question

Let $E$ be the set of elementary expressions, defined as the smallest set of mathematical expressions such that $1 \in E$, and if $a,b \in E$ then $a + b$, $a - b$, $ab$, $a/b$, $\exp(a)$, $\log(a)$ all belongs to $E$ (note that expressions such as $a/0$ or $\log(0)$ are fine, although they do not have a numerical value).

This problems often pop ups:

Problem. Given an expression $f$ in $E$ and a natural number $n$, find the first $n$ decimal digits of the numerical evaluation of $f$ (real and complex part).

Note that $E$ contains expressions for $e = \exp(1)$, $i = \exp(\log(-1)/2)$, $\pi = -i\log(-1)$, and many "elementary" mathematical constants. Also, assume a NaN evaluation for expressions like $1/0$.

My questions are the following:

1. Is this problem decidable? I found that Richardson's theorem establishes the undecidability of a similar problem.
2. If the problem is decidable, is there a known algorithm and some (at least partial) implementation of it?
3. If the problem is undecidable, what is the main obstruct and are there some ways to go around it? Again implementation of (heuristic?) algorithms are welcome.

Thanks

Update. The current answers solve the question if the problem is decidable (yes, but under Schanuel's conjecture). The only thing that prevents me from accepting an answer, is that I would like to know about implementations of the algorithm. Since I often encounter this problem in practice, is there some software that (assuming Schanuel's conjecture) I can run to solve the problem for a certain expression? (Of course I can do my own reasoning about the number of correct digits given by certain software and how the errors propagate, but I would like something that automatically do that.)

Second update. In light of Aurel's comments, I point out that the software Calcium seems to do the job. More precisely, according to the documentation, the function

char *ca_get_decimal_str(const ca_t x, slong digits, ulong flags, ca_ctx_t ctx)

returns a decimal approximation of x with precision up to digits. The output is guaranteed to be correct within 1 ulp in the returned digits, but the number of returned digits may be smaller than digits if the numerical evaluation does not succeed.

Answer 1

There is a certain confusion in the answers, so let me try to dispel this confusion.

There are two different issues here. One is “computing an approximation with arbitrary precision” and one is “computing correct digits”.

The first, “computing an approximation with arbitrary precision”, is certainly possible algorithmically (proviso the quantity is indeed a real or complex number), as Alexandre Eremenko points out in his answer. However, as Joel David Hamkins points out in a comment to this answer, computing arbitrarily precise approximations (≈being a computable real number) is not the same as computing guaranteed correct digits, essentially because deciding whether a computable real number is $\geq 0$ or $\leq 0$ (even if both answers are deemed acceptable in case of exact equality) is not decidable.

However, for the specific numbers being considered here, it turns out that equality is decidable, if we assume Schanuel's conjecture holds, as I explain in the answer to this question (this is also a result by Richardson, but this one is positive). Now if we can decide equality and we can compute with arbitrary precision, then we can indeed compute guaranteed correct digits. So the answer to the question is positive provided we assume Schanuel's conjecture. More precisely, there is a (fairly explicit) algorithm which will compute guaranteed correct digits if it terminates, and which will always terminate if Schanuel's conjecture holds.

Answer 2

This problem is Turing equivalent to the constant problem (see also Wikipedia-constant problem), but it is open whether this problem is decidable.

The constant problem is the problem of determining whether a given constant expression $E$ (in a suitable language) is zero.

This is different from Richardson's theorem, which in contrast is concerned with the problem of determining whether a given expression $E(x)$ with free variable $x$ is the zero function, that is, zero for all values of $x$. Richardson's theorem shows that this problem is not computably decidable.

Your digit problem is at least as hard as the constant problem, since as Kostya mentions in his answer, a given constant expression $E$ is zero if and only if $1-E^2$ starts with 1.0.

Conversely, the constant problem is at least as hard as the digit problem. To see this, notice first that the digit problem is computable from the order-relation problem, determining whether $E<F$ for constant expressions. This is because you can learn the digits of $E$ by comparing it with suitable rational expressions. And the $E<F$ problem is equivalent to deciding positivity $0<E$. But with an oracle for the constant problem, given $E$ we can first decide whether $E=0$ or not, and if not, compute approximations well enough to determine the sign. (Thanks for the comment of Aurel.)

So your problem is equivalent to the constant problem. But according to Wolfram, it is open whether the constant problem is computably decidable.

Answer 3

Edited after the comment of Joel David Hamkins. The "correct $n$-th digit of a real number, of of real and imaginary part of a complex number is ill defined. For example, what is the $n$-th digit of the number 1=0.999999...? What is the "correct 5-th digit"?

But you can approximate your numbers with any given accuracy, and there are simple algorithms for this. The algorithms for $a\pm b$, $ab$ and $a/b$ we study in elementary school while for $\exp(a),\log a$ one can use power series, or rational approximation.

The difference with Richardson's theorem is that he considers exact equality, while you ask only about $n$ digits. So you cannot always determine that such an expression is $=0$, but you can determine whether the first 100 digits are $0$.

Moreover, for all these functions there exist algorithms which work with polynomial speed in $n$, even with the speed $n^{1+\epsilon}$. For addition/subtraction this is evident, for multiplication/division these are fast multiplication algorithms (based of fast Fourier transform), while for $\exp$ and $\log$ these are algorithms based on AGM.

See, for example, Donald Newman, Rational approximation versus fast computer methods. Lectures on approximation and value distribution, pp. 149–174, Sém. Math. Sup., 79, Presses Univ. Montréal, Montreal, QC, 1982,

where all mentioned algorithms are explained.