C++ - 階乗の多桁計算！

以前、コンピュータで大きな桁数を計算する概念・アルゴリズムを紹介しました。

• C++ - 多桁計算！

今回は、階乗(n!)を多桁計算するアルゴリズムについてです。

0. 前提条件

• Linux Mint 14 Nadia (64bit) での作業を想定。
• g++ (Ubuntu/Linaro 4.7.2-2ubuntu1) 4.7.2

また、当方の環境で扱える int 型の範囲は -2,147,483,648 〜 2,147,483,647 であることから、

• 多桁計算で使用する1つの配列のサイズは8桁としている。

1. 計算概要

1! から 49! までをそれぞれ 64 桁まで計算する。
ループ処理を行うが、実際には順次１つ前の計算結果に乗算していく形となる。
ちなみに、50! は 65 桁になってしまうので、今回は 49! までとしているが、桁数を増やせば対応可能。

2. C++ ソース作成

例として、以下のようにソースを作成した。
ソース内の計算個数 N を変更し、計算桁数 L を格納可能な桁数に変更すれば、任意の個数・桁数を計算可能。
仮に、N を大きくして結果が L 桁で収まらなくても、エラーにはしないようにしている。

File: calc_factorial.cpp

/*********************************************
 * 階乗計算（1! - 49! 各 64 桁）
 *********************************************/
#include <iostream>  // for cout
#include <stdio.h>   // for printf()

#define L  64             // 計算桁数
#define L2 ((L + 7) / 8)  // 配列サイズ
#define N  49             // 計算個数

using namespace std;

/*
 * 計算クラス
 */
class Calc
{
    // 各種変数
    int k, i;   // LOOP インデックス
    int carry;  // 繰り上がり
    long w;     // 被乗数ワーク

    public:
        // 計算
        void calc();
        // ロング * ショート
        void lmul(int *, int, int *);
        // 結果出力
        void display(int *);
};

/*
 * 計算
 */
void Calc::calc()
{
    // 配列宣言
    int s[L2];

    // 配列初期化
    for (k = 0; k < L2 - 1; k++)
        s[k] = 0;
    s[L2 - 1] = 1;

    for (k = 1; k <= N; k++) {
        // 計算
        lmul(s, k, s);

        // 結果出力
        printf("%2d!=", k);
        display(s);
    }
}

/*
 * ロング * ショート
 */
void Calc::lmul(int a[], int b, int c[])
{
    carry = 0;
    for (i = L2 - 1; i >=0; i--) {
        w = a[i];
        c[i] = (w * b + carry) % 100000000;
        carry = (w * b + carry) / 100000000;
    }
}

/*
 * 結果出力
 */
void Calc::display(int s[])
{
    for (i = 0; i < L2; i++)
        printf("%08d", s[i]);
    printf("\n");
}

/*
 * メイン処理
 */
int main()
{
    try
    {
        // 計算クラスインスタンス化
        Calc objCalc;

        // 階乗計算
        objCalc.calc();
    }
    catch (...) {
        cout << "例外発生！" << endl;
        return -1;
    }

    // 正常終了
    return 0;
}

• Gist - C++ source code to compute factorials.

3. C++ ソースコンパイル

$ g++ calc_factorial.cpp -o calc_factorial

何も出力されなければ成功です。

4. 実行

$ ./calc_factorial
 1!=0000000000000000000000000000000000000000000000000000000000000001
 2!=0000000000000000000000000000000000000000000000000000000000000002
 3!=0000000000000000000000000000000000000000000000000000000000000006
 4!=0000000000000000000000000000000000000000000000000000000000000024
 5!=0000000000000000000000000000000000000000000000000000000000000120
 6!=0000000000000000000000000000000000000000000000000000000000000720
 7!=0000000000000000000000000000000000000000000000000000000000005040
 8!=0000000000000000000000000000000000000000000000000000000000040320
 9!=0000000000000000000000000000000000000000000000000000000000362880
10!=0000000000000000000000000000000000000000000000000000000003628800
11!=0000000000000000000000000000000000000000000000000000000039916800
12!=0000000000000000000000000000000000000000000000000000000479001600
13!=0000000000000000000000000000000000000000000000000000006227020800
14!=0000000000000000000000000000000000000000000000000000087178291200
15!=0000000000000000000000000000000000000000000000000001307674368000
16!=0000000000000000000000000000000000000000000000000020922789888000
17!=0000000000000000000000000000000000000000000000000355687428096000
18!=0000000000000000000000000000000000000000000000006402373705728000
19!=0000000000000000000000000000000000000000000000121645100408832000
20!=0000000000000000000000000000000000000000000002432902008176640000
21!=0000000000000000000000000000000000000000000051090942171709440000
22!=0000000000000000000000000000000000000000001124000727777607680000
23!=0000000000000000000000000000000000000000025852016738884976640000
24!=0000000000000000000000000000000000000000620448401733239439360000
25!=0000000000000000000000000000000000000015511210043330985984000000
26!=0000000000000000000000000000000000000403291461126605635584000000
27!=0000000000000000000000000000000000010888869450418352160768000000
28!=0000000000000000000000000000000000304888344611713860501504000000
29!=0000000000000000000000000000000008841761993739701954543616000000
30!=0000000000000000000000000000000265252859812191058636308480000000
31!=0000000000000000000000000000008222838654177922817725562880000000
32!=0000000000000000000000000000263130836933693530167218012160000000
33!=0000000000000000000000000008683317618811886495518194401280000000
34!=0000000000000000000000000295232799039604140847618609643520000000
35!=0000000000000000000000010333147966386144929666651337523200000000
36!=0000000000000000000000371993326789901217467999448150835200000000
37!=0000000000000000000013763753091226345046315979581580902400000000
38!=0000000000000000000523022617466601111760007224100074291200000000
39!=0000000000000000020397882081197443358640281739902897356800000000
40!=0000000000000000815915283247897734345611269596115894272000000000
41!=0000000000000033452526613163807108170062053440751665152000000000
42!=0000000000001405006117752879898543142606244511569936384000000000
43!=0000000000060415263063373835637355132068513997507264512000000000
44!=0000000002658271574788448768043625811014615890319638528000000000
45!=0000000119622220865480194561963161495657715064383733760000000000
46!=0000005502622159812088949850305428800254892961651752960000000000
47!=0000258623241511168180642964355153611979969197632389120000000000
48!=0012413915592536072670862289047373375038521486354677760000000000
49!=0608281864034267560872252163321295376887552831379210240000000000

当方の非力なマシンでも瞬時に終了した。
自分の環境と相談して、計算する桁数を大きくしてみるのもよいでしょう。

---

やはり、「多桁（多倍長）計算は計算機に限る」というを実感できます。

※ちなみに最近の当方の C++ アルゴリズムについての記事は、古い C によるアルゴリズムに関する書物を参考に C++ に移植した形態となっています。

以上。