by Xguru
又說階乘，這是老生常談了吧。想都不用想，一個遞歸輕松搞定！
int factorial(int n)
{
if( n == 1)
return 1;
return n * factorial(n-1);
}或者你覺得遞歸效率沒有尾遞歸來的好 ，大筆一揮。
long fact_iter(long product, long counter, long maxcount)
{
return (counter > maxcount) ? product : fact_iter(product*counter, counter+1, maxcount);
}
long factorial(long n)
{
return fact_iter(1, 1, n);
}
或者你看過《代碼大全》上面說過：“如果為我工作的程序員用遞歸去計算階乘，那么我寧愿換人。”
使用遞歸求階乘速度緩慢，無法預測運行期間內存使用情況，難以理解。于是你把遞歸改成了循環語句。
int factorial(int n)
{
int result = 1;
for(int i = 2 ; i <= n; i++)
{
result = result * i;
}
return result;
}
當你寫下這些代碼的時候，會不會覺得少了些什么？
在我的32位環境上測試一下，計算到33!的時候的溢出了，于是你會說，這是int的值太小了嘛，于是你換了個long double，測試一下，什么玩意嘛這是，數再大一點的話也不行了。
那就改用鏈表或者數組表示吧，鏈表的速度就太慢了，用數組吧。
int factorial2(int n,int a[])
{
int carry;
int digit = 1;
a[0] = 1;
int temp;
for(int i = 2; i <= n; ++i)
{
for(int j = 1, carry = 0; j <= digit; ++j)
{
temp = a[j-1] * i + carry;
a[j-1] = temp % 10;
carry = temp / 10;
}
while(carry)
{
a[++digit-1] = carry % 10;
carry /= 10;
}
}
return --digit;
}
這個算法模擬手工計算的過程，將結果保存在a數組中，返回的是結果的位數
你在這個時候是不是感覺輕飄飄了呢？請暫時打住。
如果我要求一個10W以上大數的一個科學計數法的表達式呢？或者是問你，求10W 級別上的N！左邊第三位的數字是多少？呃，這個是數學家的事了吧？振作精神，來挑戰自我吧！真正的程序員需要的就是這種追根究底的精神。
來試試數學分析方法，James Stirling這位蘇格蘭數學家，280多年前就給出了這個極限式子
這個式子能用極快的速度求出n!的近似值，也可以使用它來無限接近準確結果。具體的介紹和證明過程在這里 或者 這里。
斯特靈級數公式
下面的代碼是求大數N！科學計數法表示
struct bigNum
{
double n; //尾數
int e; //指數
};
void factorial3(struct bigNum *p,int n)
{
double logx,s,item;//s:級數的和 item:級數的每一項
int i;
logx = n* log10((double)n/E);
p->e = (int)(logx); p->n= pow(10.0, logx-p->e);
p->n *= sqrt( 2* PI* (double)n);
for (item=1.0,s=0.0,i=0;i<sizeof(a1)/sizeof(double);i++)
{
s += item * a1[i];
item /= (double)n;
}
p->n *=s;
}
下面這個是階乘的對數的漸近展開式
void factorial3b(struct bigNum *p,int n)
{
double logR;
double s,item;
int i;
logR=0.5*log(2.0*PI)+((double)n+0.5)*log(n)-(double)n;
for (item=1/(double)n,s=0.0,i=0;i<sizeof(a2)/sizeof(double);i++)
{
s+= item * a2[i];
item /= (double)(n)* (double)n;
}
logR+=s;
p->e = (int)( logR / log(10));//換底公式
p->n = pow(10.00, logR/log(10) - p->e);
}
要是求階層的位數也是特別簡單
double getFactorialLength(int n)
{
return (n * log(double(n)) - n + 0.5 * log(2.0 * n * PI )) / log(10.0)+1;
}
這個求出來的是位數的近似數，或者是改進一下，使用ceil函數來求出不小于給定實數的最小整數。
int getFactorialLength(int n)
{
if( n == 1 )
return 1;
else
return (int)ceil((N*log(N)-N+log(2*N*PI)/2)/log(10));
}
到此，你會不由感嘆：計算機科學中最閃光，最精髓，最本質的東西還是數學！
芒德布羅集合的邊界
最后用羅素的話結束這篇隨筆：
Mathematics, rightly viewed, possesses not only truth, but supreme beauty — a beauty cold and austere, like that of sculpture, without appeal to any part of our weaker nature, without the gorgeous trappings of painting or music, yet sublimely pure, and capable of a stern perfection such as only the greatest art can show. The true spirit of delight, the exaltation, the sense of being more than Man, which is the touchstone of the highest excellence, is to be found in mathematics as surely as poetry.
參考資料
1.Tom M. Apostol.《數學分析, 微積分》(Mathematical Analysis)
2.Steve McConnell.《代碼大全（第二版）》(CODE COMPLETE, Second Edition)
3.http://en.wikipedia.org/wiki/Stirling_approximation#History
4.http://mathworld.wolfram.com/StirlingsApproximation.html
5.http://zh.straightworldbank.com/wiki/%E6%96%AF%E7%89%B9%E6%9E%97%E5%85%AC%E5%BC%8F