RECYCLING RANDOM BITS IN PARALLEL
作者:
KATALIN FRIEDL,
SHI-CHUN TSAI,
期刊:
Parallel Algorithms and Applications
(Taylor Available online 1996)
卷期:
Volume 8,
issue 1
页码: 85-94
ISSN:1063-7192
年代: 1996
DOI:10.1080/10637199608915545
出版商: Taylor & Francis Group
关键词: expander;Pseudo-random bits;random walk
数据来源: Taylor
摘要:
We show thatrpseudo-random bits can be obtained by concatenatingtblocks ofr/tpseudo-random bits, where the blocks are generated in parallel. This can be considered as a parallel version of [8]—recycling random bits by doing a random walk on an expander. The proof is based on the fact thattsimultaneous independent random walks on an expander graph is equivalent to a random walk on a much larger expander. In [8] generating the random walk requires arithmetic operation with long integers. In the 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.
点击下载:
PDF (188KB)
返 回