python 競技プログラミング

pythonでべき乗計算 pow()関数と**演算子の違いを解説

pythonでべき乗計算をする方法はいくつかありますが、記述方法によって実行速度がおどろくほど違うケースがあります。

pythonでべき乗計算する時に、どの記述が高速に計算できるのか理由もあわせて解説します。

たびすけ
実行速度が全然違うこともあります!

べき乗と累乗の違い

べき乗とは、\(10^n\)のように記述して\(10\)のn乗と読みます。

累乗という言葉も聞いたことがあるかもしれませんが、違いは次の通りです。

累乗とべき乗の違い

  • 累乗は\(10^n\)の\(n\)の部分が自然数(正の整数)に限定
  • べき乗は(\(10^n\)の\(n\)の部分が実数(\(+\)複素数)まで拡張

pythonでべき乗計算の記述方法は2つ

pythonでべき乗計算をするときの記述方法は、pow()関数と**演算子の\(2\)つがあります。

説明で使う変数は\(a^n\)とします。

pow()関数

pow()関数でべき乗計算を行う時は次のように記述します。

pow(a, n)

変数の変わりに数値を入れて計算したものを出力してみましょう。

print(pow(2, 5))

出力結果は次のようになります。

32

**演算子

pow()関数でべき乗計算を行う時は次のように記述します。

a ** n

変数の変わりに数値を入れて計算したものを出力してみましょう。

print(2 ** 5)

出力結果は次のようになります。

32

割った余りを求めるときはpow()関数が高速

pow()関数も**演算子もべき乗計算だけ比較すると実行速度に差はありません。

しかし、べき乗した数値(\(a^n\))を\(m\)で割った余りを求める(剰余計算)時は実行速度に差が出ることがあります。

\(a^n\)を\(m\)で割った余りを求めてみます。

pow()関数

pow(a, n, m)

変数の変わりに数値を入れて計算したものを出力してみましょう。

print(pow(2, 1000000000, 1000))

出力結果は次のようになります。

376

この時の実行時間です。

実行時間	29 ms

**演算子

a ** n % m

変数の変わりに数値を入れて計算したものを出力してみましょう。

print(2 ** 1000000000 % 1000)

計算結果は当然同じです。

376

この時の実行時間です。

実行時間	5243 ms

実行時間の違い

**演算子はpow()関数と比較すると計算時間が200倍です。

計算時間に差がある理由は簡単です。

計算時間に差が出る理由

  • a ** n % m
    • \(a^n\)を計算した後に、mで割った余りを求めている
  • pow(a, n, m)
    • べき乗計算の都度、mで割った余りを求めている

厳密には違いますが、計算のイメージは次のような感じです。

pow()関数

2
4
8
16
32
64
28
56
12
24

**演算子

2
4
8
16
32
64
128
256
512
1024
24

数値が小さいので違いが分かりにくいですが、計算結果が大きくなるほどa ** n % mは桁数が増えていきます。

その結果、計算時間が多くかかってしまいます。

たびすけ
べき乗を割った余りを求めるときはpow(a, n, m)を使うと高速に計算できます!

-python, 競技プログラミング