階乗の高速計算

C# アルゴリズム

nCrの計算が高速にできたので，それを使ってn!の値の高速計算にも利用できないかなーと思って実験してみた．
任意のnについて

n!=(\frac{n}{2} !)^2 \cdot _nC_{\frac{n}{2}}(n:偶数)

n!=(\lfloor \frac{n}{2} \rfloor !)^2 \cdot _nC_{\lfloor \frac{n}{2} \rfloor} \cdot \frac{n+1}{2}(n:奇数)

が成り立つので，分割統治法で計算できる．

public static BigInteger Factorial(int n)
{
    if ((n & 1) == 0) return Factorial(n / 2).Square() * Combination(n, n / 2);
    else return Factorial(n / 2).Square() * Combination(n, n / 2) * (n - n / 2);
}

かなり高速に階乗を計算するらしいPeter Luschny氏のPrimeSwing，SplitRecursiveと比較してみた．
CombinationRecursiveが今回作ってみたもの．
ただし全て手前実装なので，正しい比較かどうかは微妙．．．

apfloatとか使わずにBigIntegerだけで書いているせいあって，速度的には氏の結果より圧倒的に遅い．．