8
$\begingroup$

Given an algebraic number $\alpha$, I am interested in finding an approximation of $\Re(e^\alpha)$ up to a given precision, where $\Re()$ refers to the real part of the complex number.

Formally, I want to compute a rational number $r$ such that $$|\Re(e^\alpha)-r|\leq 2^{-n}$$

$\alpha$ is given by a (standard) minimal polynomial.

How fast can we solve this problem?


When $\alpha$ is given as a floating point, the following reference

R. Brent. Fast multiple-precision evaluation of elementary functions. JACM, 1976.

seems to give an answer.

However, I am not sure it can be used for the algebraic number $\alpha$.

$\endgroup$
  • 1
    $\begingroup$ Both exp and log can be approximated to $n$ bits of precision in time $O(M(n)\log n)$. Since numerical root approximation is not significantly faster (it certainly needs time at least $\Omega(M(n))$), your question is essentially equivalent to the complexity of approximating $\alpha$. For a fixed polynomial, the latter can be done in time $O(M(n))$ using Newton method, but I’m not sure what exactly happens when the polynomial (and a bounding interval!) is a part of the input. $\endgroup$ – Emil Jeřábek supports Monica Aug 27 '14 at 19:07
  • $\begingroup$ (The asymptotic time complexity of Newton’s iteration is more or less the time needed to evaluate the polynomial on a given input to $n$ bits of precision.) $\endgroup$ – Emil Jeřábek supports Monica Aug 27 '14 at 19:18
  • 1
    $\begingroup$ Oh, but everything I wrote applies when you want relative error, that is, $r$ is output in an exponent–mantissa representation, and the error bound holds for the mantissa. The way the question is written, you cannot get a better bound than the trivial $2^{O(n)}$, as the size of the output is exponential in the size of the input already in the case $\alpha$ is an integer, and $\epsilon=1$. $\endgroup$ – Emil Jeřábek supports Monica Aug 27 '14 at 19:30
  • 2
    $\begingroup$ To avoid the issue that Emil refers to the complexity of real functions are studied when domain is a compact set like the unit interval. If your $\alpha$ can be arbitrary large then exp cannot be computed in polynomial time. $\endgroup$ – Kaveh Aug 27 '14 at 22:01
  • $\begingroup$ PS: these algorithms generally work for all computable real numbers including algebraic numbers, we only need to provide arbitrary good approximations for the inputs. $\endgroup$ – Kaveh Aug 27 '14 at 22:13
3
+50
$\begingroup$

As written, the problem requires time $2^{\Omega(m)}$, where $m$ is the length of input (you unfortunately used $n$ for something else). Indeed, if e.g. $\alpha$ is a positive integer (given by its minimal polynomial $x-\alpha$) and $n=0$, the size of the output is exponential in the size of the input. This bound is of course optimal, as there are a number of ways how to compute the result in time $2^{O(m)}$.


Let me try to reformulate the question so that it makes a bit more sense. The main issue is how to choose the representation of the input and output, as well as the notion of approximation, so that exponentiation stands a fighting chance of being computable in polynomial time.

One way was mentioned by Kaveh in the comments: restrict the domain to a fixed finite interval. While this works, it is unnecessarily restrictive; in particular, there is no good way how to transform an algebraic number into one that is bounded so that their exponentials have anything to do with each other.

A more flexible approach is to represent the input as a fixed point number, and the output as a floating point number. To be specific, a fixed point representation is a string $$\pm a_ra_{r-1}\dots a_0.a_{-1}\dots a_{-s}$$ denoting $\pm\sum_ja_j2^j$, where $a_j\in\{0,1\}$, and a floating point representation is $$\pm2^e\times a_0.a_{-1}\dots a_{-s}$$ with a similar interpretation, where $e$ is a binary integer, and $a_0=1$. (As an exception, we also allow $0$ to represent itself.) An approximation of a real $x$ to $m$ bits of absolute accuracy is a real $x'$ such that $|x-x'|<2^{-m}$, and an approximation to $m$ bits of relative accuracy is $x'$ such that $|1-x'/x|<2^{-m}$. We will use absolute accuracy for fixed point approximations, and relative accuracy for floating point approximations. It follows that in both cases, we may as well assume $s\le m$ (up to loss of one bit of accuracy).

Fixed point and floating point representations of dyadic Gaussian rationals, and approximations of complex numbers, are defined similarly, using a pair of reals. Everywhere below, $n$ denotes the total size of the input.

