ハッカーのたのしみ―本物のプログラマはいかにして問題を解くかをやっと読み終えた。素晴らしい本だった。
たとえば符号なしの整数xが2のべき乗であるかどうかを判定するにはどうすればいいか? これは x & (x - 1) という式の結果が0かどうかで判定できる。この式はxの1であるビットのうちで一番右のものを0にするという作用をもつため、2のべき乗のときには結果としてすべてのビットが0になり、そうでないときはいずれかのビットが1のまま残るからである。
また、符号なし32ビット整数nを3で割った商qは、次のようにすれば除算を使わずに乗算とシフト演算だけで計算できる。
q = 0xAAAAAAAB * n / 2^330xAAAAAAAB = (2^33 + 1) / 3という数値なので、結果として q = n/3 + n/(3*2^33) を計算しており、さらに2項目が任意の32ビット整数nに対して1/3より小さいことが保証されているからである。
この本にはこの手の一人では思いつくことができないような最適化手法が山のように載っており、コンパイラ作成者やアセンブラでゴリゴリ書く人は必読だろうし、そうでなくても十分楽しめると思う。
で、この本の中に、自然界に現れる数値の先頭桁の分布が偏りについての記述がある。先頭桁が1である確率は1/9でなく約30%にも達し、2では17%に減少、9になるとたったの4.5%しかないという話が載っている。
ググってみると世間ではベンフォードの法則と呼ばれているようだ。この本にはベンフォードの法則の数学的な分析も載っていて、その最初の部分だけ抜粋すると
今、10進数で先頭桁の分布を考えてみよう。そして、「科学的」記法(たとえば6.022*10^23)で表される、長さ、体積、質量、速度などの、単位を持つ数の大きな集合があると仮定する。もし、このような数の集合に属する大きな数の先頭桁が破綻なく定義された分布関数を持っていれば、それはインチやセンチメートル、あるいはポンドやキログラムなどの単位とは独立していなければならない。したがって、その集合の中のすべての数値にどのような定数を掛けても、先頭桁の分布は変化しないはずである。たとえば、2を掛けることを考えると、先頭の桁が1である数値(1.0から1.999...に10の冪を掛けたもの)の個数は、先頭桁が2または3である数値(2.0から3.999...に10の冪を掛けたもの)の個数と等しくならなければならないといえる。なぜなら、長さの単位がインチであるかハーフインチであるか、質量の単位がキログラムであるかハーフキログラムであるかなどは問題になるはずがないからである。このような考えから分布関数を計算すると、結局のところ先頭桁がDである確率は log(D+1) - logD と計算でき、したがって先頭桁が1の確率は log(2/1) = 0.3010 となる。
実際に下記のURLの末尾のほうに、各種の数値の集合に対してベンフォードの法則に従うか検証した表がある。たしかに綺麗にしたがっていて驚いてしまう。
http://mathworld.wolfram.com/BenfordsLaw.html
こんなに重要な法則を今まで知らなかったのがショックだ。これコーディングのときにも知っておくとおおいに役に立ちそうだなあ。
