C# Mersenne Twister random integer generator implementation (SFMT) monte carlo simulation

cmontecarlorandom

So far I've been using the C# Mersenne Twister found here to generate random numbers:

http://www.centerspace.net/resources.php

I just discovered SFMT which is supposed to be twice as fast here:

http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/SFMT/

Can anyone point me at a C# implementation of SFMT?

My requirements are to generate an integer between (and including) 0 and 2^20 (1048576).

I need to do this trillions of times everyday for a simulation running on a 24 hour clock so I am prepared to spend days tweaking this to perfection.

Currently I've tweaked the Center Space Mersenne Twister by adding a new method to fit my requirements:

public uint Next20()
{            
    return (uint)(genrand_int32() >> 12);
}

Using the method genrand_int32() I'd like to produce my own version, genrand_int20(), that generates an integer between (and including) 0 and 2^20 to save on the cast above and shift but I don't understand the mathematics. Exactly how can I do this?

Also is using an uint going to be faster that int, or is just a matter of addressable numbers? Because I only need up to 1048576, I am only concerned with speed.

Also this will be running on a Windows Server 2003 R2 SP2 (32bit) box with .NET 2. Processor is AMD Opteron 275 (4 core).

Best Answer

What you can do is download the source from the link you discovered on Code Project. Unzip it, load the solution in Visual Studio and compile it. This will give you source, an unmanaged c dll and a .lib file.

You can P/Invoke the functions in this dll, (there are only 5 simple functions exported, of which you need only two) or you can use this dll, lib, and the SFMT header file to create a managed wrapper dll you can use in C# without P/Invoke. I just tried this method and it was very simple to do. There was no explicit marshalling involved.

Here's how. Once you have downloaded and compiled the source (you need the header and the lib file that is created in addition to the dll) create a new C++ CLR Class Library project. Call it WrapSFMT or something. Go the project properties. Under C++/Precompiled Headers, change to "Not using precompiled headers." Under the Linker/General/Additional Library Directories, enter the path to the SFMT.lib. Under Linker/Input/Additional Dependencies, add SFMT.lib. Close the property pages. Copy SFMT.h to your project folder and include it in the project.

Edit WrapSFMT.h to read as follows:

#pragma once
#include "SFMT.H"

using namespace System;

namespace WrapSFMT {

public ref class SRandom
{
public:SRandom(UInt32);
public:UInt32 Rand32(void);
};
}

These declare the methods that will be in your class. Now edit WrapSFMT.cpp to read:

#include "WrapSFMT.h"

namespace WrapSFMT {

SRandom::SRandom(UInt32 seed)
{
    init_gen_rand(seed);
}

UInt32 SRandom::Rand32()
{
    return gen_rand32();
}
}

These implement the methods you declared in the header file. All you are doing is calling functions from the SFMT.dll, and C++/CLI is automatically handling the conversion from unmanaged to managed. Now you should be able to build the WrapSFMT.dll and reference it in your C# project. Make sure the SFMT.dll is in the path, and you should have no problems.

Related Solutions

Javascript – Seeding the random number generator in Javascript

I've implemented a number of good, short and fast Pseudorandom number generator (PRNG) functions in plain JavaScript. All of them can be seeded and provide high quality numbers.

First of all, take care to initialize your PRNGs properly. To keep things simple, the generators below have no built-in seed generating procedure, but accept one or more 32-bit values as the initial seed state of the PRNG. Similar or sparse seeds (e.g. a simple seed of 1 and 2) have low entropy, and can cause correlations or other quality issues, resulting in the output having similar properties (such as randomly generated levels being similar). To avoid this, it is best practice to initialize PRNGs with a well-distributed, high entropy seed.

Thankfully, hash functions are very good at generating seeds from short strings. A good hash function will generate very different results even when two strings are similar. Here's an example seed generator based on MurmurHash3's mixing function:

function xmur3(str) {
    for(var i = 0, h = 1779033703 ^ str.length; i < str.length; i++)
        h = Math.imul(h ^ str.charCodeAt(i), 3432918353),
        h = h << 13 | h >>> 19;
    return function() {
        h = Math.imul(h ^ h >>> 16, 2246822507);
        h = Math.imul(h ^ h >>> 13, 3266489909);
        return (h ^= h >>> 16) >>> 0;
    }
}

Each subsequent call to the return function of xmur3 produces a new 32-bit hash value to be used as a seed in a PRNG. Here's how you might use it:

// Create xmur3 state:
var seed = xmur3("apples");
// Output four 32-bit hashes to provide the seed for sfc32.
var rand = sfc32(seed(), seed(), seed(), seed());

// Output one 32-bit hash to provide the seed for mulberry32.
var rand = mulberry32(seed());

// Obtain sequential random numbers like so:
rand();
rand();

However, this is only one possible solution. Alternatively, simply choose some dummy data to pad the seed with, and advance the generator a few times (12-20 iterations) to mix the initial state thoroughly. This is often seen in reference implementations of PRNGs, but it does limit the number of initial states:

