べき乗のアルゴリズム

#はじめに

まずはこれを見て欲しい

```ruby: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乗`を考えてみる。

```math
5^{16}
```

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

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

になり、さらに、

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

もうひと押し

```math
((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: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乗`を考えてみる。

```math
3^{18}
```

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

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

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

ここで、

```math
2^4 = 2 \times 2^3
```

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

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

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

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

もういっちょ。

```math
(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: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: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を返しちゃうことになります)や、大きすぎる値の計算を求められた時にどうするかを決めてあげれば出来上がりということになります。

# さいごに

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