• Welcome to the new Internet Infidels Discussion Board, formerly Talk Freethought.

The Programming Thread

There are at least two "cryptographically secure" PRNGs with source code in the public domain. The most famous of these might be the Mersenne Twister (MT19937) with a cycle of (219937-1). We might assume that "security" is irrelevant but these random generators generate numbers which are VERY . . . random! Why not use them?

One possible reason to avoid them would be the computational cost of computing the next pseudo-random number in sequence. HOWEVER it is possible to minimize the consumption of the random bits.

Obviously, a binary decision with probabilities (0.5, 0.5) can be achieved with a SINGLE bit from the random-number generator. In other words we need only call MT19937 once to get 32 such random decisions.

Less obvious is that a binary decision like (0.8173, 0.1827) can be achieved with just 0.687 random bits on average.

Similarly, a uniform integer on N16 can be achieved with 4 random bits, and a uniform integer on N17 can be achieved with just 4.09 bits on average.

Is this hint enough to see how it's done?
 
The Mersenne Twister 32 bit is the default C++ library random number generator. there is also a 64 bit Mersenne Twister and a linear congruential generator.

I downloaded the Mersenne Twister code.

I have been using 10^10 iterations for testing and comparing URAND to C++ Mersenne Twister and C rand(). The C++ Mersenne Twister executes much slower than the URAND I posted. To be expected, the URAND code has one multiplication and one addition for each iteration.


In terms of frequency testing URAND look like the C++ Mersenne Twister in terms of randomness. They are equally close to a true unform distribution in terms of the number of coornces of a number. Both are an order of magnitude better than C rand() as a unform approximation.

Plotting URANFD and Mersenne Twister both look like random eectricall noise. I took the Fourier trasform of both and they both have the flat trasform of random noise as I would see with elecrcal noise.

That leaves the period and namdomness of intervals between occurences of a number, the gap test.

I have been codng a gap test.

Which to use? It alweys coes down to the application. The linear comgruential algorithm is simple, compact, and fast with reasonbale charteristcs. Suitable for the kind of simualtions I did on systems.
 
Execution times C++ Mersenne Twister vs LG.

for 10^10 iterations C++ took 68 seconds, URAND LG took .016 seconds.

Made a dumb mistake at first. Make sure the compiler is in release mode not debug, it runs slower in debug.

MS documentation says other than hardware devices Mersenne Twister has the highest performance, LG the lowest.


Code: 
#include <random>
#include <chrono>

int main(){
    long long i,n = pow(10,10);
    int x;
//   Mersenne Twister 32 bit
//   unsigned seed = chrono::system_clock::now().time_since_epoch().count();
//   default_random_engine generator (seed);
//    uniform_int_distribution<int> dist (0,100); // random ints 0-100
//    for(i=0;i<n;i++)x = dist(generator);;
  
    //URAND LG 32 bit
    int sf = 100,os = 0;
    unsigned m = 0x7fffffff;
    unsigned k1 = 907633385,k2 = 1686629725;
    unsigned rand_num = 1;
    for(i=0;i<n;i++){
        rand_num = rand_num*k2 + k1;
        x = (rand_num%m)%sf + os; // random ints 0-100
       }
  return 0;
  }
 
