Schnelle Algorithmen für die Berechnung der Fakultät

Question

Ich fand this page beschreibt eine Reihe von Algorithmen zur Berechnung der Fakultät. Leider sind die Erklärungen kurz und ich habe keine Lust, Zeile um Zeile des Quellcodes zu durchforsten, um die grundlegenden Prinzipien hinter den Algorithmen zu verstehen.

Kann mich jemand auf detailliertere Beschreibungen dieser (oder anderer schneller) Algorithmen zur Berechnung der Fakultät hinweisen?

Bearbeiten:This page beschreibt die Methode der Primfaktorzerlegung, die Technik aller faktoriellen Algorithmen mit der besten Leistung. Es enthält auch einige schöne Beispiel-Code in Python. Der Autor verlinkt auf a description of binary splitting und verweist auf einen Artikel im Journal of Algorithms ("Über die Komplexität der Berechnung von Faktoren"), der vielversprechend aussieht, wenn ich nur in die Finger bekommen könnte.

Answer 1

Schauen Sie sich diese paper (PDF link) von Richard Fateman. Die Code-Beispiele sind in Lisp, aber in jedem Fall läuft ein Großteil des Geheimnisses darauf hinaus, die Anzahl der Bignum-Berechnungen (arbitrary precision integer) zu minimieren, die Sie durchführen müssen.

Natürlich, wenn Sie bignums nicht benötigen/haben, ist es trivial; entweder eine Nachschlagetabelle oder eine einfache Schleife ist in Ordnung.

EDIT: Wenn Sie eine ungefähre Antwort verwenden können, können Sie entweder den Logarithmus des Fakultäts berechnen direkt von log(k) für k = 2 ... n Summieren oder durch die ehrwürdigen Stirling approximation verwenden. Sie möchten möglichst mit dem Logarithmus arbeiten, um Überlauf zu vermeiden. insbesondere wird eine naive Anwendung der Stirling-Approximation an vielen Stellen überlaufen, wo es nicht notwendig ist.

Answer 2

Es gibt auch eine andere Methode. Diese Methode ist detailliert here, die die Menge der Multiplikation für ein wenig Addition und Subtraktion halbiert. Sie wollen wahrscheinlich die erste Methode gezeigt, und die zweite Methode ist eine interessante Lektüre, wenn Sie es verstehen können.