From:	George Marsaglia <geo AT stat DOT fsu DOT edu>
Newsgroups:	comp.os.msdos.djgpp
Subject:	Re: An inline assembler RNG for C
Date:	Thu, 18 Feb 1999 16:58:26 -0500
Organization:	Florida State University
Lines:	42
Message-ID:	<36CC8D02.3690E0EB@stat.fsu.edu>
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> <20678zseao DOT fsf AT Sky DOT inp DOT nsk DOT su>
NNTP-Posting-Host:	dial430.acns.fsu.edu
Mime-Version:	1.0
X-Mailer:	Mozilla 4.08 [en] (Win95; I)
To:	djgpp AT delorie DOT com
DJ-Gateway:	from newsgroup comp.os.msdos.djgpp
Reply-To:	djgpp AT delorie DOT com

>
> Maybe documentation for this RNG is available somewhere?
>
> --
> Michael Bukin

As stated in my original post, theory behind MWC generators
can be found in the file mwc1.ps of
 The Marsaglia Random Number CDROM
                      with
The Diehard Battery of  Tests of Randomness

available at
        http://stat.fsu.edu/pub/diehard/cdrom
The original 1000 copies, distributed free under an NSF Grant,
are long  gone.

As for the mechanics of the multiply-with-carry method,
            x(n)=a*x(n-1) +carry mod 2^32,
the period is the order of b=2^32 in the group of
residues relatively prime to m=a*b-1.
For the examples I gave,  'a' is chosen so that
m=a*b-1  is a safeprime, that is, both m and (m-1)/2
are prime.  Then the order of any residue of m, and
in particular  b=2^32 ,  is at least (m-1)/2.    But since b
is a square, it cannot be a primitive root of m, so its order, and
the period of the  RNG, must  be (m-1)/2, on the order of 2^60.

BUT  NOONE HAS YET SUGGESTED AN EASY
INLINE ASSEMBLER SECTION OF CODE FOR THIS.
SEVERAL RESPONDENTS SUGGESTED IT COULD
BE DONE USING LONGLONG's, BUT ONLY A FEW PERCENT
OF  CURRENT CPU's SEEM TO HAVE TRUE 64-BIT
ARITHMETIC.

Are there no assembler-in-C experts out there?

George Marsaglia

- Raw text -