Last edited:
My little library has several PRNGs to choose from, though I've found no reason to use something faster than Mersenne Twister. When I time these various PRNGs, the times to call the PRNG 5 billion times range from 55 seconds (Bob Jenkin's Burtle PRNG) to 119 seconds (Marsaglia's KISS PRNG). GNU's compound Tausworthe (random(), 69 seconds) and the Mersenne Twister (83 seconds) are about midway between Burtle (which emphasizes speed) and Marsaglia (which emphasizes ridiculously long period).

These numbers "compare apples with apples." They were measured with the same compiler and overhead on my VERY old laptop running cygwin. Much of the time was spent on loop-handling etc. OUTSIDE the actual PRNG. Looking at the source code for the PRNGs we see that, Yes, the time closely parallels the number of operations in the critical code.

As you can see, ALL these generators are fast enough. In a real application the choice of PRNG will have almost no effect on net speed.

As I've mentioned, applications which consume 32 random bits for a simple switch can often make do with a single bit or even less. . . .
Swammerdami said:
Obviously, a binary decision with probabilities (0.5, 0.5) can be achieved with a SINGLE bit from the random-number generator. In other words we need only call MT19937 once to get 32 such random decisions.

Less obvious is that a binary decision like (0.8173, 0.1827) can be achieved with just 0.687 random bits on average.

Similarly, a uniform integer on N16 can be achieved with 4 random bits, and a uniform integer on N17 can be achieved with just 4.09 bits on average.

Is this hint enough to see how it's done?
Click to expand...

However this is just a fun exercise! The PRNGs are all so fast that saving those random bits is pointless!

steve_bank said:
Execution times C++ Mersenne Twister vs LG.

for 10^10 iterations C++ took 68 seconds, URAND LG took .016 seconds.
Click to expand...
Obviously something went badly wrong in your experiment! I'm sure you'll agree that you didn't do 10^10 iterations of anything in 16 milliseconds!
 
Don;t have a clue what you are 'hinting' at. I scanned through the Mersenne algorithm and there is plenty of code on the net. No mystery or puzzle.

Feel free to post complete working debugged code that others can run.
 
steve said:
Don;t have a clue what you are 'hinting' at. I scanned through the Mersenne algorithm and there is plenty of code on the net. No mystery or puzzle.
Click to expand...

Most of my comments had nothing whatsoever to do with Mersenne Twister.
My question was about your "URAND LG". Perhaps you should show us that code.

Swammerdami said:
steve_bank said:
Execution times C++ Mersenne Twister vs LG.

for 10^10 iterations C++ took 68 seconds, URAND LG took .016 seconds.
Click to expand...
Obviously something went badly wrong in your experiment! I'm sure you'll agree that you didn't do 10^10 iterations of anything in 16 milliseconds!
Click to expand...

No comment about this? :confused2:

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

I will post two miscellaneous comments about my random-number routines.

(1) when choosing a uniform real variate over (0, 1) one starts with a specified number of bits. By default my library routines use 31 bits. The variate is then chosen to be distributed uniformly over
{1,3,5,7,9,... , 4294967291, 4294967293, 232-1 } ÷ 232
Note that this chooses a number from (0, 1) -- not [0,1) as many or most implementations do. Note that the mean will be 0.5 exactly. Perfectionistic? Sure, but why not? Steve, modify your code to use, say 8 bits instead of 32 bits and se what mean value you get.

(2) I'll present pseudo-code to illustrate how to minimize the number of random bits consumed by smallish selections and binary decision.

Let Nk denote {0, 1, 2, 3, ..., k-1 }
Internally, the code maintains a pair of integers (r, m). r is a uniformly-distributed random variable over Nm
I will describe two routines Augment and Decide.

Augment (k) // used to increase ("augment") the precision of (r, m)​
Retrieve k bits from the PRNG; i.e. retrieve a random x uniform over N2k​
Replace (r, m) as follows. Obviously shifts will be used instead of multiplies.​
r ← r * 2k + x​
m ← m * 2k​
​
Decide (p) // return 1 with probability p, 0 with probability 1-p​
If m is "too small" call Augment (k) for some appropriate k (e.g. make m a 31-bit number).​
Approximate p as s/m for some integer s.​
If r < s Then​
m ← s​
Return 1​
Else (r ≥ s) Then​
m ← m - s​
r ← r - s​
Return 0​

The basic idea is that there is UNUSED randomness available for free after a Decide. Keep that randomness, rather than discarding it and "wasting" a call to the 32-bit PRNG every time. (As mentioned, even very good PRNGs are so good that the technique, however "nifty", has no importance unless you're working with a very expensive physical RNG.)

Anyone who takes the time to study this "Decide (p)" routine -- perhaps working simple examples -- and then understands how it works, should give themself a very big pat on the back! I've chatted with enough expert programmers to realize that this method -- however simple the above pseudo-code may appear -- is likely to baffle. Kudos to anyone who can pursue it all the way to an "Aha!" moment.
 
You must log in or register to reply here.
Back
Top Bottom