Jump to content

  • Log In with Google      Sign In   
  • Create Account

Mersenne twister bug...


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
1 reply to this topic

#1 Vortez   Crossbones+   -  Reputation: 2704

Like
0Likes
Like

Posted 11 October 2013 - 12:54 AM

Hi, i've been using this Mersenne twister class in c++, and decided to scan my files using cppcheck, and found a bug, which says

 

Error: Array 'MT[624]' accessed at index 624, which is out of bounds.

 

What's strange is that the error is also in the pseudo code from wikipedia. I also noticed that im starting

at index 1 instead of 0 which is probably another bug (dunno why the hell i did that).

 

Here's my code, it's not very long

#ifndef _CRNG_H_
#define _CRNG_H_
#ifdef __cplusplus

#include "Windows.h"

class CRNG {
public:
	CRNG();
private:
	int MT[624]; 
	int index;

	void GenerateNumbers();
public:
	void InitializeGenerator(int seed);
	int  ExtractNumber();
};

#endif
#endif //_CRNG_H_
#include "RNG.h"

//
CRNG::CRNG()
{
	InitializeGenerator(GetTickCount());
}

// Initialize the generator from a seed
void CRNG::InitializeGenerator(int Seed)
{
	index = 0;
	MT[0] = Seed;
	for(int i = 1; i <= 623; i++){ // loop over each other element
		MT[i] = (1812433253 * (MT[i-1] ^ (MT[i-1] >> 30)) + i);
	}
}


// Extract a tempered pseudorandom number based on the index-th value,
// calling generateNumbers() every 624 numbers
int CRNG::ExtractNumber()
{
	if(index == 0)
		GenerateNumbers();
	
	int y = MT[index];
	y = y ^ (y >> 11);
	y = y ^ ((y << 7) & (2636928640));
	y = y ^ ((y << 15) & (4022730752));
	y = y ^ (y >> 18);
	
	index = (index + 1) % 624;
	return y;
}

// Generate an array of 624 untempered numbers
void CRNG::GenerateNumbers()
{
	for(int i = 1; i <= 623; i++){ 
		
		int y = ((MT[i] & 0x80000000) + (MT[i+1] & 0x7FFFFFFF)) % 624; // <- here's the bug
		
		MT[i] = MT[(i + 397) % 624] ^ (y >> 1);
		
		if((y % 2) == 1) // y is odd
			MT[i] = MT[i] ^ (2567483615);
	}
}

Soo, what's with the buffer overflow? Is it supposed to take MT[0] instead?

 

Thx in advance.

 

EDIT: omg, i misplaced the modulus... and that 'i' should definitively be 0... hope this won't break old projects wacko.png

 

The weird thing is, it worked perfectly for encryption/decryption stuffs and never failed or crashed...


Edited by Vortez, 11 October 2013 - 01:02 AM.


Sponsor:

#2 Vortez   Crossbones+   -  Reputation: 2704

Like
1Likes
Like

Posted 11 October 2013 - 02:08 AM

Here's the fixed code:

// Generate an array of 624 untempered numbers
void CRNG::GenerateNumbers()
{
	for(int i = 0; i < 624; i++){ 
		
		int y = ((MT[i] & 0x80000000) + (MT[(i+1) % 624] & 0x7FFFFFFF));
		
		MT[i] = MT[(i + 397) % 624] ^ (y >> 1);
		
		if((y % 2) != 0) // y is odd
			MT[i] = MT[i] ^ (0x9908B0DF);
	}
}





Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS