高速累乗計算(python3)

# はじめに
今回は java の話ではなく..
たまたま面白いロジックに出会い、整理しておきたいと思いました.

純粋な python は、java と比べると処理が遅いですが、
見やすいため、簡単な書き方ゆえにロジックに時間を割愛できるため、アルゴリズムを書くときは python を使ったりします.

愛着を感じるのは、JVM 言語です -- 要らない情報でした.

# ゴール
一つ一つ考えること 🙂

# ことば
### オーダー表記
n 個のデータに対する計算量です. 
O(n) は、データが2倍、3倍 ... すると、計算量は2倍、3倍 ...

大量のデータを扱うため係数と定数は無視します.
O(3n - 4) == O(n)

O(log n) は O(log_n) です. _ は対数の底 2 のつもりで書きました.
データが2倍になると、計算量は log 2 （== 1) 増えます.
=> <a href="http://www.metareal.org/2008/09/07/logarithm-and-big-o-notation/">[外部リンク] 対数の底が省略できる理由</a>


### 再帰 
```exit case``` は ```base case``` と呼ばれたり. 
再帰を終える場合. 再帰の底です.

```standard case``` は ```recursive case``` と呼ばれたり.
再帰し続ける場合. 標準的な行動です.

"再帰が終わる"という意味が伝わるので私は exit case という表現を選んだりします.

# 累乗そのもの

```math
x^n = x \times x ...\times x \\
xをn回掛ける
```

とりあえず、正の整数を前提と考えていきます.

x が基数
n が指数

となります.

python の built-in だと

```.py
pow(x, n)  # print(pow(2, 3)) 8
x ** n     # print(2 ** 3)    8
```

になりますが、

目に見える形式で実装します.

```.py
def pow(x, n):
    """
    O(n)
    """
    result = 1
    for _ in range(n):
        result *= x
    return result

```

x の数分、計算量が増えるので、計算量は <b>O(n)</b> です.


### 同じことを再帰で表現

```.py
def pow_r(x, n):
    """
    O(n)
    """
    if n == 0:
        return 1 # exit case
    else:
        return x * pow_r(x, n - 1) # standard case
```

再帰ケースで指数 n を一つずつ減らして行き、n が 0に至ると、

```math 
2^0 = 1
```

なので、再帰から抜け出します.


# 掛け算の量を減らす

基本的な考え方はこうです.
x が n 個あったら、n 回計算する.
つまり n を減らすためには、指数を小さくしていくことが考えられます.

## まず指数を半分に減らす(再帰)

① n が偶数の場合

```math
x^n = (x^2)^\frac{n}{2} 
```

② n が奇数の場合

```math
x^n = x \times ((x^2)^\frac{n-1}{2})
```

### 例

n が偶数の場合、n を半分にします. 

```math
2^{20} = 4^{10}
```

```math
4^{10} = 16^{5}
```


n が奇数のときは、1を引いて n を半分にします.
1を引いたので、引いた分を分離して係数にします.

```math
16^{5} = 16 \times 256^{2}
```

改めて書き直すとこうなりました.

```math
 2^{20} = 16 \times 256 \times 256 \times 1
```

2を20回掛けていた20段階の乗算が、4段階に減りました.


```.py
def pow_r(x, n):
    """
    O(log n)
    """
    if n == 0:  # exit case
        return 1
    if n % 2 == 0:  # standard case ① n is even
        return pow_r(x ** 2, n // 2)
    else:  # standard case ② n is odd
        return x * pow_r(x ** 2, (n - 1) // 2)
```

```//``` は切り捨て除算の演算子なので、<b>standard case ②</b> は
>
```.py
return x * pow_r(x ** 2, n // 2)
```

と本来は n - 1 が n と省略できます.

>奇数 n を 2で割って切り捨てる == 奇数 n から 1を引いて2で割る

であるためです.

各段階ごとに掛け算の数を半分減らしていくため、計算量は <b>O(log n)</b>です.


## 使用するスタックメモリの領域も減らす(反復)
しかし、この形の再帰は、呼び出しのたびに(深くなるたびに)使うスペースの数も増えていきます.

ということで、関数内でのみ使う 変数 K を新たに設けます. 
変数なので本来なら小文字が好ましいですが、見やすくしたいので...

指数 n が奇数のケースで、指数から 1 を減らして指数を半分にする際に、
基数 x が分離されました. ぽん.

```math
x^n = x \times ((x^2)^\frac{n-1}{2})　\\
```

その x を別途記録して係数として K に溜めていきたいと思います.

### make it work first

```.py
def pow_k(x, n):
    """
    O(log n)
    """
    if n == 0:
        return 1
    K = 1
    while n > 1:
        if n % 2 != 0:
            K = K * x
            x = x ** 2
            n = (n - 1) // 2
        else:
            x = x ** 2
            n = n // 2

    return K * x # 指数を割り続け n が 1 に至ったら終了
```

2の20乗の計算で、K と x が return される時点での値は、K = 16, x = 65536 となります. 

n が奇数になるケースはこの n==5 の段階の

```math
16^{5} = 16 \times 256^{2}
```

16 のみでしたね.

### きれいきれい

```.py
def pow_k(x, n):
    """
    O(log n)
    """
    if n == 0:
        return 1

    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        n //= 2

    return K * x
```

こっちの方が
>
1. 指数が奇数の場合分離した係数を別途溜める
2. 各段階で掛け算の量を半分に減らす

が見やすくなったかもしれません.

# おわりまして
よりよい方法、よりよい説明、ご指摘や補足など、随時教えてくださいませ.