var seed = 1337 ^ 0xDEADBEEF; // 32-bit seed with optional XOR value
// Pad seed with Phi, Pi and E.
// https://en.wikipedia.org/wiki/Nothing-up-my-sleeve_number
var rand = sfc32(0x9E3779B9, 0x243F6A88, 0xB7E15162, seed);
for (var i = 0; i < 15; i++) rand();

The output of these PRNG functions produce a positive 32-bit number (0 to 2³²-1) which is then converted to a floating-point number between 0-1 (0 inclusive, 1 exclusive) equivalent to Math.random(), if you want random numbers of a specific range, read this article on MDN. If you only want the raw bits, simply remove the final division operation.

Note: JavaScript numbers can only represent whole integers up to 53-bit resolution. And when using bitwise operations, this is reduced to 32. Modern PRNGs in other languages often use 64-bit operations, which require shims when porting to JS that can drastically reduce performance. The algorithms here only use 32-bit operations, as it is directly compatible with JS.

Now, onward to the the generators. (I maintain the full list with references and license info here)

sfc32 (Simple Fast Counter)

sfc32 is part of the PractRand random number testing suite (which it passes of course). sfc32 has a 128-bit state and is very fast in JS.

function sfc32(a, b, c, d) {
    return function() {
      a >>>= 0; b >>>= 0; c >>>= 0; d >>>= 0; 
      var t = (a + b) | 0;
      a = b ^ b >>> 9;
      b = c + (c << 3) | 0;
      c = (c << 21 | c >>> 11);
      d = d + 1 | 0;
      t = t + d | 0;
      c = c + t | 0;
      return (t >>> 0) / 4294967296;
    }
}

Mulberry32

Mulberry32 is a simple generator with a 32-bit state, but is extremely fast and has good quality (author states it passes all tests of gjrand testing suite and has a full 2³² period, but I haven't verified).

function mulberry32(a) {
    return function() {
      var t = a += 0x6D2B79F5;
      t = Math.imul(t ^ t >>> 15, t | 1);
      t ^= t + Math.imul(t ^ t >>> 7, t | 61);
      return ((t ^ t >>> 14) >>> 0) / 4294967296;
    }
}

I would recommend this if you just need a simple but decent PRNG and don't need billions of random numbers (see Birthday problem).

xoshiro128**

As of May 2018, xoshiro128** is the new member of the Xorshift family, by Vigna & Blackman (professor Vigna was also responsible for the Xorshift128+ algorithm powering most Math.random implementations under the hood). It is the fastest generator that offers a 128-bit state.

function xoshiro128ss(a, b, c, d) {
    return function() {
        var t = b << 9, r = a * 5; r = (r << 7 | r >>> 25) * 9;
        c ^= a; d ^= b;
        b ^= c; a ^= d; c ^= t;
        d = d << 11 | d >>> 21;
        return (r >>> 0) / 4294967296;
    }
}

The authors claim it passes randomness tests well (albeit with caveats). Other researchers have pointed out that it fails some tests in TestU01 (particularly LinearComp and BinaryRank). In practice, it should not cause issues when floats are used (such as these implementations), but may cause issues if relying on the raw low bits.

JSF (Jenkins' Small Fast)

This is JSF or 'smallprng' by Bob Jenkins (2007), who also made ISAAC and SpookyHash. It passes PractRand tests and should be quite fast, although not as fast as sfc32.

function jsf32(a, b, c, d) {
    return function() {
        a |= 0; b |= 0; c |= 0; d |= 0;
        var t = a - (b << 27 | b >>> 5) | 0;
        a = b ^ (c << 17 | c >>> 15);
        b = c + d | 0;
        c = d + t | 0;
        d = a + t | 0;
        return (d >>> 0) / 4294967296;
    }
}

C# – Random number generator only generating one random number

Every time you do new Random() it is initialized using the clock. This means that in a tight loop you get the same value lots of times. You should keep a single Random instance and keep using Next on the same instance.

//Function to get a random number 
private static readonly Random random = new Random(); 
private static readonly object syncLock = new object(); 
public static int RandomNumber(int min, int max)
{
    lock(syncLock) { // synchronize
        return random.Next(min, max);
    }
}

Edit (see comments): why do we need a lock here?

Basically, Next is going to change the internal state of the Random instance. If we do that at the same time from multiple threads, you could argue "we've just made the outcome even more random", but what we are actually doing is potentially breaking the internal implementation, and we could also start getting the same numbers from different threads, which might be a problem - and might not. The guarantee of what happens internally is the bigger issue, though; since Random does not make any guarantees of thread-safety. Thus there are two valid approaches:

Synchronize so that we don't access it at the same time from different threads
Use different Random instances per thread

Either can be fine; but mutexing a single instance from multiple callers at the same time is just asking for trouble.

The lock achieves the first (and simpler) of these approaches; however, another approach might be:

private static readonly ThreadLocal<Random> appRandom
     = new ThreadLocal<Random>(() => new Random());

this is then per-thread, so you don't need to synchronize.