K. Friedl, Comput. & Autom. Inst., Hungarian Acad. of Sci., Budapest, Hungary
Shi-Chun Tsai, Comput. & Autom. Inst., Hungarian Acad. of Sci., Budapest, Hungary
Shows that r pseudo-random bits can be obtained by concatenating t blocks of r/t pseudo-random bits, where the blocks are generated in parallel. This can be considered as a parallel version of R. Impagliazzo and D. Zuckerman's (1989) method of recycling random bits by doing a random walk on an expander. The proof is based on the fact that t simultaneous independent random walks on an expander graph is equivalent to a random walk on a much larger expander. Impagliazzo and Zuckerman's method of generating the random walk required arithmetic operations with long integers. In the authors' parallel version, the integers involved are much shorter, and different segments of the pseudo-random bits are generated independently in parallel. Optimal speedup is also achieved.
Index Terms:
random number generation; arithmetic; parallel algorithms; randomised algorithms; pseudo-random bits; block concatenation; parallel algorithm; random bit recycling; random walk; expander graph; arithmetic operations; short integers; independently generated bit segments; optimal speedup
Citation:
K. Friedl, Shi-Chun Tsai, "Recycling random bits in parallel," hicss, pp.14, 28th Hawaii International Conference on System Sciences (HICSS'95), 1995