क्या कोई बड़े कारखानों की गणना के लिए इस एल्गोरिदम को समझा सकता है?

Question

मैं बड़े फैक्ट्रोरियल (100 जितनी बड़ी संख्या) की गणना के लिए निम्नलिखित कार्यक्रम में आया हूं .. क्या कोई मुझे इस एल्गोरिदम में उपयोग किए जाने वाले मूलभूत विचार को समझा सकता है ?? मुझे फैक्टरियल की गणना करने में लागू गणित को जानने की आवश्यकता है।

#include <cmath> 
#include <iostream> 
#include <cstdlib> 

using namespace std; 

int main() 
{ 

     unsigned int d; 

     unsigned char *a; 

     unsigned int j, n, q, z, t; 

     int i,arr[101],f; 

     double p; 


    cin>>n; 
    p = 0.0; 
    for(j = 2; j <= n; j++) 
     p += log10(j); 
    d = (int)p + 1; 
    a = new unsigned char[d]; 
    for (i = 1; i < d; i++) 
     a[i] = 0; //initialize 
    a[0] = 1; 
    p = 0.0; 
    for (j = 2; j <= n; j++) 
    { 
     q = 0; 
     p += log10(j); 
     z = (int)p + 1; 
     for (i = 0; i <= z/*NUMDIGITS*/; i++) 
     { 
      t = (a[i] * j) + q; 
      q = (t/10); 
      a[i] = (char)(t % 10); 
     } 

    } 
    for(i = d -1; i >= 0; i--) 
     cout << (int)a[i]; 
    cout<<"\n"; 
    delete []a; 

return 0; 
} 

Answer 1

ध्यान दें कि

n! = 2 * 3 * ... * n 

तो

कि

log(n!) = log(2 * 3 * ... * n) = log(2) + log(3) + ... + log(n) 

यह महत्वपूर्ण है क्योंकि अगर k एक सकारात्मक पूर्णांक है तो log(k) की छत आधार -10 में अंकों की संख्या है k का प्रतिनिधित्व। इस प्रकार, कोड की ये पंक्तियां n! में अंकों की संख्या की गणना कर रही हैं।

p = 0.0; 
for(j = 2; j <= n; j++) 
    p += log10(j); 
d = (int)p + 1; 

फिर, कोड की इन पंक्तियों के अंतरिक्ष आवंटित n! के अंकों धारण करने के लिए:

a = new unsigned char[d]; 
for (i = 1; i < d; i++) 
    a[i] = 0; //initialize 

फिर हम सिर्फ ग्रेड स्कूल गुणा एल्गोरिथ्म करना

p = 0.0; 
for (j = 2; j <= n; j++) { 
    q = 0; 
    p += log10(j); 
    z = (int)p + 1; 
    for (i = 0; i <= z/*NUMDIGITS*/; i++) { 
     t = (a[i] * j) + q; 
     q = (t/10); 
     a[i] = (char)(t % 10); 
    } 
} 

बाहरी पाश है j से 2 से n से चल रहा है क्योंकि प्रत्येक चरण में हम वर्तमान परिणाम को गुणा करेंगे a में j द्वारा igits। आंतरिक लूप ग्रेड-स्कूल गुणा एल्गोरिदम है जिसमें हम प्रत्येक अंक को j से गुणा करते हैं और यदि आवश्यक हो तो परिणाम q में ले जाएं।

लूप के अंदर नेस्टेड लूप और p += log10(j) से पहले p = 0.0 बस उत्तर में अंकों की संख्या का ट्रैक रखें।

संयोग से, मुझे लगता है कि कार्यक्रम के इस हिस्से में एक बग है। लूप स्थिति i < zi <= z नहीं होनी चाहिए अन्यथा हम a के अंत में z == d के अंत में लिखेंगे, जो j == n पर निश्चित रूप से होगा। इस प्रकार से

for (i = 0; i < z/*NUMDIGITS*/; i++) 

for (i = 0; i <= z/*NUMDIGITS*/; i++) 

की जगह फिर हम सिर्फ अंक

for(i = d -1; i >= 0; i--) 
    cout << (int)a[i]; 
cout<<"\n"; 

और मुफ्त आवंटित स्मृति

delete []a;