What is the computational complexity of sin and cos for floating point inputs?

$\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 Thrien 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 afortiori 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 dont 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 3rd5th level of CH.

Solved by user6959 (1 )
Jul 07, 2015 at 14:11