5
$\begingroup$

What is the computational complexity of the problem


INPUT: $\;\;\;$ integers $x$ and $y \:$ (both in binary)

OUTPUT:
rational approximations to $\: \sin\hspace{-0.03 in}\left(x\hspace{-0.04 in}\cdot \hspace{-0.04 in}2^{\hspace{.02 in}y}\hspace{-0.02 in}\right) \:$ and $\: \cos\hspace{-0.03 in}\left(x\hspace{-0.04 in}\cdot \hspace{-0.04 in}2^{\hspace{.02 in}y}\hspace{-0.02 in}\right)$
whose absolute errors are each less than $1/\hspace{-0.04 in}\left(2^{\hspace{.02 in}\operatorname{length}(x)}\hspace{-0.05 in}\right)$


?


One could just expand $\: x\hspace{-0.04 in}\cdot \hspace{-0.04 in}2^{\hspace{.02 in}y} \:$, $\:$ but that would use at least $\:\left|\hspace{.03 in}y\right|\:$ bits of space.
(I believe most work on the complexity of such functions
only considers their restrictions to compact intervals.)

$\endgroup$
3
  • $\begingroup$ sin and cos are (in the conventional representation) computable in uniform $\mathrm{TC}^0$, which implies that your problem is doable in the counting hierarchy (hence in polynomial space). It should be possible to estimate the relevant level of the hierarchy more precisely, but I do not see trigonometric functions mentioned in eccc.hpi-web.de/report/2013/177 , so it’s quite possible no one tried yet. $\endgroup$ Jul 1, 2015 at 19:11
  • $\begingroup$ It might be worth pointing out that the problem is equivalent to computing an approximation of $x2^y\bmod2\pi$. $\endgroup$ Jul 1, 2015 at 19:21
  • $\begingroup$ Which, on further thought, is equivalent to just computing an approximation of $2^y\bmod2\pi$ (with $\approx\log x$ bits of precision). $\endgroup$ Jul 1, 2015 at 19:27

1 Answer 1

5
$\begingroup$

$\def\tc{\mathrm{TC}^0}\DeclareMathOperator\len{len}$Since there were no other takers, let me expand the comments above.

The fundamental fact here is that approximations of basic arithmetic operations, and trigonometric and cyclometric functions like $\sin x$, $\cos x$, $\arctan x$, are computable in uniform $\tc$ (and therefore in logarithmic space) for fixed-point rational inputs. See e.g. Reif, Reif and Tate, Maciel and Thérien for the basic arguments, however, the most crucial result for the uniform version is the proof that integer division and iterated multiplication are in uniform $\tc$ by Hesse, Allender, and Barrington. This is optimal in that all such functions (except addition and subtraction) are $\tc$-complete.

(These results are typically stated for approximation of functions on a bounded domain, but they apply to arbitrary fixed-point inputs all the same, the point being that as long as there is only a linear number of bits before the binary point, we can reduce the input modulo $2\pi$ by just computing an approximation of $2\pi$ with a sufficent accuracy, followed by a division.)

This has several consequences.

First, $\sin(x2^y)$ and $\cos(x2^y)$ can also be approximated in uniform $\tc$ when $y$ is negative, by converting the input to fixed-point notation up to the desired accuracy. Thus, from now on I will only consider the case with $y\ge0$. We can as well also assume $x\ge0$, as this only affects the sign of sin.

Second, the problem is not really about trigonometric functions, as all the complexity is in reducing the input to a bounded domain. More precisely, we have:

Proposition 1: The following search problems are equivalent up to uniform $\tc$ (and a fortiori log-space) bounded-query Turing reductions:

  1. Given $x,y$, approximate $\sin(x2^y)$ and $\cos(x2^y)$ to $\len(x)$ bits of accuracy.

  2. Given $x,y$, approximate $\sin(x2^y)$ to $\len(x)$ bits of accuracy.

  3. Given $x,y$, approximate $x2^y\bmod 2\pi$ to $\len(x)$ bits of accuracy.

  4. Given $y$ and unary $n$, approximate $2^y\bmod \pi$ to $n$ bits of accuracy.

Here, approximation of $z\bmod2\pi$ is defined so that when $z$ is very close to an integer multiple of $2\pi$, numbers close to $0$ and close to $2\pi$ are both considered valid outputs.

Proof: For $1\le2$, use the identity $\cos z=1-2\sin^2(z/2)$. For $1\le3$, $\sin$ and $\cos$ are $2\pi$-periodic, and computable on $[0,2\pi]$ in $\tc$. For $3\le1$, we can compute $z\bmod2\pi$ from $u=\cos z$ and $v=\sin z$ in $\tc$ using $\arctan(v/u)$ and a little fiddling with quadrants. For $3\le4$, compute $2^y\bmod2\pi$ to $2\len(x)+O(1)$ bits of accuracy, and use $x2^y\bmod2\pi=x(2^y\bmod2\pi)\bmod2\pi$, which holds as $x$ is an integer. QED

Curiously, the argument above gives a reduction of $\cos(x2^y)$ to $\sin(x2^y)$—or actually to $|\sin(x2^y)|$—and conversely we can reduce $|\sin(x2^y)|$ to $\cos(x2^y)$ using the identity $\sin z=\pm\sqrt{1-\cos^2z}$, but I don’t know how to reduce $\sin(x2^y)$ itself to $\cos(x2^y)$.

Third, exponentially scaled uniform $\tc$ circuits can be evaluated with $O(1)$ alternations of existential and universal nondeterminism, and counting. That is,

Proposition 2: The problems from Proposition 1 are computable in the counting hierarchy FCH, and therefore in polynomial space.

(Notice that the trivial algorithm that expands $x2^y$ in full followed by a computation of $\sin,\cos$ only gives an exponential-time upper bound, so this is an improvement.)

The level of CH the problem lands in corresponds to the depth of the uniform $\tc$ circuits, up to small differences depending on the exact definitions of the levels and the circuit model. The recent paper by Allender, Balaji, and Datta tries to optimize the level for some of the basic ingredients (division, iterated multiplication). They do not mention trigonometric functions, so this would need further work, however it is a safe guess that the argument should give something in the vicinity of the 3rd–5th level of CH.

$\endgroup$
1
  • $\begingroup$ In fact, it looks like the scaling argument shows that the problem can be solved in DTISP(poly(length(x)+|y|),O(length(x)+length(y))). $\;$ $\endgroup$
    – user6973
    Jul 8, 2015 at 19:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.