Python
アルゴリズム
数学
累乗

はじめに

今回は 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) 増えます.
=> [外部リンク] 対数の底が省略できる理由

再帰

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

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

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

累乗そのもの

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

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

x が基数
n が指数

となります.

python の built-in だと

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

になりますが、

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

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

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

同じことを再帰で表現

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に至ると、

2^0 = 1

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

掛け算の量を減らす

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

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

① n が偶数の場合

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

② n が奇数の場合

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

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

2^{20} = 4^{10}
4^{10} = 16^{5}

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

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

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

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

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

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)

// は切り捨て除算の演算子なので、standard case ②

return x * pow_r(x ** 2, n // 2)

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

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

であるためです.

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

使用するスタックメモリの領域も減らす(反復)

しかし、この形の再帰は、呼び出しのたびに(深くなるたびに)使うスペースの数も増えていきます.

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

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

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

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

make it work first

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 の段階の

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

16 のみでしたね.

きれいきれい

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. 各段階で掛け算の量を半分に減らす

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

おわりまして

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