Power Function Python

Question

この関数はa^bの値を計算し、それを返します。m = log（b） の場合は、m + 1の対話を行うのが最善のシナリオです しかし、 ？そしてそれはwhileループに何回入力されますか？

def power(a,b): 
    result=1 
    while b>0: # b is nonzero 
     if b % 2 == 1: 
      result=result*a 
     a=a*a 
     b = b//2 
    return result 

Answer 1

@EliSadoffコメントで述べたように、あなたはあなたの関数でresultの初期値を必要としています。ただdef行の後の行

result = 1 

を挿入します。その後、コードは動作し、これは暗黙的にbというバイナリ表現を使用して累乗を素早く取得するための標準的な方法です。 （ループ不変はresult * a ** bの値は、このアルゴリズムの有効性を示しており、一定のままであることである。）

あなたif b % 2ラインがwhileループを通るたびに実行された場合、最悪のケースです。これは、bが2の累乗よりも1少ない場合に発生します。したがって、bの各桁はバイナリ表現が1です。 whileループ条件while b>0はまだチェックされているに過ぎません。m+1回ですが、各ループにもう少し処理が必要です。

コードをスピードアップする方法はいくつかあります。 if b % 2 = 1ではなくwhile b>0およびif b & 1ではなく、while bを使用してください。 b = b // 2ではなくa = a*aおよびb >>= 1ではなく、result = result*aおよびa *= aではなく、result *= aを使用してください。これらはもちろん、ほんのわずかな改善です。ループをさらに高速化する唯一の方法は、構造化されていないコードを使用することです。これはPythonでは不可能と思います。 （aには1つ以上の修正が必要ですが、ループにジャンプすることなくそのようなことを防ぐ良い方法はありません）。aとbを変更しないようにする内部ループなど、このコードにはいくつかのバリエーションがあります。 bは偶数ですが、必ずしも高速であるとは限りません。

最終的なコードは、私は少し良くフィットPEP8（Pythonのスタイルの基準）にあなたのコードをクリーンアップし、その後

def power(a, b): 
    """Return a ** b, assuming b is a nonnegative integer""" 
    result = 1 
    while b: 
     if b & 1: 
      result *= a 
     a *= a 
     b >>= 1 
    return result 

です。特にbが非負整数であることを確認するために、コードのエラーチェックはありません。 bが負の整数である場合にコードが無限ループになると信じていますが、結果は偽の結果を返します。だから、エラーチェックをしてください！また、あなたのコードには、このような関数のためのかなり標準的なpower(0, 0) == 1が記載されていますが、まだ驚いていくつかの人々がかかることに注意してください。