In the sense of bit complexity, how difficult is it to compute $$\sin(a\Gamma(x))$$ where $a$ is a constant and $x>1$? Is it possible to avoid the computation of $\Gamma$ as first step? Is there a way to determine if the expression equals $0$, without direct computing?
$\begingroup$
$\endgroup$
12
-
2$\begingroup$ Does this answer your question? What is the time complexity of computing sin(x) to t bits of precision? $\endgroup$– Ryan BudneyCommented Aug 28, 2023 at 1:00
-
1$\begingroup$ From a point of view of complexity, your function computes $\Gamma$, then a multiplication, then $\sin$, and thus its complexity is the sum of these complexities. Which means its complexity is the worst of the three, and two comments above already point out where to find that $\endgroup$– Max HornCommented Aug 28, 2023 at 5:18
-
2$\begingroup$ As to the other questions, there is a reason for the rule to not ask multiple questions in one question 🙂 $\endgroup$– Max HornCommented Aug 28, 2023 at 5:19
-
2$\begingroup$ The comments above are incorrect as they completely ignore the basic problem that $\Gamma$ grows exponentially, hence one needs exponentially many bits of $\Gamma$ to determine $n$ bits of the sine. The problem may well be difficult. $\endgroup$– Emil JeřábekCommented Aug 28, 2023 at 6:33
-
1$\begingroup$ @BrendanMcKay $x\log x$ is exponential in the size $O(\log x)$ of the input $x$. $\endgroup$– AurelCommented Aug 28, 2023 at 8:08
|
Show 7 more comments