c++ - 結果をすばやく計算するための再帰の閉じた形を見つける

Question

次のアルゴリズムがあるとします。

    int com(int a, int b)
    {
        if (b==0 || a==b)
        {

            return(1);
        }
        else 
        {
            return(com(a-1,b) + com(a-1,b-1));
        }
    }

再帰を使用せずにこの結果をより速く計算する方法はありますか？速度を最適化しようとしていますが、このソリューションは遅すぎます。

Answer 1

通常の式は

com(a,b) = a!/(b!(a-b)!)

ここでn！n *（n-1）* ... * 3 * 2*1です。もちろん、計算を高速化するために、互いに打ち消し合う要因を排除できるため、次のことが可能になります。

com(a,b) = a*(a-1)*...*(a-b)/(1*2*..*(a-b))

ただし、深刻な数値計算ではlgamma、独自の階乗関数をロールする代わりに、対数ガンマ関数を使用する必要があります。

com(a,b) = exp(lgamma(a+1)-(lgamma(a-b+1)+lgamma(b+1)))

Answer 2

それらの多く、特に乗法式: http://en.wikipedia.org/wiki/Binomial_coefficient