序

コーディングテストで出たfactorialで連続WAするという、何日経っても忘れられない失態を犯してしまったため、供養としてfactorialに関して解説したいと思う。

概念

Wikipediaには次のようにある。

数学において非負整数 n の階乗（かいじょう、英: factorial）n ! は、1 から n までのすべての整数の積である。例えば、

6! = 6 × 5 × 4 × 3 × 2 × 1 = 720

である。空積の規約のもと 0! = 1 と定義する。

典型的解

def fact(n)
  return n <= 1 ? n : n * fact(n-1)
end

もう少しスマートに書くと次のようになる(わずかに速い)

def fact(n)
  n <= 1 ? 1 : n * fact(n-1)
end

これは、競技プログラミング レベル1って感じである。

典型的解の問題

このような関数はnが十分に小さい場合、多くの言語で有効に機能する。 RubyはBignumを持ち、Fixnumからシームレスに移行する(最近のRubyでは統合されてIntegerになっている)ため、他の言語と比べると大きなnに対応できる。

例えばPerlでは

sub fact {
  return($_[0] <= 1 ? $_[0] : $_[0] * fact($_[0] - 1));
}

19までは出せる

2432902008176640000

が、20からは指数表記となり

5.10909421717094e+19

171でInfとなってしまう。

Rubyの場合、n == 10 ** 4であれば大丈夫だが、n == 10 ** 5になると

% ruby fact.rb
Traceback (most recent call last):
    10080: from fact.rb:5:in `<main>'
    10079: from fact.rb:2:in `fact'
    10078: from fact.rb:2:in `fact'
    10077: from fact.rb:2:in `fact'
    10076: from fact.rb:2:in `fact'
    10075: from fact.rb:2:in `fact'
    10074: from fact.rb:2:in `fact'
    10073: from fact.rb:2:in `fact'
     ... 10068 levels...
        4: from fact.rb:2:in `fact'
        3: from fact.rb:2:in `fact'
        2: from fact.rb:2:in `fact'
        1: from fact.rb:2:in `fact'
fact.rb:2:in `fact': stack level too deep (SystemStackError)

の通りだ。

主な問題は2つある。

第一に、整数の表現方法だ。 多くの言語処理系が整数値は符号付き32ビット整数であり、簡単にあふれてしまう。 階乗を計算するには、仮に符号付き64ビット整数でも足りない。

桁溢れに対応するのは競技プログラミング レベル2といったところ。

このことから、非常に多くの言語処理系でBignum(BigINT)ライブラリを必要とする。

もうひとつはコールスタックだ。 末尾呼び出し最適化を行わない言語処理系ではループなんかよりはるかに小さな値でコールスタックが溢れてしまう。

Rubyでループでがんばる

実はループで書くほうがずっと簡単。

puts (1..n).inject(1, :*)

これでn == 10 ** 5なら普通に解けるが、N == 10 ** 6だとTLEまっしぐら。手元では8分半かかった。 (C++ならできたりするかもしれない)

これで競技プログラミング レベル2.5といったところ。

競技プログラミング レベル4な解

ビットシフトを使う、という計算機科学的な知識と、素因数分解などの数学知識を駆使すると、さらに速くなる。 現実的に、これらの方法で解を求めるのが階乗としての速度の限界であり、本格的な競技プログラミングの問題として出題されるレベルになる。

残念ながら、私は速くなる理屈は理解できても、式を立てるには数学力が足りないので、このレベルの回答はできない。 問題レベルとしてはAtCoder 水色以上と思われるので、式を立てられる方は、ぜひコメントにてご教授ください。