Nビットのビット列について、各ビットを確率 \(p\) でランダムに1にするにはどうすればよいだろうか。単純にそれぞれのビットごとに1にするか0にするかを決めると、 \(N\) 回の乱数生成が必要になる。しかし、アルゴリズムを工夫することで乱数生成回数を減らすことができる。我々はこのようなランダムなビット列を生成するアルゴリズムをいくつか考案し、それを組み合わせることで劇的に計算量を減らすことに成功した[1]。我々が提案したのはBinomial-Shuffle法、Poisson-OR法、有限桁法の三種類と、そのハイブリッド法である。
Binomial-Shuffle法は、予めいくつのビットが立つかを計算し、その後でビットをシャッフルするアルゴリズムである。立つビット数の計算にWalker’s Alias法を、ビットのシャッフルにFloydのサンプリング法を使うことで、全体で \(pN+1\) 回の乱数生成でランダムビット列を生成できる。Poisson-OR法は、 \(N\) ビットのうちランダムに1ビットだけビットが立っているビット列を、 \(k\) 個論理和(OR)を取るアルゴリズムである。これはTodo and Suwaのアルゴリズム[2]の特殊な例になっており、ビット列の数 \(k\) をポアソン分布に従うように生成することで、指定の確率でビットが立つようにできる。この手法は \(-N \log(1-p) + 1\) 回の乱数生成を伴う。有限桁法は、確率 \(p\) が二進数表記で有限桁で表せる場合に有効な手法である。確率 \(p\) が二進数表記で \(n\) 桁で表示できる場合、確率 \(1/2\) でランダムにビットが立っているビット列を \(n\) 個生成し、適切に論理和と論理積を取ることで、その確率でビットが1となるようにできる。したがって、確率が \(n\) 桁で表現される場合、有限桁法は \(n\) 回の乱数生成でビット列を生成できる。
Binomial-Shuffle法、Poisson-OR法ともに、確率 \(p\) の値が小さい場合に有効だが、 \(p\) が大きくなると必要となる乱数生成数が増えてしまう。そこで我々は、まず有限桁法で \(p\) に近い確率 \(p’\) を持つビット列を生成し、その差 \(p’-p\) をBinomial-Shuffle法もしくはPoisson-OR法で補正するハイブリッド法を考案した。これにより、32ビットであればたかだか7回、64ビットでもたかだか8回の乱数生成で任意の確率 \(p\) でビットが立っているビット列を生成できること示した。
我々はこのランダムビット列生成アルゴリズムをDirected-Percolationのマルチスピンコーディングに応用し、スカラー実装に比べて14倍の高速化に成功した。このアルゴリズムは他のモデルへの応用も期待されている。
References
- H. Watanabe, S. Morita, S. Todo, and N. Kawashima, J. Phys. Soc. Jpn. 88, 024004 (2019)
- S. Todo and H. Suwa, J. Phys.: Conf. Ser. 473, 012013 (2013).
