繰り返し2乗法

はじめに

Atcoderの解説を見ていて繰り返し2乗法と言う言葉を聞いて知らなかったので調べてみた

簡単に言うと

• 2¹⁰などの計算を楽にする
• O(log n)で計算できる

  理論

  2¹⁰といった数を計算すると

[tex:
\begin{align}
 2^{10} &= 2 \times 2 \times 2 \times 2 \times 2 \times 2 \times 2 \times 2 \times 2 \times 2\\
&= 4 \times 4 \times 4 \times 4 \times 4 \\
&= 16 \times 16 \times 4 \\
&= 16 \times 64 
\end{align}
]

3⁵⁰の時以下の様に掛ける数を2の累乗にして計算回数を減らすことができる。

[tex:
\begin{align}
50 &= 2^5 + 2^4 + 2^1 \\
3^{50} &= 3^{2^{2^{2^{2^{2}}}}} \times 3^{2^{2^{2^{2}}}} \times 3^2
\end{align}
]

以上の様に表すことが可能であるためO(log n)で計算することが可能.

プログラム

def pow(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

pythonではpow()が繰り返し2乗法で動作しているため自分で組む必要はないらしい