【Java】プリミティブ型での階乗計算

2016/01/29 Fri [edit]

　任意精度整数での階乗計算との比較用にプリミティブ型での階乗計算も書いておこう。プリミティブ型では常に桁あふれ(オーバフロー)の危険が伴うが、任意精度整数(多倍長整数)[BigInteger]での階乗計算からすると約35倍速いというメリットがある。ちなみに桁あふれするのは 21! からで、20! までは問題なく使える。なので、あらかじめ値の範囲がわかっていれば使うのも１つの手だ。

　また、ちょっとした計算として使うなら、オーバーフローの心配のない Ruby 版を使うのも良い。開発環境がなくてもオンラインIDEで十分だろう。

　コードの書き方はいくつかあると思うが、一番簡単で高速だった while ループを用いた方法で書いてみる。

●while ループでの階乗計算

/**<h1>階乗 (n!) を求める</h1>
 * <p>21! でオーバーフローになる。
 * <br>1! = 1 / 0! = 1 / 負の値は 1 (不正値) となる。</p>
 * @param n ： 0～20! まで (負の値は不可)
 * @return<b>long</b> ： 階乗 (n!)
 */
public static final long factorial(int n) {
    long sum = 1;
    while (n > 1) {
        sum *= n--;
    }
    return sum;
}


//メインでは...
int n = 20;
long l = factorial(n);
System.out.println(l);

　コードはあまりにも簡単なので説明する必要はないだろう。例外処理は手抜きしているが、負の階乗はないので、n < 0 のとき、ArithmeticException などをスローするように付け加えても良いだろう（このコードでは 1 が返る）。桁あふれが心配なら、while ループ内に「if (n < 0) ～[例外処理]～」を入れても良いが、大量に計算する場合は実行速度は少し落ちる。

　あと、戻値が long で計算されているが、double にしても良い。long では桁あふれしたとき、負の値になるが（long の上限は Long.MAX_VALUE で確認できる）、double の場合、上から17桁より以降は丸められ、下の桁はすべて 0 に置き換わるという感じになる。指数形式で大まかな値を知りたいだけなら十分使える。ただし、表示するにはキャストしたり、フォーマット[String.format()]したりしないと見づらいので、ちょっと工夫が必要になる。また、計算速度は long でも double でも変わらない。これも使い途はケース・バイ・ケースだろう。

　もちろん、前回の任意精度整数[BigInteger]での階乗計算と同じ for ループの書き方でも良い。実際に私はこちらのコードを BigInteger に置き換えた。ただし、プリミティブ型の場合は for ループの方がわずかに実行速度が遅かった（といっても決定的な差はないのでどちらでも良い）。BigInteger の場合は while ループ（というより逆順で計算）すると重くなるので、for ループの方を採用したわけだ。書き方で微妙に実行速度が変わることがあるので、色々試してみると良いかもしれない。

●for ループでの階乗計算

public static final long factorial(final int n) {
    long sum = 1;
    for (int i = 2; i <= n; i++) {
        sum *= i;
    }
    return sum;
}

//※メインは先の例と同じで良い

　あともう１つは有名な(笑)再帰で書く方法だろうか。これってたぶん再帰プログラムを説明するのにわかりやすかったから書かれたのだと思うが、意外なほどに例が多い。実際には再帰を単純計算で用いるメリットはほとんどなく（シンプルで見やすいくらい？）、無駄にスタックメモリを喰い、計算速度も２倍以上劣るので、勉強用（実験用）くらいに留めておいた方が良いだろう。ループの入れ子が動的であったり、バックトラックを必要としたりしない計算ならば、単純なループの方が実行速度は格段に速い。あと、10000 回を超えて再帰すると、Stack Overflow を起こして停止することがあるので、注意する必要がある（この階乗計算場合、どのみち 20! までしか使えないのでそれほど問題はないが）[→計算時間は任意精度整数での記事を参考に]。

●再帰での階乗計算

public static final long factorial(final int n) {
    if (n < 2) {
        return 1;
    }
    return n * factorial(n - 1);
}

//※メインは先の例と同じで良い

　最後に前回の任意精度整数[BigInteger]での階乗計算と今回のプリミティブ型での階乗計算（long を double に書き換えたものも含む）での計算結果を比較してみよう。どのコードを使うかは求める答えや実行速度などに合わせて、自由に選べば良いと思う。

●long, double, BigInteger で階乗計算した結果の比較

