resolved: NXC Mersenne Twister RNG for NXT rand with srand

[HaWe]

I don't understand this error msg:

# Error: Line type "Code" is not valid while in the "Data Segment" state
File "c:\Temp\temp.nxc" ; line 7
# index sword
#----------------------------------------------------------
# Error: Invalid variable argument: index
File "c:\Temp\temp.nxc" ; line 13
# mov index, __D0InitTT800
#----------------------------------------------------------
# Error: Error parsing expression: index
File "c:\Temp\temp.nxc" ; line 18
#
#----------------------------------------------------------
# Error: Error parsing expression: index
File "c:\Temp\temp.nxc" ; line 20
#
#----------------------------------------------------------
# Error: Invalid variable argument: index
File "c:\Temp\temp.nxc" ; line 34
# mov index, __D0TT800
#----------------------------------------------------------
# Error: Error parsing expression: index
File "c:\Temp\temp.nxc" ; line 36
#
#----------------------------------------------------------
# Error: Error parsing expression: index
File "c:\Temp\temp.nxc" ; line 36
#
#----------------------------------------------------------
# Error: Invalid variable argument: index
File "c:\Temp\temp.nxc" ; line 36
# add index, __constVal0, __constVal1
#----------------------------------------------------------
8 errors during compilation

this is the NXC pseudo C code:

Code: Select all

int N;
int M;
unsigned long A[2];
unsigned long y[25];
int index;

void InitTT800() {
  N = 25;
  M = 7;
  A[0] = 0;
  A[1] = 0x8ebfd028;
  index = N+1;
}

unsigned long TT800(void) {
  unsigned long r, s, e;
  int k;
  
  if (index >= N) {
    if (index > N) {
       r = 9;
       s = 3402;
       for (k=0 ; k<N ; ++k) {
         r = 509845221 * r + 3;
         s *= s + 1;
         y[k] = s + (r >> 10);
       }
    }
    for (k=0 ; k<N-M ; ++k)
       y[k] = y[k+M] ^ (y[k] >> 1) ^ A[y[k] & 1];
    for (; k<N ; ++k)
       y[k] = y[k+(M-N)] ^ (y[k] >> 1) ^ A[y[k] & 1];
    index = 0;
  }

  e = y[index++];
  e ^= (e << 7)  & 0x2b5b2500;
  e ^= (e << 15) & 0xdb8b0000;
  e ^= (e >> 16);
  return e;
}


task main() {
  long rd;
  InitTT800();
  rd = TT800();
  NumOut(0,48, rd);
  rd = TT800();
  NumOut(0,40, rd);
  rd = TT800();
  NumOut(0,32, rd);
  rd = TT800();
  NumOut(0,24, rd);
  rd = TT800();
  NumOut(0,16, rd);
  
  while(1);
}

this is the original ANSI C code:

Code: Select all

unsigned TT800(void) {
  const int N = 25;
  const int M = 7;
  const unsigned A[2] = { 0, 0x8ebfd028 };

  static unsigned y[25];
  static int index = N+1;

  if (index >= N) {
    int k; 
    if (index > N) {
       unsigned r = 9, s = 3402;
       for (k=0 ; k<N ; ++k) {
         r = 509845221 * r + 3;
         s *= s + 1;
         y[k] = s + (r >> 10);
       }
    }
    for (k=0 ; k<N-M ; ++k)
       y[k] = y[k+M] ^ (y[k] >> 1) ^ A[y[k] & 1];
    for (; k<N ; ++k)
       y[k] = y[k+(M-N)] ^ (y[k] >> 1) ^ A[y[k] & 1];
    index = 0;
  }

  unsigned e = y[index++];
  e ^= (e << 7) & 0x2b5b2500;
  e ^= (e << 15) & 0xdb8b0000;
  e ^= (e >> 16);
  return e;
}

[spillerrec]

It seems there is some sort of issue with "index" and the compiled NBC code. Rename "index" to something else and it compiles.

EDIT: "index" is a NBC statement for reading variables in an array. Since you declare it as a global variable, it doesn't prefix it in the NBC code and the name collision happen. So the compiler should also prefix global variable names too to avoid these issues. Same issue appears if you try to use "add" or "mov" for variable names.
(NBC code have two parts, a variable declaration section and a code section, so since there is a NBC statement in the variable declaration part it becomes confused.)

