意外な事実：64ビット整数のうち、2つの32ビット整数の積で表せるのはわずか17%だけ

数学的な興味深い事実ですが、64ビット整数全体の中で、2つの32ビット整数の掛け算（積）として表現できる数は全体の17%に過ぎません。これはメモリ最適化やビット演算を扱うエンジニアにとって、ハッシュ関数やデータのマッピングを設計する際に考慮すべき面白い統計データと言えます。

すべての64ビット整数が32ビット整数の積になるような未来を夢見てる。みんなで協力して数学をより良いものに変えていこうぜ。

ランダムに値を選んだとき、たいていは条件を満たさないっていうのは興味深いよね！つまり、ほとんどの64ビット整数は2つの32ビット整数の積として表せないってことだ。

17%という数字を考えるのは面白いけど、「ほとんど」という言葉についてはそれほど興味をそそられないな。掛け算は順序に関係ないから、2^64通りの組み合わせは一瞬で約2^63通りまで減る。その時点で「ほとんど」という状況にかなり近いし、少しでも重複する結果があることを考慮すればすぐにそこに到達するよ。

本当に面白いのは、重複する結果を実際に定量化しようとすることだと思う。

32ビット整数1つあたり、約40億個の64ビット整数が存在する計算になるな。

ランダムな64ビット整数が32ビット整数である確率は0.0000000233%

ランダムな64ビット整数が2つの32ビット整数の積である確率は17%

なるほどね。

これはベンフォードの法則0に寄与する基本的な性質のような気がする。つまり、私たちが測定や記録をする数値のほとんどは、様々な独立した要因（加算）と従属的な要因（乗算）が積み重なった結果であり、その分布にこの性質が現れているんだろう。

これは以前ちょっと考えてたことなんだけど、乗算器内の上位レジスタと下位レジスタを汎用ストレージとして使って、コンパクトにできないか試したりして遊んでたんだ。

とにかく、8ビットの符号なし整数を掛け合わせたときに現れる面白いパターンがあるよ。

https://i.imgur.com/Gb3HDR0.png (https://i.imgur.com/Gb3HDR0.png)

（消えないようにGitHub Gistsにホストし直したほうがいいかな？）

nが大きくなるにつれて、2nビットの値のうち2つのnビットの値の積で生成できるものの割合はゼロに近づく。つまり、例えば10000000ビットの整数同士を掛け合わせる場合、生成される100000000000000ビットの整数は比較的少数になると予想される。

それって「比較的少数の20000000ビットの整数」の間違いじゃないか？

これって単に素数の概念を2^33以上の範囲の因子を含めるように拡張しただけのように見えるな。要するに、ある数が素数かどうかをチェックする際に、因子が2^32を超えた時点で判定を打ち切っているようなものだ。

もっと効率的なアルゴリズムを思いつくかもしれない。

挑戦受けて立つよ。小数点以下3桁まで答えを出したい（見出しと合わせるため）として、1000回に1回は間違えてもいい（「おそらく概ね正しい」）という条件で考えてみる。

まず、ランダムな64ビット整数を定数C個サンプリングする。各サンプルをY（32ビットの因子を持つ）、N（持たない）、U（不明）の3クラスに分けるアルゴリズムを実行する。

確率的ミラー-ラビン素数判定法で素数かどうかをチェックする（エラー確率は指数関数的にゼロへ収束する）。素数ならNを返す。素数でないなら、ポラード・ロー法をTステップ実行して32ビットの因子を持つか判定し、見つかった因子に応じてY、N、Uを返す。

重要なのは、UNKNOWNクラスを（高い確率で）非常に小さくするようにTを選択できることだ。そうすれば、推定値は急速に17%Y、83%N、約0.001%Uに収束するはずだよ。

許容誤差を固定すれば、Nに関係なくほぼ一定の繰り返し回数で計算できるはずだ。

漸近的に見て、[0,n^2]の整数のうち0%しか「n×nの掛け算表」には現れないという素晴らしい議論があるよ（確かエルデシュによるものだったはず）：

エルデシュ・カッツの定理によれば、n^2程度のサイズのほとんどの整数は約log(log(n^2)) ≒ log(log(n))個の素因数を持つ。しかし、掛け算表にあるほとんどの整数は約2*log(log(n))個の素因数を持っている。

ケビン・フォードがより精密な漸近評価を出しているね。

数学的には、これはある数がb-滑らか数（b-smooth）である確率という用語で説明されるよ。ここで『b』は2^32のことだ。