Fakultät

[Zeratul]

Hallo, ich habe im Moment eine Wette mit einem Freund laufen, wer die höheren Werte der Fakultät ausrechnen kann. Das bisherige Maximum liegt bei 2 Millionen Fakultät, jetzt wollte ich fragen, ob man folgendes Programm noch optimieren könnte:

Code: Alles auswählen

n = int(input('Fakultaet von n = '))
f = 1
for i in range(1, n + 1):
    f = f * i
print(n,'! = ',f)

Könnte man auch das Ergebnis in einer Datei abspeichern anstatt es auszugeben ohne viel Zeit zu verlieren?

Außerdem ist die Prozessorauslastung immer nur bei knapp 30%, ist das das Maximum, was verwendet werden kann oder kann ich dem Programm auch noch mehr zuweisen?

Vielen Dank schonmal!

[BlackJack]

@Zeratul: Ich nehme mal an Dein Prozessor hat nicht nur einen Kern, denn das da lastet einen eigentlich komplett aus. Wenn Du mehr als einen Prozessorkern beschäftigen möchtest, müsstest Du die Berechnung erst einmal parallelisieren können, wofür ich hier aber so direkt keine Möglichkeit sehe.

Du könntest das noch in eine Funktion stecken. In CPython können lokale Namen schneller aufgelöst werden als welche auf Modulebene.

[snafu]

Sind Fremdbibliotheken erlaubt? Wenn ja: Auch welche, die zusätzlich installiert werden müssen oder nur jene, die bei Python mitgeliefert werden? Grundsätzlich könnte man natürlich erstmal auf die factorial()-Funktion aus dem math-Modul umsteigen, anstatt das nachzubauen.

Die Problematik besteht ja im Übrigen nicht nur in der Berechnung, sondern auch in der Darstellung des Ergebnisses. Hier muss nach der Erzeugung einer ziemlich großen Zahl auch noch ein ziemlich großer String erzeugt werden und dieser muss wie auch immer geschrieben bzw angezeigt werden.

[snafu]

Könnte man auch das Ergebnis in einer Datei abspeichern anstatt es auszugeben ohne viel Zeit zu verlieren?

Du könntest, falls es dir nützlich erscheint, die hexadezimale Darstellung der Zahl speichern, um damit die Länge der Textdarstellung zu verkürzen:

Code: Alles auswählen

from math import factorial

N = 600000

def hexify_factorial(n):
    result = factorial(n)
    return '{:X}'.format(result)

def write_factorial(n, filename='factorial.txt'):
    result = hexify_factorial(n)
    with open(filename, 'w') as outfile:
        num_bytes = outfile.write(result)
    return num_bytes

def main():
    num_bytes = write_factorial(N)
    msg = (
        'Needed {:,} bytes to write hexadecimal '
        'representation of factorial({:,})'
    )
    print(msg.format(num_bytes, N))

if __name__ == '__main__':
    main()

Ansonsten wäre noch der Einsatz des pickle-Moduls denkbar oder gleich ein eigenes binäres Format.

[Zeratul]

Ok vielen Dank!

Alle bisher genannten Methoden sind erlaubt. Für 2 Millionen Fakultät braucht der Computer mit dem Code von snafu jetzt nur noch weniger als eine Minute statt mehreren Stunden. Und zusätzlich wird das Ergebnis noch als Datei abgespeichert, das ist uns eigentlich lieber als die Ausgabe.

Ich werde später hier nochmal reinschreiben, wie hoch ich damit komme

[snafu]

Python 3 hat übrigens eine praktische Möglichkeit, um einen Integer als Bytes darzustellen. Habe das mal hier aufgegriffen:

Code: Alles auswählen

from math import factorial

N = 500
FILENAME = 'factorial.txt'

def factorial_as_bytes(n):
    result = factorial(n)
    num_bytes = n
    bytestring = None
    while not bytestring:
        try:
            bytestring = result.to_bytes(
                num_bytes, 'little'
            )
        except OverflowError:
            num_bytes += n
    return bytestring.rstrip(b'\0')

def save_factorial(n, filename):
    result = factorial_as_bytes(n) 
    with open(filename, 'wb') as outfile:
        num_bytes = outfile.write(result)
    return num_bytes

def load_factorial(filename):
    with open(filename, 'rb') as infile:
        bytestring = infile.read()
    return int.from_bytes(bytestring, 'little')

def main():
    num_bytes = save_factorial(N, FILENAME)
    print('Needed', num_bytes, 'bytes to save result')
    result = load_factorial(FILENAME)
    print('Correct?', result == factorial(N))

if __name__ == '__main__':
    main()

[snafu]

Die Schleife zum Umwandeln in Bytes ist übrigens nicht nötig. Daher hier die verbesserte Funktion:

Code: Alles auswählen

def factorial_as_bytes(n):
    result = factorial(n)
    num_bytes = (result.bit_length() + 7) // 8
    return result.to_bytes(num_bytes, 'little')