歩いたら休め

If the implementation is easy to explain, it may be a good idea.

【Python】『小飼弾のコードなエッセイ』に書いてた掛け算の実装

 本屋で見かけて面白そうだったので買ってきました。

 これの51ページ(『Mathコミュニケーション コードで考えられますか?』)で、計算量が{log_2b}の掛け算の実装をPythonで書きなおしてみました(頭がゆるふわなのでC言語のビット演算子が直感的に理解できないのです)。

元のC言語のコードはこうです。

int a_x_b(int a, int b){
    int r = 0;
    for (; b > 0; b >>= 1, a += a)
        if (b & 1) r += a;
    return r;
}

Pythonだとこう。やっぱりPython先生は擬似コードめいててわかりやすいですね。整数型以外が引数になるとどうなの?とかつっこまないでください。

def a_x_b(a, b):
    r = 0
    while b > 0:
        if (b % 2 == 1):
            r += a
        b //= 2
        a += a
    return r

単純にaをb回足し上げるより早いです。解説とかは面倒なのでこれ読んでください。

404 Blog Not Found:アルゴリズム - 同じ文字列のn回繰り返しをlog n回で作る方法

 

関係ないですが、はてなブログってlatexで数式を表示できるんですね。便利なので覚えておきます。

【はてなブログ】LaTexを使って数式を表示(tex記法) | okuzawatsのブログ@メイキニング