10
$\begingroup$

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.

$\endgroup$
4
  • 2
    $\begingroup$ This doesn't answer your question, which I believe assumes that the base n is fixed, i.e. n=O(1), but I note that if n is allowed to grow with N, say log n ~ c log N for some small constant c > 0, then the answer to your question is almost certainly no, since a positive answer would give a polynomial-time algorithm to factor n (even just using M=0). $\endgroup$
    – AVS
    Oct 13, 2010 at 19:28
  • $\begingroup$ Some trivial observations: $\eta$ and $\mu$ should be related. If $\eta > 2^\mu$ (roughly, I may be missing a constant factor), then $N!$ has bit $M$ precisely 0. If $\mu > \eta 2^\eta$ then the bit is also 0. But the relationship doesn't seem to simplify the quesiton. $\endgroup$ Oct 13, 2010 at 19:43
  • $\begingroup$ there is also a theoretical computer science stackexchange $\endgroup$
    – ohai
    Oct 13, 2010 at 20:34
  • $\begingroup$ @ohai: This site gets more traffic. If I don't get an answer in a reasonable amount of time I will cross post. $\endgroup$ Oct 13, 2010 at 21:00

3 Answers 3

1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Yes, that is the question...can you efficiently get the middle bits $\endgroup$ Oct 14, 2010 at 3:22
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.