Calculating the factorial n! by the algorithm that defines it is of O(n) complexity because it requires n-1 multiplications to find the solution. Is there an algorithm that is any faster than that?
1
-
$\begingroup$ Does this answer your question? Factorial algorithm more efficient than naive multiplication $\endgroup$– Bolton BaileyCommented Aug 12, 2021 at 6:28
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
If you want to get into technicalities, computing the factorial actually takes more than $O(n)$ time: One way to notice this is that $n!$ as a number has $\Theta(n \log n)$ digits. It will therefore take at least $\Theta(n \log n)$ time to even write the answer, so computing the answer will take at least that long.
That being said, can you compute $n!$ in $O(n \log n)$ time? Yes, but you have to be a little careful. The pseudocode
product = 1
for i from 1 to n:
product = product * i
Is too slow, because at during the second half of the for loop, you end up multiplying $O(n)$-digit numbers $O(n)$ times, and you would end up with an algorithm that is at least quadratic.
A more efficient way is to divide and conquer: Starting with a list of numbers $1$ through $n$, pair the numbers up and multiply. Then do this again and again until you have a single number. In the $i^{\text{th}}$ iteration, you multiply $O(n/2^i)$ pairs of $O(2^i \log n)$-digit numbers. If we use a multiplication algorithm which takes $O(d \log d)$ time for $d$-digit numbers, then the $i$th iteration takes $O(n (\log n) \cdot \log(2^i \log n)) = O(n (\log n) i + n (\log n) (\log (\log n)))$ time. Summing for $i$ going from 1 to $\log n$, we get $O(n \log(n)^2 (\log (\log n)))$.
Even faster is to decompose the prime factors of the numbers below $n$. More details in this paper
By the way you are asking the question though, it seems like you are more interested in a model of computation where multiplication of integers takes a single step, and you want the answer to the question "How many multiplications do you have to do to compute the factorial?". In this case the answer is O(n), simply because if we treat the numbers we have to multiply as given and the multiplication algorithm as a black box, each multiplication has two inputs and one output, so it only reduces the list of numbers we have to multiply by 1.
-
$\begingroup$ 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. $\endgroup$ Commented Aug 12, 2021 at 23:52
-
$\begingroup$ @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)})}}}))$. $\endgroup$ Commented Aug 13, 2021 at 2:25
-
$\begingroup$ 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 $\endgroup$ Commented Dec 25, 2022 at 18:30