[Plugin] [REL] MerRandom v2.0 - Mersenne Twister Randoms
#1

MerRandom version 2.1 - Mersenne Twister Randoms for Pawn/SA:MP

Created by Cyber_Punk - Copyright 2009-2010

Special Thanks to Tannz0rz

Release notes: Thanks Yom for pointing out how shitty the first version really was.

v.2.1
Thanks to Kye's MapAndreas I was able to pass a true float value back to Pawn, MRandFloatRange now needs a variable passed to store the returned value. See this post for an example: http://forum.sa-mp.com/showthread.ph...843#post852843


v.2.0

This uses:
Mersenne Twister pseudo random number generator in assembly language By Agner Fog. © 2008 - 2010.
Apart of his randoma library.
http://www.agner.org/random/
GNU General Public License.
Version 2.01. 2010-08-03.

v.1.5 (not released was made hours before 2.0)

fixed extremely slow speeds by only init'd the MTrand class once on plugin load. (noob mistake lol)
Note: Even with this fix dispite being much much faster it still was slower then pawn by at least 3x.

Based on code by Makoto Matsumoto, Takuji Nishimura, and Shawn Cokus
Mersenne Twister Random Number Generator
The Mersenne Twister is an algorithm for generating random numbers. It was designed with consideration of the flaws in various other generators. It has an incredibly long period, 219937-1 (more than 106001), before its sequence of numbers will repeat. And it has 623 dimensions of equidistribution, meaning that all sequences up to 623 numbers long are equally probable. The generator is also fast; it avoids multiplication and division, and it benefits from caches and pipelines. See the inventors' page or Wikipedia article for more details.

__________________________________________________ ______________________________

native MRandom(max); // Get an integer in the range 0 to n (for n < 2^32-1)
native MRandRange(min, max); // Get an integer in a specified range
native MRandFloatRange(Float:min, Float:max, &Float:result); // Get a float in a specified range *return it to a Float variable... This function has been updated in v2.1
__________________________________________________ ________________________________

To Install:

Goto Samp Server folder and copy the respective files into the proper folder locations.

FOR WINDOWS:
In server config add merrandom to the line plugins (if you do not have this line you need to create it )

FOR LINUX:
In server config add merrandom.so(compiled on debian) to the line plugins (if you do not have this line you need to create it )

For a speed test vs. pawn load up rand_test in the gamemode folder, code from yom's post :P


DOWNLOAD:
http://www.sendspace.com/file/z90mqn


Special Note: If you are going to compile this yourself on Linux you have nothing to worry about your ready to go, BUT if you have windows, depending on your compiler you may have to switch library files in the makefile.

Compiler

MS C++ unmanaged, Intel, Gnu - randomacof32.lib (Default file no need to change....)

Borland C++, Digital Mars, Watcom - randomaomf32.lib
(remove randomacof32.lib from makefile.win32 and replace with randomaomf32.lib)



Happy randoming...
(New speed test results on last page)
Reply
#2

Well done, indeed PAWN's random() uses pretty bad LCG values. This one should get job done good.
Good job
Reply
#3

Quote:
Originally Posted by JoeBullet
Well done, indeed PAWN's random() uses pretty bad LCG values. This one should get job done good.
Good job
Thanks, I noticed not only a better random but some decent speed on getting a return.
Reply
#4

Enzo's the man. Nice work mon ami.
Reply
#5

Quote:
Originally Posted by cyber_punk
native MRandom(max); // Get an integer in the range 0 to n (for n < 2^32)
You mean 2^31 − 1 (2147483647).

Anyways, not bad i guess.
Reply
#6

Seem to be a lot of warnings and at the end fails to compile under linux.
Reply
#7

Quote:
Originally Posted by potato
Seem to be a lot of warnings and at the end fails to compile under linux.
Hm, I don't think there is anything in my code to stop a compile on linux. (sucks I don't have it to test) But I used the helloworld example and modified it. I checked the makefile to see if there was something I should have changed and removed.


