Timeline for What is the most efficient algorithm for calculating factorials?
Current License: CC BY-SA 4.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| S Feb 23, 2023 at 9:36 | history | suggested | CommunityBot | CC BY-SA 4.0 |
Improved formatting
|
| Feb 21, 2023 at 9:12 | review | Suggested edits | |||
| S Feb 23, 2023 at 9:36 | |||||
| Dec 25, 2022 at 18:30 | comment | added | Nino Rode | OK, I'm late, but for anybody interested in the algorithms for computation of factorial, there is a very informative page from Lushny: luschny.de/math/factorial/FastFactorialFunctions.htm | |
| Aug 13, 2021 at 2:25 | comment | added | Matt Groff | @magnetlion: $M(n \log{(n)})$, the time to multiply a number at least as large as $n \log{(n)}$, is almost certainly as large as $n \log{(n)}$, so we have $O(n \log{n} \log{ \log{ n}}) \in O(\log{ \log {n \underbrace{M(n \log{(n)}}_{\ge n \log{(n)})}}}))$. | |
| Aug 12, 2021 at 23:52 | comment | added | magnetlion | The paper you linked says that its algorithm is of time O(log log n M (n log n)) where M(n) is the complexity of multiplication. Does that mean that if we consider multiplication to be one operation that the algorithm is O(log log n)? That seems awefully fast, especially if it requires we perform a prime number decomposition up to n. | |
| Aug 12, 2021 at 23:46 | vote | accept | magnetlion | ||
| Aug 12, 2021 at 6:25 | history | answered | Bolton Bailey | CC BY-SA 4.0 |