Efficiently getting bits of N! ?

Question

Given $N$ and $M$, is it possible to get the $M$'th bit (or digit of any small base) of $N!$ in time/space of $O( p( ln(N), ln(M) ) )$, where $p(x, y)$ is some polynomial function in $x$ and $y$?

i.e. Given $N = 2^\eta$, $M = 2^\mu$ (with $N$, $M \in \mathbb{Z}$), find bit $2^\mu$ of $(2^\eta)!$ in $O( p(\eta, \mu) )$.

Or perhaps I should be asking whether this problem is NP-Complete?

NOTE: Crossposted to cstheory.stackexchange where Suresh Venkat was kind enough to point me to Dick Lipton's post from 2009 that seems to indicate that this problem is as hard as factoring.

Answer 1

This isn't a complete answer, but I can do it polynomially in $\log N$ and $M$. In other words, the problem isn't hard if $M$ is small.

Stirling's formula approximating $N!$ gives the first few terms of a convergent series for $\log(N!)$. Using this series, we may approximate $\log(N!)$ to any fixed degree of accuracy in polynomial time (in $\log N$). Indeed, if you work it out, you'll see that you can approximate $\log(N!)$ within $2^{-M}$ in $O(M^2 \log N \log\log N)$ time. (Recall $\log N \log\log N$ is the cost of multiplication with a fast Fourier transform; if you multiplied naively, it would be $(\log N)^2$.) Approximating $\log(N!)$ within $2^{-M}$ is exactly what it takes to get the first $M$ digits.

Your question is actually equivalent to: Can you quickly pull out any digit of $N!$? There are only about $N \log N$ digits, so $M$ is bounded by a polynomial in $N$. By the above, we can get digits near the beginning. Digits near the end will also be easy: The problem then reduces to modular arithmetic and divisibility considerations. But I have no idea whether there's a fast way to pull out digits in the middle.

Answer 2

I believe the problem is thought to be hard, but I unfortunately have no reference to give.

A "complexity class" upper bound in given by Peter Bürgisser in the paper On defining integers and proving arithmetic circuit lower bounds. Specifically he shows the problem is in the counting hierarchy.

Answer 3

Perhaps I don't understand correctly (edit: I didn't, see below), but isn't this a trivial problem?

The complexity of multiplication is $m(n):=O(n\lg n)$ (where $\lg:=\log_2$) for two numbers of length $n$. We can naively compute factorial recursively via the good old $$N!=\begin{cases}1 & \text{if } N=0\\\\ N\cdot(N-1)! & \text{if }N>0.\end{cases}$$ The length of $N$ in base $2$ is approximately $\lg N$, so multiplication has an upper bound of $m(\lg N)$. Clearly this terminates in $N$ steps and hence requires $N$ multiplications, and therefore has a complexity of $O(Nm(\lg N))=O(N\lg N\lg\lg N)$. Supposing looking up the $M$th digit is $O(1)$, it is then just $O(N\lg N\lg\lg N)$. If look-up is linear in length, then it's $O(N(\lg N)^2\lg\lg N)$.

Edit: I guess I just forgot that it should be strictly polynomial in $\lg N$, which $N(\lg N)^2\lg\lg N$ of course isn't. Sorry about that. I'll refrain from deleting this though for the sake of ... completeness?