Prev: 3D Star of David space filler based on truncated tetrahedrons.
Next: Nebular Dust Cloud where all the stars are "blue stars"; (use in 4th)
From: geo on 30 Dec 2009 08:17
With b=2^32-1, the following primes
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[i] 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

 | 
Pages: 1
Prev: 3D Star of David space filler based on truncated tetrahedrons.
Next: Nebular Dust Cloud where all the stars are "blue stars"; (use in 4th)