Now, let (real or complex) exponentiation be the following problem: the input is a fixed point representation of a number $x$ and a unary natural number $m$, and the output is a floating point approximation of $e^x$ to $m$ bits of relative accuracy. Dually, logarithm takes as input a floating point number $x$ and unary $m$, and the output is a fixed point approximation of $\log x$ (say, the principal branch in the complex case) to $m$ bits of absolute accuracy.

As long as we stick to run-time bounds satisfying some mild regularity conditions, and ignore constant multiplicative factors, we have:

  • The complexity of exponentiation, logarithm, or any similar analytic function, is at least the complexity of integer multiplication: e.g., we can read off $a^2$ from $\exp(a2^{-t})=a2^{-t}+a^22^{-2t-1}+O(a^32^{-3t})$ for sufficiently large $t$, linear in the length of $a$.
  • Exponentiation and logarithm have the same complexity. The reason is that we can compute the inverse of a nice function by Newton iteration (or more sophisticated methods such as in Brent) using evaluation of the function itself. The iteration typically involse multiplications or divisions, but we can afford these by the previous point.

As for algebraic numbers $\alpha$, they can be represented by their minimal polynomial $f$ (written as a sequence of integer coefficients in binary) together with some means to distinguish between the roots of the same polynomial. A natural way to do that is to require an isolation interval or disk: a pair of fixed point numbers $c,\rho$ such that $|c-\alpha|<\rho$. We need to at least require that $\alpha$ is a unique root of $f$ with this property, but something stronger may be more suitable. More on that later.

Let algebraic number approximation be the following problem: given an algebraic number $\alpha$ in the representation above, and $m$ in unary, compute a (complex) fixed point approximation of $\alpha$ to $m$ bits of absolute accuracy.

$\DeclareMathOperator\re{Re}$The original question asked for $\re e^\alpha$, but let me ignore that for now, and define algebraic number exponentiation as the following problem: given $\alpha$ and $m$ as above, compute a (complex) floating point approximation of $e^\alpha$ to $m$ bits of relative accuracy.

Fact: Up to linear factors, the complexity of algebraic number exponentiation is the same as the complexity of algebraic number approximation plus the complexity of complex exponentiation.

Proof sketch: On the one hand, we can first compute the fixed point approximation of $\alpha$ and then exponentiate it. Note that $m+O(1)$ bits of absolute accuracy for $\alpha$ determine $e^\alpha$ to $m$ bits of relative accuracy, and vice versa.

On the other hand, if we can do algebraic number exponentiation, we can also do plain exponentiation, as we can readily convert a fixed point number (considered exact) to its representation as an algebraic number. By the comments above, this means we can also compute logarithms in the same time bound. Thus, we can approximate an algebraic number by first approximating $e^\alpha$, and then taking a logarithm. QED

This splits the question to two quite unrelated problems. The best known upper bound on exponentiation is

Theorem (Brent): If we can multiply $n$-bit integers in time $M(n)$, we can compute complex exponentiation (and logarithm) in time $O(M(n)\log n)$.

The best known lower bound is the $\Omega(M(n))$ mentioned above. The best known upper bound on $M(n)$ is $n\log n\,2^{O(\log^*n)}$ by Fürer’s algorithm.

Figuring out the state of art for algebraic number approximation (that is, root finding) is rather harder, as it is still an area of active research, and the formulations of bounds in the literature are often not as clear as one would want them. Let $\tilde O(f(n))$ denote $O(f(n)\mathrm{polylog}(f(n)))$.

For real root approximation, Pan and Tsigaridas give:

Theorem: Real algebraic number approximation can be done in time $\tilde O(d^2\tau+dm)$, where $d=\deg(f)$, and $\tau$ is maximum of bit-lengths of the coefficients of $f$.

