本屋で見かけて面白そうだったので買ってきました。
小飼弾のコードなエッセイ ~我々は本当に世界を理解してコードしているのだろうか? (Software Design plus)
- 作者: 小飼弾
- 出版社/メーカー: 技術評論社
- 発売日: 2013/04/16
- メディア: 単行本(ソフトカバー)
- この商品を含むブログ (5件) を見る
これの51ページ(『Mathコミュニケーション コードで考えられますか?』)で、計算量がの掛け算の実装を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回で作る方法