数値計算を行う場合、アルゴリズムを変えてみるとぐっと速度が上がることがあります。
階乗とは
念のため説明しておきますが、「$x$の階乗」は「1から$x$までの数をかけ合わせた数」のことで1、「$x!$」と書き表します。ビックリマークがついているように、急速に大きくなっていきます。
なお、あっという間に64ビット整数も超えてしまうので、多倍長整数を前提とします。
掛け算の性質
どうあがいても大量の掛け算は避けられないので、まずはその性質について吟味しておきます。
以前Rubyで行った試験の結果から、「掛け算の所要時間は大きい方の桁数×小さい方の桁数の平方根に比例する」ことが分かりました（Karatuba法やToom-3法を使う場合には、ほぼ共通する結果だと思います）。
ということで、「できるだけ同じ大きさの数同士で掛け算を繰り返す」ようにするだけでも、かなり高速化しました。
2の成分
高速な計算を行う上で、「2の累乗」と「奇数成分」を分離して計算を進めることが有力な方法となります。というのも、コンピューターが2進法で動くものなので、「2の累乗をかける」ことは単なる「ビットシフト」というごく軽い演算となるからです。
そして、$n! = 2^x\times (2k+1)$ というように分けた場合、$x$は「$n$から、『$n$を2進法で表したときの1の数』を引いたもの」となります（この事実自体は、数学的帰納法で証明できます）。「1の数」はx64に専用命令が積まれるぐらいに最適化がなされているので、階乗の2の累乗成分は高速に計算可能です。
奇数パートの計算法その1 素因数分解
いちばんシンプルに考えて、「階乗を素因数分解してしまう」という方法があります。例えば、「100!に含まれる3の累乗はどれだけか」を考えてみると、
- 1～100で、3で割り切れる数…100/3→33個
- 1～100で、$3^2$で割り切れる数…33/3→11個
- 1～100で、$3^3$で割り切れる数…11/3→4個
- 1～100で、$3^4$で割り切れる数…4/3→1個
ということで、33+11+4+1=49となります。これは100まですべての数を当たらなくてもいいので、効率的に各素因数について計算できます。
そのうえで、累乗して掛け合わせていくのですが、これまた累乗してからかけるより、バイナリ法などで全部の素数について一気に累乗＆掛け算とするほうが高速になります。
この手法は、素数テーブルの生成時間を無視できるならかなり高速です。
奇数パートの計算法その2 奇数以上に分解しない
では、素因数分解のコストを払いたくないという状況では、どのような方法を使えるでしょうか。素因数分解しない「奇数」単体で考えても、同じものは複数回登場します。
- 100/2=50→51～99までの奇数は1回だけ
- 50/2=25→27～49の奇数は2回（27、27×2）
- 25/2=12.5→13～25の奇数は3回（13、13×2、13×4）
- 12/2=6→7～11の奇数は4回（7、14、28、56）
- 6/2=3→5は5回（5、10、20、40、80）
- 3/2=1→3は6回（3、6、12、24、48、96）
このように分類したところで、また適宜掛け合わせれば、そこそこの速度で動きます。
-
なお、$0!=1$ という約束になっています。 ↩