Timeline for Can $N!$ be computed in less than $\mathcal{O}(N)$ operations?
Current License: CC BY-SA 4.0
15 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 2, 2023 at 13:20 | vote | accept | user6873235 | ||
| Jul 2, 2023 at 10:18 | comment | added | kodlu | Please clarify if the supplied answer addresses the question the way you intended. | |
| Jul 2, 2023 at 9:54 | comment | added | Federico Poloni | @EmilJeřábek I suggest to post this as an answer. | |
| Jul 2, 2023 at 9:08 | history | edited | Federico Poloni | CC BY-SA 4.0 |
Tried to improve that very confusing formulation.
|
| Jul 2, 2023 at 9:06 | comment | added | Emil Jeřábek | It seems you are interested in the algebraic circuit complexity of $N!$, as in mathworker21’s comment. There is a well known argument that, basically, $N!$ cannot have small algebraic circuits unless factoring is easy. Specifically, if $N!$ has algebraic circuits of size $s$, constructible in time (bit-complexity) $s^{O(1)}$, then integers $X$ below $N^2$ or so can be factored in time $s^{O(1)}$, using binary search to find the least $M\le N$ such that $M!\bmod X$ is not coprime to $X$, which will be a prime factor of $X$. | |
| Jul 2, 2023 at 9:03 | answer | added | Hhan | timeline score: 11 | |
| Jul 2, 2023 at 8:46 | comment | added | Emil Jeřábek | Well, a model of computation where multiplication of exponentially large integers takes constant time is totally unrealistic. | |
| Jul 2, 2023 at 8:44 | history | edited | user6873235 | CC BY-SA 4.0 |
added 192 characters in body
|
| Jul 2, 2023 at 8:41 | comment | added | user6873235 | As for model of computation, we're just considering a naive idealisation of an everyday computer where all basic arithmetic operations take equal constant time. I had more discussion of closed forms in an earlier draft of the question, which clarified this. I'm not really interested in conceptualising things on the level of bits unless someone can give a clever algorithm using bit fiddling. A model of computation where $\mathcal{O}(\times) \neq 1$ is not interesting given the heart of the question is really "is there a smarter/faster way to calculate factorials than just using the definition?" | |
| Jul 2, 2023 at 8:21 | comment | added | user6873235 | Yeah, I'm kinda abusing notation here with big O due to factorial being conventionally not written with standard function notation. I hoped the context would've made the intended meaning obvious. | |
| Jul 2, 2023 at 8:16 | comment | added | Emil Jeřábek | What kind of time complexity are you talking about? What is your model of computation? The length of the output is $\approx N\log N$ bits, hence under the standard computation model and standard definition of time complexity, it requires time at least $N\log N$ just to write the output, hence the function cannot be computed faster than that. | |
| Jul 2, 2023 at 8:13 | comment | added | GH from MO | @mathworker21 I understand the question. However, the OP uses the $O(\dots)$ notation incorrectly (or at least in a very non-standard way). | |
| Jul 2, 2023 at 7:59 | comment | added | mathworker21 | @GHfromMO I think the question is: can you define N! with strictly less than $N$ multiplications (or additions, subtractions, and divisions also I suppose)? | |
| Jul 2, 2023 at 7:42 | comment | added | GH from MO | Usually $f(N)=O(g(N))$ means that $|f(N)|$ is bounded by a constant times $g(N)$. You clearly use the $O(\dots)$ notation in a different sense, and then you should explain in what sense (i.e. define it). | |
| Jul 2, 2023 at 7:16 | history | asked | user6873235 | CC BY-SA 4.0 |