In the same paper, they mention $\tilde O(d^3+d^2m)$ as the best known bound for complex root approximation. In a slightly more recent paper (http://arxiv.org/abs/1404.4775), they seem to claim the same bounds for the complex case as for the real case, under the assumption that the given isolation disk has isolation ratio (the distance of the disk’s center to the nearest other root of $f$ divided by the radius of the disk) at least $1+1/\log d$ or so, but it’s written in a rather messy way and I may misinterpret it.


Now, the final complication. I defined the problem as approximation of $e^\alpha$, whereas the question asks for $\re e^\alpha$. This actually makes the problem harder: if $\re e^\alpha\ll\operatorname{Im}e^\alpha$, then an approximation $x+iy$ of $e^\alpha$ to $m$ bits of relative accuracy has error $y2^{-m}$, which may well be larger than $x$ itself, and in any case is not guaranteed to be bounded by $x2^{-m}$.

For exponentiation of exact rationals, we can circumvent the problem:

Proposition: Given $\alpha=x+iy$ and unary $m$, where $x,y$ are binary rationals (or exact fixed point numbers), we can compute a floating point approximation of $\re e^\alpha$ to $m$ bits of relative accuracy within the same time bound as complex exponentiation as defined above, up to linear factor. (I.e., $O(M(n)\log n)$ using Brent’s algorithm.)

Proof sketch: We have $\re e^\alpha=e^x\cos y$. We can approximate $e^x$, and floating point numbers are easily multiplied, the problem is to approximate $\cos y$ with relative error $2^{-m}$. We can compute the integer $k$ nearest to $2y/\pi$, whence $\cos y$ is $\pm\cos y'$ or $\pm\sin y'$, where $y'=y-k\frac\pi2$ satisfies $|y'|\le\pi/4$. The issue arises when we need to compute $\sin y'$ and $y'$ is very small, since in order to have $\sin y'$ to $m$ bits of relative accuracy, we need $m+\log|{y'}^{-1}|$ bits of absolute accuracy. Assume that $y=u/v$, where $u,v$ are integers given as input. If $y'$ is small, we have a good rational approximation of $\pi$: $$\left|\pi-\frac{2u}{kv}\right|\le\frac{2|y'|}k.$$ Now, $\pi$ is known to have a finite irrationality measure $\nu$ (the current bound is $7{.}6063$ by Salikhov). This implies $$|y'|\ge\frac1{2k^{\nu-1}v^\nu},$$ which gives a linear upper bound on $\log|{y'}^{-1}|$ in terms of the length of the input. We can thus compute $y'$ to the desired accuracy; evaluating $\sin y'$ is then not a problem (if $y'$ is sufficiently small, we can just take $\sin y'\approx y'$). QED

I do not know whether the same holds for algebraic $\alpha$. In the argument above, one can get a bound on $\log|y'|$ from Baker’s theorem, however, none of its versions that I’ve seen is good enough to make the required accuracy linear in the size of the input: in particular, the bounds involve a (rather nasty) polynomial in $\deg(f)$. This makes the resulting algorithm polynomial in the size of the input, but with a ridiculous exponent.

$\endgroup$
  • $\begingroup$ I think the main issue is that exponentiation over integers is not poly time computable. So one way to deal with exponentiation over real numbers is to separate that issue from the rest: 1. find an integer $k$ such that $0 \leq b/k < 1$, 2. compute $r = (b/k)^e$, 3. return $(r,k,e)$ as answer. $\endgroup$ – Kaveh Sep 5 '14 at 21:46
  • $\begingroup$ Sorry, I’m lost. What is $k,b,e$, and what is $(r,k,e)$ an answer to? Anyway, the whole point of using a different representation for input and output as above is to make integer exponentiation polynomial time: you can compute $2^a$ trivially by just making $a$ the floating-point exponent, and $e^a$ works similarly (the exponent is $\lfloor a/\log 2\rfloor$, and then you proceed to approximate the bounded number $\exp(a-\lfloor a/\log 2\rfloor\log 2)$ to get the mantissa). $\endgroup$ – Emil Jeřábek supports Monica Sep 5 '14 at 22:02
  • $\begingroup$ Sorry Emil, I was a bit cryptic. Consider the problem where we want to compute $b^e$. What I was trying to say was that the only problem that prevents computing or efficiently is the one that comes from inefficiency of exponentiation on integers. $\endgroup$ – Kaveh Sep 6 '14 at 15:47
  • $\begingroup$ Yes, in a sense the problem is that integer exponentiation is inefficient (or rather, the result is too large). However, I don’t understand how your proposal is supposed to work. How do you represent $r$? If $e$ is an $n$bit integer, then if say $b/k\approx1/2$, then $r\approx 2^{-2^n}$ is exponentially tiny, hence we are back at square one. Anyway, since you are effectively representing the result as $k^er$, this is essentially a base-$k$ floating point, except it is not normalized and $k$ may vary, which makes it difficult to do any computation on such representations. What are the benefits? $\endgroup$ – Emil Jeřábek supports Monica Sep 6 '14 at 16:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.