Kann man wissen, wie groß ein Fakultäts vor der Berechnung es sein würde?
-
12-09-2019 - |
Frage
Ich bin mit GMP sehr großen factorials berechnen (z 234.234!). Gibt es eine Möglichkeit zu wissen, bevor man in die Berechnung, wie viele Ziffern lang wird das Ergebnis (oder könnte) sein?
Lösung
Der Logarithmus des Fakultäts verwendet werden kann, die Anzahl der Stellen zu berechnen, dass die Fakultäts Zahl nehmen:
Dies kann leicht zu einer algorithmischen Form übersetzt werden:
//Pseudo-code
function factorialDigits (n)
var result = 0;
for(i = 1; i<=n; i++)
result += log10(n);
return result;
Andere Tipps
Sie können die Transformation Stirling Annäherung Formel einfach logarithmisch Mathematik verwenden Sie die Nummer zu bekommen die Stellen:
n! ~ sqr(2*pi*n) * (n/e)^n
log10(n!) ~ log10(2*pi*n)/2 + n*log10(n/e)
Hardware float Mathematik ist dafür ausreichend, was es macht blitzschnell.
es sei
nlog(n) - n + log(n(1 + 4n(1 + 2n)))/6 + log(pi)/2
siehe Thema "Wachstumsrate" @ http://en.wikipedia.org/wiki/Factorial Srinivasa Ramanujan Methode
Ja, finden Sie unter Stirling Annäherung
Es heißt n! ~ = Sqrt (2 * Pi n) (n / e) ^ n. Um die Anzahl der Ziffern zu erhalten, nehmen 1 + log (n!) / Log (10).
Nun etwa vier Leute haben erwähnt, Stirling so ... eine weitere Option, eine LUT ist die Anzahl der Stellen für jede der ersten N factorials speichern. Unter der Annahme, 4 Bytes für die ganze Zahl und 4 Byte für die Anzahl der Stellen, die ersten 1.000.000 factorials in rund 8 MB speichern kann.