8

重複の可能性:
整数ベースの累乗関数 pow(int, int) を実装する最も効率的な方法

実行時間を短縮して電力を計算するにはどうすればよいですか?

例: 2^13。

次の計算と関係があることをどこかで見たのを覚えています。

2^13 = 2^8 * 2^4 * 2^1

しかし、方程式の右辺の各要素を計算してから乗算することがどのように役立つかわかりません。

何か案は？

編集：私はどんなベースでも意味しました。以下で言及したアルゴリズム、特に「二乗による指数」は、ランタイム/複雑さをどのように改善しますか?

4

6 に答える 6

16

これには一般化されたアルゴリズムがありますが、ビットシフトのある言語では、2 の累乗を計算するはるかに高速な方法があります。入力するだけです(ビットシフト演算子が、操作をサポートするほとんどの言語と同じであると1 << exp仮定します)。 <<.

一般化されたアルゴリズムを探していて、例として不幸なベースを選択しただけだと思います。このアルゴリズムを Python で与えます。

def intpow(base, exp):
   if exp == 0:
      return 1
   elif exp == 1:
      return base
   elif (exp & 1) != 0:
       return base * intpow(base * base, exp // 2)
   else:
       return intpow(base * base, exp // 2)

これにより、基本的に指数を log2 exp 時間で計算できるようになります。分割統治アルゴリズムです。:-) 他の誰かが言ったように、二乗による累乗。

例をこれに差し込むと、それがどのように機能し、与えられた方程式に関連しているかがわかります。

intpow(2, 13)
2 * intpow(4, 6)
2 * intpow(16, 3)
2 * 16 * intpow(256, 1)
2 * 16 * 256 == 2^1 * 2^4 * 2^8
于 2010-02-04T08:08:51.387 に答える
3

2 のべき乗は簡単です。バイナリでは、2^13 は 1 の後に 13 個のゼロが続きます。

多くの言語の組み込み演算子であるビットシフトを使用します。

于 2010-02-04T08:09:36.007 に答える