Timeline for Computing sine of gamma function [closed]
Current License: CC BY-SA 4.0
16 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| S Oct 21, 2023 at 6:09 | history | closed | S. Carnahan♦ | Not suitable for this site | |
| S Oct 21, 2023 at 6:09 | comment | added | S. Carnahan♦ | I’m voting to close this question because it was crossposted to Math.SE and has a good answer there. | |
| Aug 28, 2023 at 14:44 | comment | added | Sidharth Ghoshal | Some info here: 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 $10^{100}$ 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. | |
| Aug 28, 2023 at 14:43 | comment | added | Sidharth Ghoshal | I would assume there exists some kind of digit extract algorithm for this that doesn’t compute the intermediate $\Gamma$ ever since once such algorithm was found for $\pi$. I would guess actually finding such an algorithm might be very difficult | |
| Aug 28, 2023 at 8:34 | comment | added | Brendan McKay | @Aurel, yes it is exponential in that sense. | |
| Aug 28, 2023 at 8:08 | comment | added | Aurel | @BrendanMcKay $x\log x$ is exponential in the size $O(\log x)$ of the input $x$. | |
| Aug 28, 2023 at 7:13 | comment | added | Brendan McKay | @EmilJeřábek Finding $n$ bits of the fractional part of $\Gamma(x)$ needs $O(x\log x)+ n$ bits of $\Gamma(x)$, not exponentially many bits. | |
| Aug 28, 2023 at 6:38 | comment | added | Emil Jeřábek | 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 $\Gamma$ first. | |
| Aug 28, 2023 at 6:33 | comment | added | Emil Jeřábek | 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. | |
| Aug 28, 2023 at 5:19 | comment | added | Max Horn | As to the other questions, there is a reason for the rule to not ask multiple questions in one question 🙂 | |
| Aug 28, 2023 at 5:18 | comment | added | Max Horn | 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 | |
| Aug 28, 2023 at 1:20 | review | Close votes | |||
| Sep 14, 2023 at 3:02 | |||||
| Aug 28, 2023 at 1:00 | comment | added | Ryan Budney | Does this answer your question? What is the time complexity of computing sin(x) to t bits of precision? | |
| Aug 28, 2023 at 0:58 | comment | added | Dmitri Pavlov | This question is already answered here, for both sin and Γ: mathoverflow.net/questions/19946/…. The answer is $O(M(n)\log n)$, where $M(n)$ is the complexity of multiplication. | |
| Aug 28, 2023 at 0:15 | history | edited | LSpice | CC BY-SA 4.0 |
Proofreading
|
| Aug 28, 2023 at 0:08 | history | asked | roignoirewg | CC BY-SA 4.0 |