Wu, P.-C., Huang, K.-C., Ouyang, S.-T., "Bit-Parallel Random Number Generation for Discrete Uniform Distributions," Computer Physics Communications, Vol. 144, No. 3, 15 April 2002, pp.252-260. (SCI, EI)

論文題目: 離散平均分佈的位元平行亂數產生器

Abstract

When a die is cast, the outcome is one of the six sides, i.e., the outcome is discrete and uniformly distributed over the range R = { 1, 2, 3, 4, 5, 6 }. Generating random numbers with such a distribution is very easy: obtain a random number w Î W, the domain of the random numbers, and take (w mod |R|) + 1. However, many uniform discrete distributions have a rather short range, e.g., |R| = 6 in a dice game, and |R| = 3 for the walking directions of a 2-dimensional nonreversal random walk. The number w is typically a machine word, i.e., log2(|W|) » 32 in a 32-bit computer, so generating a log2(|R|)-bit random number has consumed about 32 random bits. When |W| >> |R|, it is wasteful and hence inefficient. This paper presents an efficient algorithm for generating random numbers for the distributions with |R| discrete uniform outcomes. The algorithm uses parallel bit-wise operations on machine words. The performance results of the algorithm are presented. The statistical quality of the random numbers generated from this algorithm is also discussed.

Key Words: random number generators, Monte Carlo simulation, random walks, discrete uniform distribution.

摘要

擲骰子遊戲的結果是六面中的一面朝上,此結果是離散且平均分佈在區間R = { 1, 2, 3, 4, 5, 6 }。產生此機率分佈的亂數並不難:得到一亂數 wÎ W,取 (w mod |R|) + 1,其中W為亂數的領域(domain)。然而,許多離散平均分佈的範圍都不大,如擲骰子遊戲中,|R| = 6;又如二維不可逆(nonreversal)隨機漫步中,|R| = 3。數值w通常是一機器字組(machine word),亦即在一32位元電腦中log2(|W|) » 32,因此產生log2(|R|)位元的亂數已耗去約32個亂數位元。當|W| >> |R|時,既浪費亂數位元又沒效率。本文提出一快速的演算法以產生範圍|R|的離散平均分佈的亂數,此演算法在機器字組上採用平行的位元運算。本文並報告此演算法的效能及使用此一演算法產生的亂數的統計品質。

關鍵詞:亂數產生器,蒙地卡羅模擬、隨機漫步、離散平均分佈。