0!
long       = 1
double     = 1
BigInteger = 1
1!
long       = 1
double     = 1
BigInteger = 1
2!
long       = 2
double     = 2
BigInteger = 2
3!
long       = 6
double     = 6
BigInteger = 6
4!
long       = 24
double     = 24
BigInteger = 24
5!
long       = 120
double     = 120
BigInteger = 120
6!
long       = 720
double     = 720
BigInteger = 720
7!
long       = 5040
double     = 5040
BigInteger = 5040
8!
long       = 40320
double     = 40320
BigInteger = 40320
9!
long       = 362880
double     = 362880
BigInteger = 362880
10!
long       = 3628800
double     = 3628800
BigInteger = 3628800
11!
long       = 39916800
double     = 39916800
BigInteger = 39916800
12!
long       = 479001600
double     = 479001600
BigInteger = 479001600
13!
long       = 6227020800
double     = 6227020800
BigInteger = 6227020800
14!
long       = 87178291200
double     = 87178291200
BigInteger = 87178291200
15!
long       = 1307674368000
double     = 1307674368000
BigInteger = 1307674368000
16!
long       = 20922789888000
double     = 20922789888000
BigInteger = 20922789888000
17!
long       = 355687428096000
double     = 355687428096000
BigInteger = 355687428096000
18!
long       = 6402373705728000
double     = 6402373705728000
BigInteger = 6402373705728000
19!
long       = 121645100408832000
double     = 121645100408832000
BigInteger = 121645100408832000
20!
long       = 2432902008176640000
double     = 2432902008176640000
BigInteger = 2432902008176640000
21!
long       = -4249290049419214848    //←ここでオーバフロー
double     = 51090942171709440000
BigInteger = 51090942171709440000
22!
long       = -1250660718674968576
double     = 1124000727777607700000    //←上から17桁以降は丸められる(0で埋まる[指数形式])
BigInteger = 1124000727777607680000
23!
long       = 8128291617894825984
double     = 25852016738884980000000
BigInteger = 25852016738884976640000
24!
long       = -7835185981329244160
double     = 620448401733239400000000
BigInteger = 620448401733239439360000
25!
long       = 7034535277573963776
double     = 15511210043330984000000000
BigInteger = 15511210043330985984000000
26!
long       = -1569523520172457984
double     = 403291461126605700000000000
BigInteger = 403291461126605635584000000
27!
long       = -5483646897237262336
double     = 10888869450418352000000000000
BigInteger = 10888869450418352160768000000
28!
long       = -5968160532966932480
double     = 304888344611713800000000000000
BigInteger = 304888344611713860501504000000
29!
long       = -7055958792655077376
double     = 8841761993739701000000000000000
BigInteger = 8841761993739701954543616000000
30!
long       = -8764578968847253504
double     = 265252859812191100000000000000000
BigInteger = 265252859812191058636308480000000
31!
long       = 4999213071378415616
double     = 8222838654177924000000000000000000
BigInteger = 8222838654177922817725562880000000
32!
long       = -6045878379276664832
double     = 263130836933693550000000000000000000
BigInteger = 263130836933693530167218012160000000
33!
long       = 3400198294675128320
double     = 8683317618811890000000000000000000000
BigInteger = 8683317618811886495518194401280000000
34!
long       = 4926277576697053184
double     = 295232799039604100000000000000000000000
BigInteger = 295232799039604140847618609643520000000
35!
long       = 6399018521010896896
double     = 10333147966386144000000000000000000000000
BigInteger = 10333147966386144929666651337523200000000
36!
long       = 9003737871877668864
double     = 371993326789901300000000000000000000000000
BigInteger = 371993326789901217467999448150835200000000
37!
long       = 1096907932701818880
double     = 13763753091226346000000000000000000000000000
BigInteger = 13763753091226345046315979581580902400000000
38!
long       = 4789013295250014208
double     = 523022617466601000000000000000000000000000000
BigInteger = 523022617466601111760007224100074291200000000
39!
long       = 2304077777655037952
double     = 20397882081197447000000000000000000000000000000
BigInteger = 20397882081197443358640281739902897356800000000
40!
long       = -70609262346240000
double     = 815915283247898000000000000000000000000000000000
BigInteger = 815915283247897734345611269596115894272000000000
41!
long       = -2894979756195840000
double     = 33452526613163800000000000000000000000000000000000
BigInteger = 33452526613163807108170062053440751665152000000000
42!
long       = 7538058755741581312
double     = 1405006117752880100000000000000000000000000000000000
BigInteger = 1405006117752879898543142606244511569936384000000000
43!
long       = -7904866829883932672
double     = 60415263063373840000000000000000000000000000000000000
BigInteger = 60415263063373835637355132068513997507264512000000000
44!
long       = 2673996885588443136
double     = 2658271574788449500000000000000000000000000000000000000
BigInteger = 2658271574788448768043625811014615890319638528000000000
45!
long       = -8797348664486920192
double     = 119622220865480200000000000000000000000000000000000000000
BigInteger = 119622220865480194561963161495657715064383733760000000000
46!
long       = 1150331055211806720
double     = 5502622159812089000000000000000000000000000000000000000000
BigInteger = 5502622159812088949850305428800254892961651752960000000000
47!
long       = -1274672626173739008
double     = 258623241511168270000000000000000000000000000000000000000000
BigInteger = 258623241511168180642964355153611979969197632389120000000000
48!
long       = -5844053835210817536
double     = 12413915592536068000000000000000000000000000000000000000000000
BigInteger = 12413915592536072670862289047373375038521486354677760000000000
49!
long       = 8789267254022766592
double     = 608281864034267900000000000000000000000000000000000000000000000
BigInteger = 608281864034267560872252163321295376887552831379210240000000000
50!
long       = -3258495067890909184
double     = 30414093201713376000000000000000000000000000000000000000000000000
BigInteger = 30414093201713378043612608166064768844377641568960512000000000000