On the Distribution of Fractional Linear Congruential Pseudorandom Numbers

Yoshinori TAKEI  Toshinori YOSHIKAWA  Xi ZHANG  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E86-D   No.2   pp.276-284
Publication Date: 2003/02/01
Online ISSN: 
DOI: 
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Issue on Selected Papers from LA Symposium)
Category: Algorithms
Keyword: 
pseudorandom generators,  fractional linear transforms,  discrepancy,  inversive linear congruent generators,  leap-frog,  

Full Text: PDF(268.1KB)>>
Buy this Article




Summary: 
As pseudorandom number generators for Monte Carlo simulations, inversive linear congruential generators (ICG) have some advantages compared with traditional linear congruential generators. It has been shown that a sequence generated by an ICG has a low discrepancy even if the length of the sequence is far shorter than its period. In this paper, we formulate fractional linear congruential generators (FCG), a generalized concept of the inversive linear congruential generators. It is shown that the sequence generated by an FCG is a geometrical shift of a sequence from an ICG and satisfies the same upper bounds of discrepancy. As an application of the general formulation, we show that under certain condition, "Leap-Frog technique," a way of splitting a random number sequence to parallel sequences, can be applied to the ICG or FCG with no extra cost on discrepancy.