From: M DOT A DOT Bukin AT inp DOT nsk DOT su
To: djgpp AT delorie DOT com
Subject: Re: An inline assembler RNG for C
References: <George Marsaglia's message of "Wed, 17 Feb 1999 13:35:29 -0500">  <36CB0BF1 DOT 23FF9E2 AT stat DOT fsu DOT edu> <3 DOT 0 DOT 6 DOT 32 DOT 19990218103218 DOT 008d7180 AT pop DOT globalserve DOT net>
Date: 19 Feb 1999 01:27:27 +0600
In-Reply-To: Paul Derbyshire's message of "Thu, 18 Feb 1999 10:32:18 -0500"
Message-ID: <20678zseao.fsf@Sky.inp.nsk.su>
Lines: 32
X-Mailer: Gnus v5.5/Emacs 19.34
Reply-To: djgpp AT delorie DOT com

Paul Derbyshire <pderbysh AT usa DOT net> writes:

> At 07:18 PM 2/18/99 +0600, you wrote:
> >Can it be proved that there is no situation when x(i+1)=x(i) and
> >c(i+1)=c(i), and generated sequence will not degrade to x(i)?
> 
> The original poster stated as much...indeed, he stated the repeat time
> should be a very large prime number in the same ballpark as 2^32.

I will try to explain with example

sequence of 1 bit numbers x and c is generated from 1 bit numbers c(i)
and x(i) with recurrent formula:

tmp = x(i) * a + c(i);
x(i + 1) = (tmp & 1);
c(i + 1) = (tmp >> 1) & 1;

For initial number x(0) = 1, c(0) = 0 and a = 1, x(i) in generated
sequence for all i will be equal to 1 and all c(i) will be 0.  Other
initial numbers will lead to sequences of x=1, c=0, or x=0, c=0, maybe
after some relaxation period.

This extreme example does not give much choice for coefficient `a',
maybe in the original generator good choice of `a' prevents
such thing, no matter what initial x and c are used, except for x=0,
c=0.

Maybe documentation for this RNG is available somewhere?

-- 
Michael Bukin