任何人都可以解釋這個算法來計算大的因子？

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，因爲在每一步我們將乘以由d表示的當前結果在a之前j。內循環是小學乘法算法，其中我們將每個數字乘以j，並在必要時將結果攜帶到q中。

嵌套循環前的p = 0.0和循環內的p += log10(j)只記錄到目前爲止答案中的位數。

順便說一句，我認爲這個程序有一個bug。循環條件應該是i < z不是i <= 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;