乱数ライブラリー

Linear Feedback Shift Register Generator (M-series)

A pseudo-random number generator based on a recursive binary sequence:

b i = ( a p b i - p + a p - 1 b i - p + 1 + + a 1 b i - 1 )     mod  2 b_i=(a_{p}b_{i-p}+a_{p-1}b_{i-p+1}+…+a_{1}b_{i-1})mod 2 with constant coefficients a p underline {a_p} as well as sequence terms b i b_i restricted to binary values. In practical applications most a p underline {a_p} are set to zero. In order to obtain an l l -bit pseudo-random integer, the binary sequence b i b_i is iterated forward l l times and successive bits b i b_i , b i - 1 b_{i-1} , dotsaxis , b i - l + 1 b_{i-l+1} form a binary representation of an l l -bit integer number. To obtain a pseudo-random floating-point number in the range [ 0,1 0,1 ) , the l l -bit integer must be further divided by 2 l underline {2^l} .

In practice the following simplified recursive sequence is used:

b i = ( b i - p + b i - p + q )     mod  2 b_i=(b_{i-p}+b_{i-p+q})mod2

Since terms b i b_i are binary this is equivalent to peforming the exclusive-OR (XOR) operation (in some implementations XOR has been replaced by XNOR):

b i = b i - p  ⊕ b i - p + q b_i=b_{i-p} XOR b_{i-p+q}



▲Back to this TOP