首页   按字顺浏览 期刊浏览 卷期浏览 RECYCLING RANDOM BITS IN PARALLEL
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)



返 回