Try removing this line from the makefile and let me know if it compiles please. If not I might have to install a linux distro and see whats going on.
Код:
	$(GPP) $(COMPILE_FLAGS) ../PAWN/*.cpp
That line is for the pawn invoke code, which I don't use in this project.

[Edit] Actually attached is a makefile with that line removed, please let me know if it compiles.
Reply
#8

I already tried that, but these are the warnings:


Код:
gcc -c -O3 -w -DLINUX -I../SDK/amx/ ../SDK/amx/*.c
g++ -c -O3 -w -DLINUX -I../SDK/amx/ ../SDK/*.cpp
g++ -c -O3 -w -DLINUX -I../SDK/amx/ *.cpp
g++ -O2 -fshort-wchar -shared -o "merrandom.so" *.o
collect2: ld terminated with signal 11 [Segmentation fault]
merrandom.o: In function `Supports':
merrandom.cpp:(.text+0x0): multiple definition of `Supports'
helloworld.o:helloworld.cpp:(.text+0x0): first defined here
merrandom.o: In function `Load':
merrandom.cpp:(.text+0x10): multiple definition of `Load'
helloworld.o:helloworld.cpp:(.text+0x10): first defined here
merrandom.o:(.bss+0x0): multiple definition of `logprintf'
helloworld.o:(.bss+0x0): first defined here
/usr/lib/gcc/i486-pc-linux-gnu/4.2.4/../../../../i486-pc-linux-gnu/bin/ld: Warning: size of symbol `logprintf' changed from 8 in helloworld.o to 4 in merrandom.o
merrandom.o: In function `Unload':
merrandom.cpp:(.text+0x40): multiple definition of `Unload'
helloworld.o:helloworld.cpp:(.text+0x50): first defined here
merrandom.o: In function `AmxUnload':
merrandom.cpp:(.text+0x60): multiple definition of `AmxUnload'
helloworld.o:helloworld.cpp:(.text+0x70): first defined here
merrandom.o: In function `AmxLoad':
merrandom.cpp:(.text+0xd0): multiple definition of `AmxLoad'
helloworld.o:helloworld.cpp:(.text+0x190): first defined here
merrandom.o:(.bss+0x4): multiple definition of `ppPluginData'
helloworld.o:(.bss+0x8): first defined here
/usr/lib/gcc/i486-pc-linux-gnu/4.2.4/../../../../i486-pc-linux-gnu/bin/ld: Warning: size of symbol `ppPluginData' changed from 8 in helloworld.o to 4 in merrandom.o
/usr/lib/gcc/i486-pc-linux-gnu/4.2.4/../../../../i486-pc-linux-gnu/bin/ld: i386:x86-64 architecture of input file `helloworld.o' is incompatible with i386 output
/usr/lib/gcc/i486-pc-linux-gnu/4.2.4/../../../../i486-pc-linux-gnu/bin/ld: i386:x86-64 architecture of input file `invoke.o' is incompatible with i386 output
make: *** [all] Error 1
Reply
#9

Quote:
Originally Posted by cyber_punk
I noticed a hell of a speed increase to the responses from the randoms
Sorry but have you actually profiled it?

Because I've tested and was very surprised... Results, from my laptop, for 500000 calls:
Код:
random
 -> Average time per call :    68 ns
 -> Total execution time :    34 ms
 -> Calls per second   : 14705883 calls

MRandom
 -> Average time per call :  51258 ns
 -> Total execution time :  25629 ms
 -> Calls per second   :  19509 calls
(took the best 2 results)

My profiling method:
pawn Код:
#define BENCH_INIT(%1); new BT1=GetTickCount(),BT2,BI1,BI2=%1;

#define BENCH(%1(%2)); \
{\
  for(BI1=0;BI1<BI2;BI1++)\
    %1(%2);\
\
  BT2=GetTickCount();\
  BT1=BT2-BT1;\
\
  printf("\n"#%1"\n -> Average time per call : %8.f ns\n -> Total execution time : %8d ms\n -> Calls per second   : %8.f calls",\
  (float(BT1)/BI2)*1000000,BT1,(float(BI2)/BT1)*1000);\
\
  BT1=BT2;\
}

main()
{
  BENCH_INIT(500000);

  BENCH(random(101));
  BENCH(random(101));
  BENCH(MRandom(100));
  BENCH(MRandom(100));
  BENCH(random(101));
  BENCH(random(101));
  BENCH(MRandom(100));
  BENCH(MRandom(100));
}
Just being curious about how you noticed a speed increase because as you can see, random() is about 750x faster
Reply
#10

Quote:
Originally Posted by 0rb
Quote:
Originally Posted by cyber_punk
I noticed a hell of a speed increase to the responses from the randoms
Sorry but have you actually profiled it?

Because I've tested and was very surprised... Results, from my laptop, for 500000 calls:
Код:
random
 -> Average time per call :    68 ns
 -> Total execution time :    34 ms
 -> Calls per second   : 14705883 calls

MRandom
 -> Average time per call :  51258 ns
 -> Total execution time :  25629 ms
 -> Calls per second   :  19509 calls
(took the best 2 results)

My profiling method:
pawn Код:
#define BENCH_INIT(%1); new BT1=GetTickCount(),BT2,BI1,BI2=%1;

#define BENCH(%1(%2)); \
{\
  for(BI1=0;BI1<BI2;BI1++)\
    %1(%2);\
\
  BT2=GetTickCount();\
  BT1=BT2-BT1;\
\
  printf("\n"#%1"\n -> Average time per call : %8.f ns\n -> Total execution time : %8d ms\n -> Calls per second   : %8.f calls",\
  (float(BT1)/BI2)*1000000,BT1,(float(BI2)/BT1)*1000);\
\
  BT1=BT2;\
}

main()
{
  BENCH_INIT(500000);

  BENCH(random(101));
  BENCH(random(101));
  BENCH(MRandom(100));
  BENCH(MRandom(100));
  BENCH(random(101));
  BENCH(random(101));
  BENCH(MRandom(100));
  BENCH(MRandom(100));
}
Just being curious about how you noticed a speed increase because as you can see, random() is about 750x faster
In this case, speed honestly shouldn't be a reason as to why you wouldn't want to use this. The randoms with Mersenne are, pardon my lack of words, more "random", while the pawn-generated version is a tad bit sad.
Reply
#11

Quote:
Originally Posted by Tannz0rz
Quote:
Originally Posted by 0rb
Quote:
Originally Posted by cyber_punk
I noticed a hell of a speed increase to the responses from the randoms
Sorry but have you actually profiled it?

Because I've tested and was very surprised... Results, from my laptop, for 500000 calls:
Code:
random
 -> Average time per call :    68 ns
 -> Total execution time :    34 ms
 -> Calls per second   : 14705883 calls

MRandom
 -> Average time per call :  51258 ns
 -> Total execution time :  25629 ms
 -> Calls per second   :  19509 calls
(took the best 2 results)

My profiling method:
pawn Code:
#define BENCH_INIT(%1); new BT1=GetTickCount(),BT2,BI1,BI2=%1;

#define BENCH(%1(%2)); \
{\
  for(BI1=0;BI1<BI2;BI1++)\
    %1(%2);\
\
  BT2=GetTickCount();\
  BT1=BT2-BT1;\
\
  printf("\n"#%1"\n -> Average time per call : %8.f ns\n -> Total execution time : %8d ms\n -> Calls per second   : %8.f calls",\
  (float(BT1)/BI2)*1000000,BT1,(float(BI2)/BT1)*1000);\
\
  BT1=BT2;\
}

main()
{
  BENCH_INIT(500000);

  BENCH(random(101));
  BENCH(random(101));
  BENCH(MRandom(100));
  BENCH(MRandom(100));
  BENCH(random(101));
  BENCH(random(101));
  BENCH(MRandom(100));
  BENCH(MRandom(100));
}
Just being curious about how you noticed a speed increase because as you can see, random() is about 750x faster
In this case, speed honestly shouldn't be a reason as to why you wouldn't want to use this. The randoms with Mersenne are, pardon my lack of words, more "random", while the pawn-generated version is a tad bit sad.
Upside down.
Reply
#12

Quote:
Originally Posted by MenaceX^
Upside down.
And you know this from what experience? Give it a test drive yourself and see the results.
Reply
#13

Quote:
Originally Posted by Tannz0rz
In this case, speed honestly shouldn't be a reason as to why you wouldn't want to use this. The randoms with Mersenne are, pardon my lack of words, more "random", while the pawn-generated version is a tad bit sad.
The real question is, is it REALLY worth using this plugin? I'm sorry if you take my posts as offensive, cyber_punk, but i like discussing this sort of things and i like testing/comparing things, and also giving proofs, not just saying. We are here to progress isn't it?

I did a small code to compare probabilities of each functions:
pawn Code:
#define TESTS  20  //How many times to reproduce the test
#define CALLS  3  //How many function calls
#define MAX   3  //Numbers from 0 to MAX (not included)

//Obviously..
#if CALLS < MAX
  #undef CALLS
  #define CALLS MAX
#endif
pawn Code:
new a[MAX][2], i, j;

public OnFilterScriptInit()
{
  for (i = 0; i < TESTS; i++)
  {
    for (j = 0; j < CALLS; j++)
    {
      a[ random(MAX)  ][0]++;
      a[ MRandom(MAX-1) ][1]++;
    }
    for (j = 0; j < MAX; j++)
    {
      printf("Probability of %4d -> random: %3.2f%% - MRandom: %3.2f%%",j, (a[j][0]/CALLS.0)*100,(a[j][1]/CALLS.0)*100);
      a[j][0] = 0;
      a[j][1] = 0;
    }
    print(" ");
  }
}
This gives those results:
Code:
Probability of  0 -> random: 33.33% - MRandom: 33.33%
Probability of  1 -> random:  0.00% - MRandom: 33.33%
Probability of  2 -> random: 66.66% - MRandom: 33.33%

Probability of  0 -> random:  0.00% - MRandom: 66.66%
Probability of  1 -> random: 100.00% - MRandom:  0.00%
Probability of  2 -> random:  0.00% - MRandom: 33.33%

Probability of  0 -> random: 100.00% - MRandom: 33.33%
Probability of  1 -> random:  0.00% - MRandom: 33.33%
Probability of  2 -> random:  0.00% - MRandom: 33.33%

Probability of  0 -> random: 33.33% - MRandom: 33.33%
Probability of  1 -> random: 33.33% - MRandom: 66.66%
Probability of  2 -> random: 33.33% - MRandom:  0.00%

Probability of  0 -> random: 33.33% - MRandom: 66.66%
Probability of  1 -> random:  0.00% - MRandom: 33.33%
Probability of  2 -> random: 66.66% - MRandom:  0.00%

Probability of  0 -> random:  0.00% - MRandom: 66.66%
Probability of  1 -> random: 33.33% - MRandom:  0.00%
Probability of  2 -> random: 66.66% - MRandom: 33.33%

Probability of  0 -> random: 66.66% - MRandom: 66.66%
Probability of  1 -> random:  0.00% - MRandom:  0.00%
Probability of  2 -> random: 33.33% - MRandom: 33.33%

Probability of  0 -> random:  0.00% - MRandom: 33.33%
Probability of  1 -> random: 33.33% - MRandom:  0.00%
Probability of  2 -> random: 66.66% - MRandom: 66.66%

Probability of  0 -> random: 33.33% - MRandom: 33.33%
Probability of  1 -> random: 33.33% - MRandom:  0.00%
Probability of  2 -> random: 33.33% - MRandom: 66.66%

Probability of  0 -> random:  0.00% - MRandom: 66.66%
Probability of  1 -> random: 66.66% - MRandom: 33.33%
Probability of  2 -> random: 33.33% - MRandom:  0.00%

Probability of  0 -> random:  0.00% - MRandom: 100.00%
Probability of  1 -> random: 66.66% - MRandom:  0.00%
Probability of  2 -> random: 33.33% - MRandom:  0.00%

Probability of  0 -> random: 66.66% - MRandom: 33.33%
Probability of  1 -> random:  0.00% - MRandom:  0.00%
Probability of  2 -> random: 33.33% - MRandom: 66.66%

Probability of  0 -> random: 33.33% - MRandom:  0.00%
Probability of  1 -> random: 33.33% - MRandom: 33.33%
Probability of  2 -> random: 33.33% - MRandom: 66.66%

Probability of  0 -> random: 66.66% - MRandom:  0.00%
Probability of  1 -> random: 33.33% - MRandom: 100.00%
Probability of  2 -> random:  0.00% - MRandom:  0.00%

Probability of  0 -> random: 33.33% - MRandom:  0.00%
Probability of  1 -> random: 33.33% - MRandom: 33.33%
Probability of  2 -> random: 33.33% - MRandom: 66.66%

Probability of  0 -> random: 100.00% - MRandom: 33.33%
Probability of  1 -> random:  0.00% - MRandom: 66.66%
Probability of  2 -> random:  0.00% - MRandom:  0.00%

Probability of  0 -> random: 66.66% - MRandom:  0.00%
Probability of  1 -> random:  0.00% - MRandom:  0.00%
Probability of  2 -> random: 33.33% - MRandom: 100.00%

Probability of  0 -> random: 33.33% - MRandom: 33.33%
Probability of  1 -> random: 33.33% - MRandom: 33.33%
Probability of  2 -> random: 33.33% - MRandom: 33.33%

Probability of  0 -> random: 66.66% - MRandom: 33.33%
Probability of  1 -> random:  0.00% - MRandom: 33.33%
Probability of  2 -> random: 33.33% - MRandom: 33.33%

Probability of  0 -> random:  0.00% - MRandom: 33.33%
Probability of  1 -> random: 66.66% - MRandom:  0.00%
Probability of  2 -> random: 33.33% - MRandom: 66.66%
As you can see, even for a random number between 0, 1, and 2, the random() function (which suck for small values, i agree) give pretty similar results compared to MRandom(). A perfect random generator should always give 33% for each of these tests, but i guess it's impossible. You could try increase MAX and see what happen: results are more and more similar as MAX is increased.

I agree that this MRandom() give sometimes more randomized numbers than random(), at least for small values, but for me it's really not worth using it.
Reply
#14

Been waiting for Y_Less' reply.
But why would you make a new random script while SA:MP developers had created one?
Reply
#15

I agree that only 3 calls was maybe not a good test case. Also i should have changed that word 'probability' with 'percentage' or something, because i realize it's confusing after re reading my post. Oh well, i was drunk anyway

Quote:
Originally Posted by MenaceX^
But why would you make a new random script while SA:MP developers had created one?
'They' haven't created it. The random function can be found in amxcore.c, if you ever downloaded the PAWN toolkit.
Reply
#16

Quote:
Originally Posted by MenaceX^
Been waiting for Y_Less' reply.
But why would you make a new random script while SA:MP developers had created one?
Because the native one is apparently not truly random apparently, which is what people are trying to figure out right now.

PHP has mt_rand too, which is apparently a better random function, which is described as:
' Many random number generators of older libcs have dubious or unknown characteristics and are slow. By default, PHP uses the libc random number generator with the rand() function. The mt_rand() function is a drop-in replacement for this. It uses a random number generator with known characteristics using the » Mersenne Twister, which will produce random numbers four times faster than what the average libc rand() provides. '

Reply
#17

Quote:
Originally Posted by 0rb
I agree that only 3 calls was maybe not a good test case. Also i should have changed that word 'probability' with 'percentage' or something, because i realize it's confusing after re reading my post. Oh well, i was drunk anyway

Quote:
Originally Posted by MenaceX^
But why would you make a new random script while SA:MP developers had created one?
'They' haven't created it. The random function can be found in amxcore.c, if you ever downloaded the PAWN toolkit.
Yeah it doesn't that matter for me, I meant that there's already existing one.
Reply
#18

Quote:
Originally Posted by MenaceX^
But why would you make a new random script while SA:MP developers had created one?
Because the old one SUCKS completely, I use random a lot in my script and it's often giving the same value n times in a row which is VERY frustrating at some point (like command that should tele you to random base but it's always moving you to the same one), I hope this one will be better...
Reply
#19

Thanks for the input and opinions.

The first post has been updated, I downloaded ubuntu(debian) and got it compiled properly. The makefile should be good for all linux releases. The .so is also included.


@ Orb - The speed results surprised me actually, seeing that the results when run in c++ the average time for call is about 60-70ns. My guess is there must be a bottleneck in the way the pawn vm and the plugin communicate.


Now to clear up how I made my speed assumption. My gm is random heavy, and one of these areas are when a player is team balanced they are chosen a random skin from and array and a spawn location (array also) using the method random(sizeof(array)) survivors array is a bit over 200. When you would /kill (which is just SpawnPlayer()) over and over again there would be a slight hiccup or noticeable lag. Most of the time you don't have to spam it to notice the delay. When I switched to MRandom and went back and spammed the command there was no delay or lag at all. As fast as I spammed as fast as I spawned. To me that's a return in speed. My theory is possibly that off loading the maths and such from the pawn vm cured the lag, but that's just an assumption.


What I know is a fact is that my car starting has not gone into a 15 no start loop. In fact the longest tries I have encountered is about 3 till vehicle start. Also in my testing of my new server patch where I utilize this plugin the checkpoints are not appearing Glen Park, Glen Park, Glen Park. Also there is the added benefit of a random float value, something pawn's random doesn't do.

I have since your posts Orb been looking into some other algorithms and found a few I like and want to try, so I am going to turn this project from a Mersenne Twister only plugin to a Multi-PRNG plugin. Each Method will just have its own set of functions so it will be easy to test and try them all and ultimately the choice of what random can be left to the scripter.


@DiDok - Let me know how it goes.


Thanks,
C-P
Reply
#20

It still doesn't seem to be compiling right:

Code:
gcc -c -O3 -w -DLINUX -I../SDK/amx/ ../SDK/amx/*.c
g++ -c -O3 -w -DLINUX -I../SDK/amx/ ../SDK/*.cpp
g++ -c -O3 -w -DLINUX -I../SDK/amx/ *.cpp
g++ -O2 -fshort-wchar -shared -o "./Release-Linux/merrandom.so" *.o
collect2: ld terminated with signal 11 [Segmentation fault]
merrandom.o: In function `Supports':
merrandom.cpp:(.text+0x0): multiple definition of `Supports'
helloworld.o:helloworld.cpp:(.text+0x0): first defined here
merrandom.o: In function `Load':
merrandom.cpp:(.text+0x10): multiple definition of `Load'
helloworld.o:helloworld.cpp:(.text+0x10): first defined here
merrandom.o:(.bss+0x0): multiple definition of `logprintf'
helloworld.o:(.bss+0x0): first defined here
/usr/lib/gcc/i486-pc-linux-gnu/4.2.4/../../../../i486-pc-linux-gnu/bin/ld: Warning: size of symbol `logprintf' changed from 8 in helloworld.o to 4 in merrandom.o
merrandom.o: In function `Unload':
merrandom.cpp:(.text+0x40): multiple definition of `Unload'
helloworld.o:helloworld.cpp:(.text+0x50): first defined here
merrandom.o: In function `AmxUnload':
merrandom.cpp:(.text+0x60): multiple definition of `AmxUnload'
helloworld.o:helloworld.cpp:(.text+0x70): first defined here
merrandom.o: In function `AmxLoad':
merrandom.cpp:(.text+0xd0): multiple definition of `AmxLoad'
helloworld.o:helloworld.cpp:(.text+0x190): first defined here
merrandom.o:(.bss+0x4): multiple definition of `ppPluginData'
helloworld.o:(.bss+0x8): first defined here
/usr/lib/gcc/i486-pc-linux-gnu/4.2.4/../../../../i486-pc-linux-gnu/bin/ld: Warning: size of symbol `ppPluginData' changed from 8 in helloworld.o to 4 in merrandom.o
/usr/lib/gcc/i486-pc-linux-gnu/4.2.4/../../../../i486-pc-linux-gnu/bin/ld: i386:x86-64 architecture of input file `helloworld.o' is incompatible with i386 output
/usr/lib/gcc/i486-pc-linux-gnu/4.2.4/../../../../i486-pc-linux-gnu/bin/ld: i386:x86-64 architecture of input file `invoke.o' is incompatible with i386 output
make: *** [all] Error 1
P.S. it's a Gentoo.
Reply


Forum Jump:


Users browsing this thread: 1 Guest(s)