Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
2  
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). –  AVS Oct 13 '10 at 19:28
    
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. –  Willie Wong Oct 13 '10 at 19:43
    
there is also a theoretical computer science stackexchange –  ohai Oct 13 '10 at 20:34
    
@ohai: This site gets more traffic. If I don't get an answer in a reasonable amount of time I will cross post. –  dorkusmonkey Oct 13 '10 at 21:00

3 Answers 3

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.

share|improve this answer
    
Yes, that is the question...can you efficiently get the middle bits –  dorkusmonkey Oct 14 '10 at 3:22

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.

share|improve this answer

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?

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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