【C言語】べき乗を割り算で効率よく

 大学でコンピュータのアルゴリズムの基礎として「べき乗」の計算がよく出ます。まあ、実用的にはライブラリのpow関数でも使えば良いのですが、基礎的な関数を自分で実装できる機会も学生のときは必要だと考えます。

確かに仕事を始めると「車輪の再発明」みたいな言葉で何でも自作することは悪みたいな風潮はあります。ただ、初学者が自分で作ってみる機会は重要です。建築家が研究のために小さな小屋や木工製品を作るように、プログラマも既存の関数を自分で作ってみて下さい。

まず思いつく方法

1. unsigned int power1(const int x,const int n){
3.     unsigned int val = 1;
4.     
5.     for(int i=1;i<=n;i++){
6.             val *= x;
7.     }
8.         
9.     return val;
10. }

上記の関数を思いつくのでは無いでしょうか？　単純に指数だけループして基底部を掛け算しています。２の３０乗を計算するときも 2*2*.....*2 と３０回繰り返しています。

分かりやすいアルゴリズムですが、もっと最適な方法があるだろうと言う疑問を持つと考えます。

指数部を２進数にしてみる

先程の３０と言う数字を２進数にすると

(30)10=(11110)2

となります。具体的には２で割った余りが２進数の桁になります。一番最初が一番地位いさい桁です。

30÷2 = 15…0
15÷2 = 7…1
 7÷2 = 3…1
 3÷2 = 1…1
 1÷2 = 0…1

数字を２で割った余りが２進数の桁数になっていることが確認出来ます。次に２を繰り返し二乗します。先程の３０を２進数にした桁数である５回やってみます。

2,4,16,256,65536

となります。この数字を先程の２進数の桁が少ない方からかけ合わせて見ます。

0*2,1*4,1*16,1*256,1*65536

と計算できます。後はこの数字を全て掛け算すれば２の３０乗が計算できます。答えは

1073741824

です。

実際のコード

1. unsigned int power2(const int a,const int n){
2.     unsigned int val = 1;
3.     int base = a;
4.     int exp = n;
5.     
6.     while(exp > 0){
7.         if(exp%2){
8.             val *= base;
9.         }
10.     base *= base;
11.     exp /= 2;
12.     }
13.     return val;
14. }

これが指数を２進数にしたコードです。３行目では base に基底部、４行目ではexpに指数を入れています

6行目で expがゼロより上の条件でループします。　7行目の if 文では exp%2 は　２で割った余りがあれば２進数の桁が１ということで、現在の基底部base の内容が掛け算されます。

その後、基底部は二乗されます。単に自分自身を自分自身で乗算しています。　expは２で割り算しています。整数型なので小数点は切り捨てられます。

忘れがちなことですが、わり算の答えで余りを出す方法を思い出して下さい。小学生の算数や高校数学の整数で出てきているはずです。

他には

base *= base;
exp /=2;

と言った記述がありますが、以下と同じ意味です。表記が簡潔になるのと、間違えが発生しにくいと言う利点がありますので使って下さい。

base = base * base;
exp = exp / 2;

これと全く同じことが行われます。

途中結果を出すコード

1. unsigned int powerInst(const int a,const int n){
2.     unsigned int val = 1;
3.     int base = a;
4.     int exp = n;
5.     
6.     printf("Idx / 2 Div ...M Base * M\n");
7.     while(exp > 0){
8.         printf("%3d / 2 = %3d...%1d %10d * %1d\n",exp,exp/2,exp%2,base,exp%2);
9.         if(exp%2){
10.             val *= base;
11.         }
12.     base *= base;
13.     exp /= 2;
14.     }
15.     printf(" %10d\n",val);
16.     return val;
17. }

上記コードは途中結果を出力します。これで動作を確認してみて下さい。実行結果は以下です。

• Idx / 2 Div ...M Base * M
•  30 / 2 = 15...0 2 * 0
•  15 / 2 = 7...1 4 * 1
•   7 / 2 = 3...1 16 * 1
•   3 / 2 = 1...1 256 * 1
•   1 / 2 = 0...1 65536 * 1
•                   1073741824

一列目が指数、二列目が２、三列目が割り算、四列目が余り、五列目が基底部、六列目が余りです。

べき乗計算は既にライブラリとしてありますので、正直この実験は「車輪の再発明」に近いです。　ただ、最初に言ったように初学者ほどこのような基礎的なアルゴリズムを空で打てるようにしておいて下さい。

あと、べき乗計算でこの方法を応用すると劇的に処理を高速化出来ます。今回も正攻法だと指数部３０だと３０回のループが必要ですが、今回の方法だと５回のループで計算できています。この知識は高度なプログラミングにも応用が利くので覚えておいても損は無いと考えます。

Amazonでアルゴリズム

の本を確認する

動画を見る