1

In the sense of bit complexity, how difficult is it to compute sin(aΓ(x))

where a is a constant and x>1? Is it possible to avoid the computation of Γ as first step? Is there a way to determine if the expression equals 0, without direct computing?

LSpice
  • 11,423
roignoirewg
  • 67
  • This question is already answered here, for both sin and Γ: https://mathoverflow.net/questions/19946/what-is-the-time-complexity-of-computing-sinx-to-t-bits-of-precision. The answer is O(M(n)logn), where M(n) is the complexity of multiplication. – Dmitri Pavlov Aug 28 '23 at 00:58
  • 2
    Does this answer your question? What is the time complexity of computing sin(x) to t bits of precision? – Ryan Budney Aug 28 '23 at 01:00
  • 1
    From a point of view of complexity, your function computes Γ, 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 – Max Horn Aug 28 '23 at 05:18
  • 2
    As to the other questions, there is a reason for the rule to not ask multiple questions in one question – Max Horn Aug 28 '23 at 05:19
  • 2
    The comments above are incorrect as they completely ignore the basic problem that Γ grows exponentially, hence one needs exponentially many bits of Γ to determine n bits of the sine. The problem may well be difficult. – Emil Jeřábek Aug 28 '23 at 06:33
  • As for the last question, I don't even see why exact equality to 0 should be decidable at all. Computing approximations does not by itself help with deciding equality. This is unrelated to the problem of computing Γ first. – Emil Jeřábek Aug 28 '23 at 06:38
  • @EmilJeřábek Finding n bits of the fractional part of Γ(x) needs O(xlogx)+n bits of Γ(x), not exponentially many bits. – Brendan McKay Aug 28 '23 at 07:13
  • 1
    @BrendanMcKay xlogx is exponential in the size O(logx) of the input x. – Aurel Aug 28 '23 at 08:08
  • @Aurel, yes it is exponential in that sense. – Brendan McKay Aug 28 '23 at 08:34
  • 1
    I would assume there exists some kind of digit extract algorithm for this that doesn’t compute the intermediate Γ ever since once such algorithm was found for π. I would guess actually finding such an algorithm might be very difficult – Sidharth Ghoshal Aug 28 '23 at 14:43
  • 1
    Some info here: https://en.m.wikipedia.org/wiki/Spigot_algorithm generally speaking determining whether for a particular x that function is 0 is not tractable without the use of symbolic computation. You might need to extract 10100 digits before you find out if something is nonzero. With symbolic forms (depending on how large your space of allowed symbols and expressions is) this is most likely undecidable. – Sidharth Ghoshal Aug 28 '23 at 14:44
  • I’m voting to close this question because it was crossposted to Math.SE and has a good answer there. – S. Carnahan Oct 21 '23 at 06:09

0 Answers0