べき乗のアルゴリズム

はじめに

まずはこれを見て欲しい

ruby

def pow(base, exponent)
  result = 1
  while exponent > 0
    result = result*base if exponent%2 == 1
    exponent = exponent >> 1
    base = base*base
  end
  return result
end

powはpowerの略で、べき乗計算の関数。色々な言語でおなじみだと思う。あまり中身を気にして使ったことなかったが、こんな感じになっているらしい。

分かってしまえば何ということはないが、ぱっと見で私はコレが何をしているのか分からなかった。

実際のところ、これは何をしているのか

pow(5,16)で考えてみる

pow(5,16)つまり5の16乗を考えてみる。

5^{16}

ここがスタート。ここからこれをどんどん分解していく。まず、

5^{16} = (5^2)^8

になり、さらに、

(5^2)^8 = ((5^2)^2)^4

もうひと押し

((5^2)^2)^4 = (((5^2)^2)^2)^2 \\
5^{16} = (((5^2)^2)^2)^2

ということで、5の16乗が5を2乗したものを2乗したものを2乗したものの2乗に変わりました。こうすることで、単純に掛け算をしていくと15回掛け算する必要があるものが、4回二乗の計算をすれば済むものに変わります。

これを5の16乗以外にも通用する**(?)**ルールとして書いてみると、こうなります。

1. 指数が1になっていれば終了
2. 指数を2で割り、「現在の底の2乗」を新たな底とする
3. 1に戻る

これをrubyで書くと

ruby

def pow(base,exponent)
  raise ArgumentError if exponent < 0
  # 指数が0の時は結果は1です
  return 1 if exponent==0
  # 指数が1なら終了
  while exponent != 1 do
    # 指数を2で割る
    exponent /= 2
    # 底の2乗を新たな底とする
    base *= base
    # 繰り返す
  end
  # 結果を返す
  return base
end

になります。**しかし、この関数には致命的な欠陥があります。**次に行ってみましょう。

pow(3,18)で考えてみる

次はpow(3,18)つまり3の18乗を考えてみる。

3^{18}

では、同じように分解していこう。

3^{18} = (3^2)^9

ここで今までと違うパターンに出会う。9は2では割れない。どうしようか。

ここで、

2^4 = 2 \times 2^3

であることを思い出して欲しい。これを使って一旦横に置いておくことをしよう。

(3^2)^9 = 3^2 \times (3^2)^8

これで3の2乗は一旦置いておいて、3の2の8乗について分解を進める。

(3^2)^9 = 3^2 \times ((3^2)^2)^4

もういっちょ。

(3^2)^9 = 3^2 \times (((3^2)^2)^2)^2

これで分解できた。

ということで、前回作ったルールに欠陥があったことがわかった。前回作ったルールに加えて、指数が奇数の時に、その時の底を一旦横に置いて置くルールを加えなくてはいけないということだ。

なので...

1. 指数が1になっていれば終了
2. 指数を2で割り、「現在の底の2乗」を新たな底とする
3. 1に戻る

これが、

1. 指数が1になっていれば終了
2. 指数が奇数であれば、その時の底を一旦横に置いておき、指数を一つ減らす
3. 指数を2で割り、「現在の底の2乗」を新たな底とする
4. 1に戻る

にならなくてはいけない。

ruby

def pow(base,exponent)
  raise ArgumentError if exponent < 0
  # 指数が0の時は結果は1です
  return 1 if exponent==0
  # 一旦底を置いておく場所を作る
  bases = []
  # 指数が1なら終了
  while exponent != 1 do
    # 指数が奇数の時、その時の底を一旦横に置いておき、指数を一つ減らす
    if exponent.odd? then
      bases.push( base )
      exponent -= 1
    end
    # 指数を2で割る
    exponent /= 2
    # 底の2乗を新たな底とする
    base *= base
    # 繰り返す
  end
  # 最後に、一旦置いておいたものと現時点での底を全て掛け合わせる
  array.each{ |past_base| base*= past_base }
  # 結果を返す
  return base
end

これでオッケー。上記では一旦置いておくイメージの為に箱を作ってその中に放り込み、最後にかけ合わせましたが、実際にはこんなことをする必要がなく、一番最初のコードにあるようにresultという結果が出る変数を最初に作って、どんどんそこに掛けて行けばよいのです。

ruby

def pow(base,exponent)
  raise ArgumentError if exponent < 0
  # 指数が0の時は結果は1です
  return 1 if exponent==0
  # 結果が出る変数を用意
  result = 1
  # 指数が1なら終了
  while exponent != 1 do
    # 指数が奇数の時、その時の底はここでresultに掛けてしまい、指数を一つ減らす
    if exponent.odd? then
      result *= base
      exponent -= 1
    end
    # 指数を2で割る
    exponent /= 2
    # 底の2乗を新たな底とする
    base *= base
    # 繰り返す
  end
  result *= base
  # 結果を返す
  return result
end

ここから、最初のreturn 1 if exponent==0はresult = 1を見て、なんだか消せそうだぞとなり、2で割る、偶数奇数は2進数(ビット)を上手いこと使えばきれいに掛けそうだぞ、などとなっていった結果、最初のコードのようになります。

基本的なルールは変わらないです。あとは指数をマイスのときにどうするか(0を返すか、例外を投げるか、一番上だと1を返しちゃうことになります)や、大きすぎる値の計算を求められた時にどうするかを決めてあげれば出来上がりということになります。

さいごに

基本的なルールだけ、細かいところはだいぶ雑になりましたが、こういうちょっといした仕組みは面白いですね。