ソフトウェアプログラミングでは、整数の積はしばしば固定ビット数でオーバーフローを伴って計算される。8ビット整数の場合を考えてみよう。127と127を掛けた場合、8ビット符号なし整数としては1が返され、オーバーフローが発生する。実際の完全な積は16129である。16129を表すには、通常16ビットの精度が必要になる。

したがって、完全積という概念が得られる。2つの32ビット整数の完全積は通常64ビットで表される。私が気になったのは、64ビット整数全体のうち、何割が2つの32ビット整数の積として書けるのかという点である。

なぜ気にするのかと疑問に思うかもしれない。

私たちはしばしばハッシュ関数を設計する。ハッシュ関数は入力を受けてランダムに見える出力を生成する特殊な関数である。数年前、私は文字列（数百バイト以上）を対象とした非常に高速なハッシュ関数 clhash を設計した。clhashについて知らなければ、ぜひ確認してほしい。それ自体が非常に興味深いものだ。

このclhashハッシュ関数は、暗号応用で典型的に用いられる種類の乗算を使用している。私は、標準的な乗算に基づく手法と比べて、私たちのアプローチに利点があると主張しようとしていた。例を挙げて説明しよう。32ビット整数のための単純なハッシュ関数は、最下位ビットと最上位ビットを掛け合わせる方法が考えられる。

// simpleHighLowHash is a simple (and weak) 32-bit hash
// that multiplies the high 16 bits by the low 16 bits.
func simpleHighLowHash(x uint32) uint32 {
    high := uint16(x >> 16)
    low := uint16(x & 0xFFFF)
    return uint32(high) * uint32(low)
}

ハッシュ関数が一様であることを望むかもしれない。つまり、あり得るすべての32ビットハッシュ値が等しい確率で出現するようにしたい。この例では、ハッシュ関数がすべての32ビットハッシュ値を生成できる場合にのみ可能だが、現実にはそうではない。

偉大な数学者エルデシュは、2つのnビット値の積で生成できるすべての2nビット値の割合が、nが大きくなるにつれてゼロに近づくことを示した。つまり、10000000ビット整数同士を掛け合わせた場合、20000000ビット整数のうち生成されるものは比較的少ないと予想される。しかし、32ビット整数や64ビット整数のような実用的なケースではどうだろうか？

16ビット整数同士の積を32ビット積にするまでは、問題を簡単に力任せに解くことができる。その時点で、32ビット数のおよそ5分の1が2つの16ビット整数の積である。32ビット整数全体の約80%は、このハッシュによって生成されない。しかし、実行時間は指数関数的に増加し、力任せの方法は32ビットまでスケールしない。

では32ビットのケースについてはどうすればよいか？つまり、2つの32ビット整数を掛けて64ビット積を生成する場合、以下の関数が生成できる64ビット値の割合はどれくらいだろうか？

func simpleHighLowHash(x uint64) uint64 {
    high := uint32(x >> 32)
    low := uint32(x & 0xFFFFFFFF)
    return uint64(high) * uint64(low)
}

正確な結果を得ることはできるだろうか？

できる！！！

Websterと彼の同僚たちは、正確な計算をスケールアップできる数学を構築した。彼は親切にもコードを公開してくれた。

2つの32ビット整数の積として書くことができる64ビット（符号なし）整数は 3,215,709,724,700,470,902 個ある。これは可能な値全体の約17%に相当する。

積が与えられたときに、実際にそのペアの整数を計算するにはどうすればよいだろうか？一つの方法は、完全素因数分解を計算し、それらの因子を使って 2^32 未満のすべての可能な除数を構築することである。まず候補集合に 1 のみを含め、既存の候補に各素因数を繰り返し掛ける（2^32 未満に収まる積のみを保持する）。重複を避けるために、各素因数をその多重度とともに一意に処理する。最後に、候補の中から最大のもの m を 2^32 未満の最大の除数として選び、対応する残り n / m を計算し、有効な32ビット因数への分割が存在するかどうかを報告する。一般に、答え（存在する場合）は一意ではない。この方法は、一方の値を最大化するペアを返す。Pythonでのコードは次のようになる。

for p in factor_multiplicities:
    new_candidates = []
    for c in candidates:
        for i in range(factor_multiplicities[p] + 1):
            if c * (p ** i) < 2**32:
                new_candidates.append(c * (p ** i))
    for new_c in new_candidates:
        candidates.append(new_c)
m = max(candidates)
print(f"Maximum candidate: {m}")
leftover = n // m
print(f"Leftover: {leftover}")
if leftover >= 2**32:
    print("Leftover is too large, cannot find a suitable candidate.")

より効率的なアルゴリズムを考え出せるかもしれない。ランダムに値を選ぶと、たいてい失敗するという事実は興味深い。つまり、ほとんどの64ビット整数は2つの32ビット整数の積として書くことができない。