Berechne Fakultät von großen Zahlen in 0,5 Sekunden mit Python

Question

Ich habe versucht, einen super schnellen Code zu finden, der die Fakultät einer großen Zahl wie 70000 in 0,5 Sekunden berechnen kann, Mein eigener Code könnte es in 10 Sekunden tun Ich habe überall gesucht, jeder Code, den ich finde, hat ein Speicherfehlerproblem oder ist nicht so schnell wie ich es möchte. Kann mir jemand dabei helfen?

enter code here 
import math 
num =int(raw_input()) 
usefrm=0 
if len(str(num)) > 2: 
    if int(str(num)[-2]) % 2 == 0: 
     usefrm = 'even' 
    else: 
     usefrm = 'odd' 
else: 
    if num % 2 == 0: 
     usefrm = 'even1' 
    else: 
     usefrm = 'odd1' 

def picknumber(num): 
    s = str(math.factorial(num)) 
    l = [] 
    for n in s: 
     if int(n) != 0: 
       l.append(int(n)) 
    return l[-1] 

    def picknumber1(num): 
    s = str(num) 
    l = [] 
    for n in s: 
     if int(n) != 0: 
       l.append(int(n)) 
    return l[-1] 
    if usefrm == 'even': 
    e=picknumber1(6*picknumber(int(num/5))*picknumber(int(str(num)[-1]))) 
    if usefrm == 'odd': 
    e=picknumber1(4*picknumber(int(num/5))*picknumber(int(str(num)[-1]))) 
    else: 
    e=picknumber1(math.factorial(num)) 
    print e 

Answer 1

Versuchen Sie, die Kommutativitätseigenschaft der Ganzzahlmultiplikation zu verwenden.

Wenn multiplizierte Zahlen lang sind (sie passen nicht in ein einzelnes Wort), wächst die für die Operation erforderliche Zeit superlinear mit ihrer Länge.

Wenn Sie zuerst die kleinsten (in Bezug auf die Speicherrepräsentation) Faktoren (und Teilprodukte) multiplizieren, sparen Sie möglicherweise viel Zeit.

Answer 2

Für die meisten praktischen Gebrauch ist die Stirling's approximation sehr schnell und sehr genau

import math 
from decimal import Decimal 

def fact(n): 
    d = Decimal(n) 
    return (Decimal(2 * math.pi) * d).sqrt() * (d/Decimal(math.e)) ** d 

print(fact(70000)) 

1.176811014417743803074731978E+308759 

Answer 3

Wenn Sie nicht über eine perfekte Präzision wollen Sie die Annäherung der Stirling können https://en.wikipedia.org/wiki/Stirling's_approximation

import np 
n! ~ np.sqrt(2*np.pi*n)*(n/np.e)**n 

für große n-Werte. Diese Berechnung ist buchstäblich augenblicklich.

Answer 4

Sie können math.factorial() verwenden. Zum Beispiel:

from math import factorial 
factorial(7000) 

mit Ausführungszeit von 20,5 ms zur Berechnung der Fakultät von :

python -m timeit -c "from math import factorial; factorial(7000)" 
10 loops, best of 3: 20.5 msec per loop