[HaWe]

thank you very much!
Now the Mersenne Twister is running :)

surprisingly it gives a negative value (first output line), although I defined all random numbers as "unsigned long". Is the original program using bigger longs than NXC supports?
I don't understand quite all the code.
Here is the current version:

Code: Select all

// Mersenne Twister TT800
// by Makoto Matsumoto & Takuji Nishimura
// periodicity: 6,7*10^240
// http://de.wikipedia.org/wiki/Mersenne_Twister
// version 0.2

#define printf1( _x, _y, _format1, _value1) { \
  string sval1 = FormatNum(_format1, _value1); \
  TextOut(_x, _y, sval1); \
}

int N_MTW;
int M_MTW;
unsigned long A_MTW[2];
unsigned long y_MTW[25];
int i_MTW;
char virgin_MTW=true;

void InitMTW() {
  N_MTW = 25;
  M_MTW = 7;
  A_MTW[0] = 0;
  A_MTW[1] = 0x8ebfd028;
  i_MTW = N_MTW+1;
}

unsigned long Mrand(void) {
  unsigned long r, s, e;
  int k;
  
  if (virgin_MTW) {virgin_MTW=FALSE; InitMTW(); }
  
  if (i_MTW >= N_MTW) {
    if (i_MTW > N_MTW) {
       r = 9;
       s = 3402;
       for (k=0 ; k<N_MTW ; ++k) {
         r = 509845221 * r + 3;
         s *= s + 1;
         y_MTW[k] = s + (r >> 10);
       }
    }
    for (k=0 ; k<N_MTW-M_MTW ; ++k)
       y_MTW[k] = y_MTW[k+M_MTW] ^ (y_MTW[k] >> 1) ^ A_MTW[y_MTW[k] & 1];
    for (; k<N_MTW ; ++k)
       y_MTW[k] = y_MTW[k+(M_MTW-N_MTW)] ^ (y_MTW[k] >> 1) ^ A_MTW[y_MTW[k] & 1];
    i_MTW = 0;
  }

  e = y_MTW[i_MTW++];
  e ^= (e << 7)  & 0x2b5b2500;
  e ^= (e << 15) & 0xdb8b0000;
  e ^= (e >> 16);
  return e;
}


task main() {
  long rd;
  rd = Mrand();
  printf1(0,48, "%12d", rd);
  rd = Mrand();
  printf1(0,40, "%12d", rd);
  rd = Mrand();
  printf1(0,32, "%12d", rd);
  rd = Mrand();
  printf1(0,24, "%12d", rd);
  rd = Mrand();
  printf1(0,16, "%12d", rd);
  
  printf1(0,8, "%s", "test: 0x8ebfd028");
  printf1(0,0, "%12d", 0x8ebfd028);
  
  while(1);
}

I would try to change some of the constants into small ones (like e.g. 0x2b5b2500 into 0x2b5b25) but I'm afraid to effect the calculating seriously doing this.
What should I try?
e.g. converting all returned outputs e to abs(e)?

[spillerrec]

You use "%12d" which prints a signed decimal integer. So if you change this to "%12u" which formats a unsigned decimal integer it shows correctly. FormatNum() most likely uses a signed long for %d, so when you passes it a unsigned long it overflows.

[HaWe]

thank you!
I formerly used NumOut which gave the same display output as printf formatted by "%12d".

But now with "%12u" it shows correctly only positive numbers, so it was only a display output mistake.
thx again!

Now I'll only still have to implement a srand() function for the Mersenne Twister :P

[HaWe]

resolved!
Mersenne Twister is working with srand ! :)
(edit: improved)
http://www.mindstormsforum.de/viewtopic.php?f=70&t=6656

[afanofosc]

What remains for me a complete mystery is why on earth you would need a working Mersenne Twister PRNG working on your NXT. rand() works just fine for anything I can imagine you might need a random number for with an NXT program.

John Hansen

[HaWe]

well - the whole LIFE is a mystery ;)