整数版powについて

C言語、あるいはC++言語において累乗を計算する場合powを使う。幾つか亜種があるが標準で用意されているのは実数版のみだ。
最も一般的なpowの定義は以下の通り

  double pow( double x, double expr );

整数版は用意されていないので、累乗が欲しいときには実数にキャストして、整数に戻す必要がある。
あまり気にすることもないかもしれないが、値によってはキャストで正しい値でなくなる場合もあるので注意が必要だ。

パフォーマンスに関する疑問もあるので、今回整数版のpowを自作し、計算時間の比較をした。
コンパイル環境はC++ Builder XE 10.2.3で、 32bit版はbcc32、64bit版はbcc64(CLang版)を使った。
計算時間はそれぞれ1億回のミリ秒だ。
また、整数はintと__int64の両方で検討した。

整数版の累乗関数は、単純なかけ算置き換え(かけ算)と、2の累乗で計算をまとめる方法(かけ算2)の2種類を試した。
かけ算は計算量がO(n)、かけ算2は計算量がO(logn)だ。

かけ算のルーチンは以下の通り

int pow( int n, int exp )
{
  int a;

  if( exp <  0 ) return 0;

  a = 1;
  for( ; exp >= 1; --exp )
  {
    a *= n;
  }

  return a;
}

かけ算2のルーチンは以下の通り。

int pow( int n, int exp )
{
  int a;

  if( exp <  0 ) return 0;

  a = 1;
  for( ; exp >= 1; exp >>= 1 )
  {
    if( exp & 1 )
      a *= n;
    n *= n;
  }

  return a;
}

累乗(x^expr)の基数xを13として計算時間を見る。 オリジナルのpowはキャストの時間を入れないために値をdoubleに変換してから時間を計測している。
64bit版のpowはなぜか異常に遅いので、試行回数を10万回に減らして100倍した値を掲載している。

大体5～6乗まではかけ算が最も早い場合が多いという結果になった。7乗以上だとかけ算2の方が早い。
かけ算2はどの場合でも概ねコンスタントに早い結果となった。
32bit版で__int64を用いる場合は、20乗以上ではオリジナルのpowが最も早いという結果になった。
64bit版(CLang版)のpowは非常に遅く、13^expではexp>4でさらに遅くなっている。ここに結果は掲載しないが累乗の基数を替えると遅くなる乗数は変わるようだ。

実際上はintは32ビット、__int64ビットは64ビット幅しかないので、2の累乗でも31乗及び63乗より大きくなればオーバーフローになるため、100乗などと言う高い乗数には意味がない。
intであれば実用上は10～20乗、__int64で40乗位がせいぜいではないだろうか。
また、今回の自作ルーチンにはオーバーフローのチェック機構がないので、汎用化ではその辺を組み込む必要がある。

このほか、0の0乗の扱いをどうするかという問題があり、解析的に1とするか(今回のルーチンはそうなっている)、それとも0にするかが問題となる。他の言語では1とする場合が多いようだ。Excelではpower(0,0)はNUM!エラーが発生する。

32bit int

32bit __int64

64bit int

64bit __int64

以下計算結果一覧表

表. 32bit int

乗数	pow	かけ算	かけ算2
0	656	219	203
1	2079	203	203
2	2141	234	328
3	2156	250	281
4	2157	328	390
5	2188	328	406
6	2219	344	437
7	2265	360	375
8	2188	375	468
9	2265	407	485
10	2250	437	563
15	2500	562	391
20	2390	750	625
25	2500	969	594
30	2625	1172	562
35	2687	1391	672
40	2516	1703	656
45	2765	2063	672
50	2625	2375	735
75	2891	3843	813
100	2765	5250	828

表. 32bit __int64

乗数	pow	かけ算	かけ算2
0	609	266	250
1	2094	500	719
2	2125	765	1094
3	2156	1078	1313
4	2172	1359	1453
5	2188	1656	1656
6	2218	1985	1703
7	2234	2266	1875
8	2203	2563	1781
9	2250	2891	2016
10	2250	3218	2016
15	2516	4937	2500
20	2391	6531	2391
25	2516	8218	2609
30	2625	9938	2828
35	2656	12047	2969
40	2500	13890	2735
45	2781	15578	3172
50	2625	17359	2969
75	2922	26297	3484
100	2781	35688	3344

表. 64bit int

乗数	pow	かけ算	かけ算2
0	1600	94	47
1	7800	125	109
2	7800	172	125
3	7800	203	141
4	7800	281	250
5	248500	297	187
6	239100	297	171
7	245300	329	172
8	231200	359	391
9	243700	391	297
10	246800	438	282
15	253100	656	203
20	246800	860	344
25	243700	1063	328
30	251500	1235	281
35	248500	2422	453
40	250000	2656	516
45	253100	2125	422
50	243700	2297	469
75	248400	4891	422
100	243800	6265	500

表. 64bit __int64

乗数	pow	かけ算	かけ算2
0		93	63
1	7800	125	109
2	7800	157	140
3	7800	188	141
4	7800	281	266
5	248400	297	203
6	239100	281	172
7	246900	312	172
8	231300	359	390
9	243800	391	296
10	248400	454	281
15	253100	672	203
20	246900	875	344
25	243800	1062	344
30	250000	1234	266
35	248400	2422	453
40	248500	2656	500
45	251600	2031	437
50	243700	2297	469
75	245300	4938	437
100	242200	6219	500