Skutecznie uzyskuje bity N! ?

Biorąc pod uwagę i , czy możliwe jest uzyskanie M -tego bitu (lub cyfry dowolnej małej podstawy) N! w czasie / przestrzeni O (P (ln (N), LN (M))) , gdzie p (x, y) jest kilka funkcji wielomianowej w X i Y ?M M N $N$$M$$M$$N!$p ( x , y ) x $O( p( ln(N), ln(M) ) )$$p(x, y)$$x$$y$

tzn. Biorąc pod uwagę $N = 2^\eta$ , $M = 2^\mu$ (z $N$ , $M \in \mathbb{Z}$ ), znajdź bit $2^\mu$ z $(2^\eta)!$w $O( p(\eta, \mu) )$ .

Uwaga: zapytałem o to tutaj na mathoverflow.net i nie otrzymałem żadnych odpowiedzi, więc napisałem do siebie.

Z komentarza na drugiej stronie Gene Kopp zwraca uwagę, że można efektywnie obliczyć bity niższego rzędu, wykonując modularne bity arytmetyczne i bity wyższego rzędu przy użyciu aproksymacji Stirlinga, więc pytanie brzmi „jak skutecznie można obliczyć bity środkowego rzędu?”. .

Dick Lipton ma piękny post z 2009 roku na temat związku funkcji czynnikowej z faktoringiem. Jest wiele rzeczy niezwiązanych z tym pytaniem, ale jednym istotnym punktem jest to twierdzenie:

Jeślimożna obliczyć za pomocą obliczeń arytmetycznych po linii prostej w krokach , a następnie faktoring ma obwody wielomianowe.O ( log c n $n!$$O(\log^{c} n)$

Podejrzewam, że jest to dowód na to, że na twoje pytanie, szczególnie w podanych terminach, trudno będzie odpowiedzieć.

Odpowiedź Suresha prawdopodobnie odpowiada na twoje pytanie, ale pomyślałem, że zwrócę uwagę na szczególny przypadek. Zawsze możesz obliczyć wynik dla mniej znaczących cyfr dla dowolnej bazy. Weź jako naszą bazę.$p$

Oczywiście każdy ^piąty wyraz w silni jest wielokrotnością . Każdy ^p termin jest wielokrotnością , i tak dalej, o najwyższej mocy , który jest czynnikiemto . jest łatwy do przybliżenia przez przybliżenie Stirlingsa: . Ponadto, więc sumę zawsze można skutecznie obliczyć, sumując zamiast (od( p 2 ) p 2 p N ! X p = ∑ ⌊ log p ( N ! ) ⌋ i = 1 ⌊ $p$$(p^2)$$p^2$$p$$N!$logp(N!)lnN! ≈N$X_p = \sum_{i=1}^{\lfloor \log_p(N!) \rfloor} \lfloor \frac{N}{p^i}\rfloor$$\log_p(N!)$$\ln N! \approx N \ln N - N$$p^{N \lceil \log_p (N) \rceil} > N!$$1 \leq i \leq {N \lceil \log_p (N) \rceil}$$\lfloor \frac{N}{p^i}\rfloor = 0$dla ).$i > {\lfloor \log_p(N!) \rfloor}$

Zatem ostatnie cyfry zmają zero w podstawie . N ! $X_p$$N!$$p$