アルゴリズムクイックリファレンス 第2版

2.6

 参考文献

■

35

る。この振る舞いは、

Python

が

**

演算子を用いてべき乗を計算するのに

平方によ

る指数化

（

Exponentiation By Squaring

）アルゴリズム

＊

1

を使用していることを示

す。

2

x

を

for

ループを使って普通に計算すると二乗性能になる。

仮説

H2

を論破するために、

2

n

の値を前もって計算し、π

*2

n

を計算する時間を

評価する実験を行った。

1

万回試行した全実行時間を図2-7に示す。

図2-7の点列は、どうして直線にならないのか。

x

のどの値で線が途切れるのか。

乗算（

*

）は、オーバーロードされているようだ。掛けられる数が浮動小数点数か整

数かで、また機械語の

1

ワード（語）に収まるか、大きすぎて複数ワードにまたがっ

て格納されるか、あるいは、これらの組み合わせによって、乗算は異なる作業を行う。

pi*2**x

を計算する全実行時間

図2-7　大きな乗算を計算する実行時間

グラフの最初の変化点は、

x

＝

{64, 65}

のときで、大きな浮動小数点数の格納に

よる変更のようだ。計算に予期しない速度低下があり、このようにベンチマークを

取ることによって初めて明らかになる。

2.6

 参考文献

Bentley, J., Programming Pearls. Second Edition. Addison-Wesley Professional,

1999.

（邦題『珠玉のプログラミング

−

本質を見抜いたアルゴリズムとデータ構造』丸

善出版、

2014

）

＊1 訳注：リポジトリの

exponentiationBySquaring.py ...