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

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

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

まず思いつく方法

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

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

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


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

先程の30と言う数字を2進数にすると

(30)10=(11110)2

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

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

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

2,4,16,256,65536

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

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

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

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. }

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

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

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

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

他には

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

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

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

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




クラウドを使わずにバックアップが安心 ROBOCOPY と バックアップの習慣化

 皆さん、ファイルのバックアップは作成していますか? 私が聞いた限りでは「誰もやっていない」というのが正直なところです。ただ、そこまでパソコンというデバイスを信用しているのは怖いところです。 「良い道具は一生物」という言葉があります。実際、工具類は良いものを手に入れれば一生涯使え...