15.7.3 二項係数

二項係数C(n,k)は，まず最初に k <= n/2の場合はC(n,k) = C(n,n-k)と変換し，しかる後に下記の積をi=2から i=k方向に取って簡略化していきます。

                      k  (n-k+i)
C(n,k) =  (n-k+1) * prod -------
                     i=2    i

各分母iは積に分割できることは簡単に分かるので，完全除算アルゴリズムが利用できます(see Exact Division)。

分子n-k+iと分母iはまず最初にリムサイズに収まる程度まで積を取っておき，なるべく多倍長演算量を抑えるようにします。 mpz_bin_ui関数は除算に対してのみ使うようにします。nは mpz_t型で，n-k+iは一般に1リムに収まるとは限りません。