C++

Forum

 
Mersenne Twister - Yet Another C++ Implementation

Zia Ur Rehman (63)
Hello folks!

A while ago, I came on this forum with a problem with C code. I was trying to write a simple implementation for Mersenne Twister. The code that I had written in C worked fine but I was going for object-oriented model, so I wrote this implementation in C++.

mersenneTwister.h 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
 
#ifndef _MERSENNE_TWISTER_
#define _MERSENNE_TWISRER_

#ifdef _MSC_VER
#include <Windows.h>
#endif
#include <climits>

/* Constant definitions! */
#define VEC_L	624				// Length of state-vector
#define SHF_C	397				// Shuffling constant
#define KNU_M	1812433253		// Knuth multiplier
#define ODG_C	2567483615		// Generator constant
#define TWC_1	2636928640		// Twisting constant #1
#define TWC_2	4022730752		// Twisting constant #2


/* MersenneTwister class */
class MersenneTwister
{
private:
	unsigned int state[VEC_L];
	unsigned short int index;

	void generateNumbers();

public:
	MersenneTwister(unsigned int);
#ifdef _MSC_VER
	unsigned __int32 extInt32();
	unsigned __int16 extInt16();
	unsigned __int8  extInt8();
#else
	unsigned int extInt32();
	unsigned short int extInt16();
	unsigned char extInt8();
#endif
	double extNormalDbl();
	double extSymmetricDbl();
};

#endif


mersenneTwister.cpp 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
 
#include "mersenneTwister.h"

MersenneTwister::MersenneTwister(unsigned int seed)
{
	unsigned long long temporaryStateVector[VEC_L];
	index = 0;
	temporaryStateVector[0] = (unsigned long long) seed;

	unsigned short int i;
	for (i=1; i<VEC_L; i++)
	{
		temporaryStateVector[i] =  ((KNU_M*((temporaryStateVector[i-1]^
			(temporaryStateVector[i-1]>>30))+i))<<32)>>32;
	}

	for (i=0; i<VEC_L; i++)
	{
		state[i] = (unsigned int) temporaryStateVector[i];
	}
}

void MersenneTwister::generateNumbers()
{
	unsigned int y;

	unsigned short int i;
	for (i=0; i<VEC_L; i++)
	{
		y = (state[i]>>31)+((state[(i+1)%VEC_L]<<1)>>1);
		state[i] = state[(i+SHF_C)%VEC_L]^(y >> 1);
		if ((y % 2) != 0)
		{
			state[i] ^= ODG_C;
		}
	}
}

#ifdef _MSC_VER
unsigned __int32 MersenneTwister::extInt32()
#else
unsigned int MersenneTwister::extInt32()
#endif
{
	if (index == 0)
	{
		generateNumbers();
	}
	unsigned int y = state[index];
	y = y^(y>>11);
	y = y^((y<<7)&TWC_1);
	y = y^((y<<15)&TWC_2);
	y = y^(y>>18);

	index = (index++)%VEC_L;
	return y;
}

#ifdef _MSC_VER
unsigned __int16 MersenneTwister::extInt16()
#else
unsigned short int MersenneTwister::extInt16()
#endif
{
	unsigned short int y;
	y = unsigned short int (extInt32() % 0xFFFF);
	return y;
}

#ifdef _MSC_VER
unsigned __int8 MersenneTwister::extInt8()
#else
unsigned char MersenneTwister::extInt8()
#endif
{
	unsigned char y;
	y = unsigned char (extInt32() % 0xFF);
	return y;
}

double MersenneTwister::extNormalDbl()
{
	double y;
	y = double(extInt32())/double(0xFFFFFFFF);
	return y;
}

double MersenneTwister::extSymmetricDbl()
{
	double y;
	y = (double(extInt32())/double(0xFFFFFFFF)) - 0.5;
	return y;
}


And for testing...
main.cpp 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
#include <iostream>
#include <cstdlib>
#include <ctime>
#include "mersenneTwister.h"

using namespace std;

int main(int argc, char **argv)
{
	MersenneTwister mTwist(__int32(time(NULL)));

	cout << mTwist.extInt32() << endl;
	cout << mTwist.extInt16() << endl;
	cout << mTwist.extInt8() << endl;
	cout << mTwist.extNormalDbl() << endl;
	cout << mTwist.extSymmetricDbl() << endl;

	return 0;
}


I want the experts on this forum to review the code. It is very basic, beginner level, so there is a lot of room for improvement. Please discuss how you think it can or should be improved.

Also, I have some performance-specific queries that I hope you can answer:

1- It is obviously not portable. How do I make it portable?
2- What if I had to compile a dynamic library (dll / so). How would I go about that? And for that matter, how would I access it in other C++ (or any other language) programs?
3- What exactly is thread-safety and how do I make it thread safe, if that is possible?
4- I want to calculate performance, as in how many numbers can be generated per second. How is that possible? (I have experimented with QPC but the results are unpredictable.)
5- How do I improve performance, make it faster?


On a side note, has anyone in here explored the application of Mersenne Twister in communication applications like encryption key generation or coded multiplexing? I read somewhere that MT is not safe for encryption. But the benefit of the object-oriented model is that I can have multiple streams from multiple generator-objects and mix (xor or multiply) them to get an encryption-safe code-generation algorithm or something. I don't know. I was looking for an expert opinion.

Thank you guys for your time.

EDIT: I meant to add comments so it's easy to understand the code. But I'm sorry that I couldn't. For now, you're going to have to read it like that. Maybe in a day or two, I'll add the commented version of the code.

EDIT: Made the questions bold, so they are easier to spot. :)
Last edited on
Zia Ur Rehman (63)
High-priority question...

You see that I have several functions for returning different types of values. I want to define a function with an arbitrary return type... Meaning, to obtain values of different types, the user can call the same function...

Right now, the function call goes like this:
1
2
3
4
5
6
 
MersenneTwister mTwist(0xabcdef);
unsigned int i = mTwist.extInt32();
unsigned short s =  mTwist.extInt16();
unsigned char c = mTwist.extInt8();
double d1 =  mTwist.extNormalDbl();
double d2 = mTwist.extSymmetricDbl();


If I use templates, I can make function calls like this:
1
2
3
4
5
6
 
MersenneTwister mTwist(0xabcdef);
unsigned int i = <unsigned int>mTwist.ext();
unsigned short s =  <unsigned short>mTwist.ext();
unsigned char c = <unsigned char>mTwist.ext();
double d1 =  <double>mTwist.ext();
double d2 = <double>mTwist.ext();


Now, the function mTwist.ext performs different operations depending on the return type. For example, for unsigned short, it extracts a 32-bit number and truncates it using modulus. For double it divides by the maximum possible value of an unsigned 32-bit integer.

How would I be able to determine the return-type in order to be able to perform type-specific operations on it?

EDIT: I don't know why no one has replied yet. I have searched and found several posts on this forum about the Mersenne Twister (however, they don't address the same problems as this one). I would presume many people here are familiar with the topic. But this is like an obsession of mine. I wouldn't be able to continue my routine work if I don't solve this quickly... :)
Last edited on
Zia Ur Rehman (63)
Still... No replies. :(
Topic archived. No new replies allowed.