1は、階乗はそれを計算する前になりますどのように大きな知っていることはできますか?
-
12-09-2019 - |
質問
私は非常に大きな階乗を計算するためにGMPを使用しています(たとえば、234234を!)。知ってのいずれかの方法は、1つの計算を行う前に、どのように多くの桁が結果を長い間、存在します(または可能性があります)も?
解決
のの対数階乗の階乗数が取ることの桁数を計算するために使用することができます。
これは容易アルゴリズムの形に変換することができます。
//Pseudo-code
function factorialDigits (n)
var result = 0;
for(i = 1; i<=n; i++)
result += log10(n);
return result;
他のヒント
あなたはあなたの番号を取得するには、単純な対数計算を使用してスターリングの近似する式を変換することができます桁のます:
n! ~ sqr(2*pi*n) * (n/e)^n
log10(n!) ~ log10(2*pi*n)/2 + n*log10(n/e)
ハードウェア浮動数学は、それが超高速になりれ、このために十分である。
それは次のようになります。
nlog(n) - n + log(n(1 + 4n(1 + 2n)))/6 + log(pi)/2
@ http://en.wikipedia.org/wiki/Factorialトピック "成長率" を参照してください。 の シュリニヴァーサ・ラマヌジャン方法
さて約4人には、スターリングに言及しているので...別のオプションは、最初のN階乗の各桁の番号を格納するLUTです。桁数の整数のための4バイト、4バイトと仮定すると、あなたの周りの8メガバイトに最初の1,000,000階乗を格納することができます。
所属していません StackOverflow