## Return to Answer

2 improved formatting

Take a look at Ker-I Ko's book or his survey. I don't have the book with me right now. You can find the following in Weirauch's book:

"On compact subspaces of their domains real functions exp, sin, cos, tan, and their inverse can be computed in time $t_m(k)\log(k)$."

Where $t_m(k)$ is the time needed to compute the first k digits of the multiplication (of two real numbers) which is $O(k^2)$. This is from page 229. In the introduction he mentions that multiplication, $\sin$, $\exp$, and $\log$ can be computed in time $O(k^2)$.

--

Ker-I Ko, "Polynomial-time computability in analysis", in "Handbook of Recursive Mathematics," Volume 2, Recursive Algebra, Analysis and Combinatorics, Yu. L. Ershov et al., Eds., 1998, pp. 1271-1317. http://www.cs.sunysb.edu/~keriko/survey3.ps

Ker-I Ko, "Computational Complexity of Real Functions", Birkhauser, 1991

Klaus Weihrauch, "Computable Analysis: An Introduction", (Texts in Theoretical Computer Science. An EATCS Series), Springer, 2000

1

Take a look at Ker-I Ko's book or his survey. I don't have the book with me right now. You can find the following in Weirauch's book:

"On compact subspaces of their domains real functions exp, sin, cos, tan, and their inverse can be computed in time $t_m(k)\log(k)$."

Where $t_m(k)$ is the time needed to compute the first k digits of multiplication (of two real numbers) which is $O(k^2)$. This is from page 229. In the introduction he mentions that multiplication, $\sin$, $\exp$, and $\log$ can computed in time $O(k^2)$.

--

Ker-I Ko, "Polynomial-time computability in analysis", in "Handbook of Recursive Mathematics," Volume 2, Recursive Algebra, Analysis and Combinatorics, Yu. L. Ershov et al., Eds., 1998, pp. 1271-1317. http://www.cs.sunysb.edu/~keriko/survey3.ps

Ker-I Ko, "Computational Complexity of Real Functions", Birkhauser, 1991

Klaus Weihrauch, "Computable Analysis: An Introduction", (Texts in Theoretical Computer Science. An EATCS Series), Springer, 2000