يمكن للمرء أن يعرف كيف سيكون كبير العاملين قبل حساب ذلك؟
-
12-09-2019 - |
سؤال
أنا أستخدم GMP لحساب فصائل كبيرة جدا (على سبيل المثال 234234!). هل هناك أي طريقة لمعرفة، قبل أن يقوم الحساب، وعدد الأرقام الطويلة أن تكون النتيجة (أو قد)؟
المحلول
ال لوغاريتم العاملين يمكن استخدامها لحساب عدد الأرقام التي سيستغرق الرقم العامل:
يمكن ترجمة هذا بسهولة إلى نموذج الخوارزميات:
//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.Srinivasa Ramanujan طريقة
نعم، انظر تقريب ستيرلينغ
تقول ن! ~ = SQRT (2 * بين)(n / e) ^ n. للحصول على عدد الأرقام، خذ 1 + سجل (ن!) / سجل (10).
ذكرت أن حوالي أربعة أشخاص قد ذكروا ستيرلينغ حتى الآن ... خيار آخر هو تخزين LUT عدد الأرقام لكل من العاملات الأولية الأولى. على افتراض أن 4 بايت للأعتماء و 4 بايت لعدد الأرقام، يمكنك تخزين أول 1،000،000 فصيلة في حوالي 8 ميغابايت.