G

#### geo

have b as a primitive root:

543213218b^128+1, 8007626b^128+1,

8006134b^256+1, 107982b^256+1,

123554642b^512+1, 70024066b^512+1,

123471786b^1024+1, 1030770b^1024+1,

1030770b^2048+1, 914646b^2048+1,

18782b^4096+1

They are among many I have found as p=ab^r+1,

with b primitive mod p and r a power of 2 so as to

provide simpler implementations of CMWC RNGs

based on such primes and with period p-1.

Primes p=a*b^r+1 for which b=2^32-1 is primitive

are relatively easy to find for r=16,32,64,128,256.

For larger r=2^k, the largest so far is that with

r=2^12=4096 above, but r=2^13,2^14,... seem

worthy targets for worldwide prime searchers.

If you are among, or aspire to be in, that group,

and would like to search for primes that are both

notable and useful, try r=8192, 16384, 32768 or higher.

I repeat: Can any of you familiar with prime searches

find primes a*(2^32-1)^r+1 for r=8192, 16384,

32768, 65536 or beyond? (a<b)

Here is a C implementation of a CMWC,

(Complementary-Multiply-With-Carry), RNG function

based on that so-far-largest p=a*b^r+1 prime,

p=18782*(2^32-1)^4096+1,

and with period p-1 > 2^131086 or 10^39460:

--------------------------------------------------------

static unsigned long Q[4096],cary;

unsigned long CMWC4096(void)

{ unsigned long long t, a=18782LL;

static int indx=4095;

unsigned long x,s=0xfffffffe; /* s is 2^32-2 in hex */

indx=(indx+1)&4095;

t=a*Q[indx]+cary; cary=(t>>32);

x=t+cary; if(x<cary || x+1==0) {x++;cary++;}

return(Q[indx]=s-x);

}

--------------------------------------------------------

More than 131086 seed bits are needed for every

possible seeding of the Q[ ] array and the initial

'cary', but I recommend including CMWC4096( ) as

the third of a three-component KISS

(Keep-It-Simple-Stupid) RNG, with two of them,

CNG (Congruential) and XS (Xorshift), used to seed

the Q array. Thus, for convenience, only 78=32+32+14

bits are need to initialize CNG,XS and the cary<a,

after which main( ) can fill Q

*with CNG+XS*

before subsequent calls to the combination

KISS=CMWC4096( )+CNG+XS. See, for example,

"SuperKISS for 32- and 64-bit RNGs in both C and Fortran"

posted on math.sci and other groups, as well as other

postings for KISS random number generators.

The above CMWC4096( ) RNG produces 32-bit random integers

at a rate of 132 million per second, or 110 million

per second as part of a CMWC4096( )+CNG+XS KISS.

gcc, Vista, 2.4GHz Intel Core2 Quad Q6600

Yours might be faster; try and compare.

Or compare with other RNGs for speed, complexity,

length of period and performance on tests of randomness.

Or perhaps you can find a p=ab^8192+1 prime to provide

an even better CMWC8192( ) and include it with a KISS.

George Marsaglia

before subsequent calls to the combination

KISS=CMWC4096( )+CNG+XS. See, for example,

"SuperKISS for 32- and 64-bit RNGs in both C and Fortran"

posted on math.sci and other groups, as well as other

postings for KISS random number generators.

The above CMWC4096( ) RNG produces 32-bit random integers

at a rate of 132 million per second, or 110 million

per second as part of a CMWC4096( )+CNG+XS KISS.

gcc, Vista, 2.4GHz Intel Core2 Quad Q6600

Yours might be faster; try and compare.

Or compare with other RNGs for speed, complexity,

length of period and performance on tests of randomness.

Or perhaps you can find a p=ab^8192+1 prime to provide

an even better CMWC8192( ) and include it with a KISS.

George Marsaglia