News:

MASM32 SDK Description, downloads and other helpful links
MASM32.com New Forum Link
masmforum WebSite

Random Generator

Started by Neil, June 17, 2009, 12:44:13 PM

Previous topic - Next topic

Antariy

Well, this is my random numeric generator, which is not very fast, and not very big:  :P


.data
Initial dd "RAND"
.code
option prologue:none
option epilogue:none
Axrand proc STDCALL dwRange:DWORD

xor edx,edx

mov eax,Initial
mov ecx,eax
div dword ptr [esp+4]
push edx
mov eax,ecx
xor eax,dword ptr [esp+4]  ; just one more seed
imul eax,12347
add eax,17
bswap eax

mov Initial,eax
pop eax
ret 4
Axrand endp
OPTION PROLOGUE:PrologueDef
OPTION EPILOGUE:EpilogueDef


Of course, this is not "great thing", but with using of ENT.EXE, I got these results of generation of 200,000 random numbers with using of DWORD range in all calls:


Entropy = 7.999750 bits per byte.

Optimum compression would reduce the size
of this 800000 byte file by 0 percent.

Chi square distribution for 800000 samples is 277.21, and randomly
would exceed this value 25.00 percent of the times.

Arithmetic mean value of data bytes is 127.6224 (127.5 = random).
Monte Carlo value for Pi is 3.140137850 (error 0.05 percent).
Serial correlation coefficient is -0.001622 (totally uncorrelated = 0.0).


With -b switch
Entropy = 1.000000 bits per bit.

Optimum compression would reduce the size
of this 6400000 bit file by 0 percent.

Chi square distribution for 6400000 samples is 2.16, and randomly
would exceed this value 25.00 percent of the times.

Arithmetic mean value of data bits is 0.5003 (0.5 = random).
Monte Carlo value for Pi is 3.140137850 (error 0.05 percent).
Serial correlation coefficient is 0.000450 (totally uncorrelated = 0.0).



So, have look at results - they not so bad  :bg


Hutch, I'm allow using of this algo in any case as you want.
But using and "optimization" of this algo is strictly forbidden for hater of "asian lamers"   :green2



Alex

Antariy

P.S. Code size is 40 bytes.
Initial seed at programmers responsibility. When I made test in post above, I don't made initial seed at all. And this is not make algo worst  :P

Why used DIV, not "reversed MUL"? Well, couple years ago, I rewrite this algo from ASM to C, and I been wanted to use only language constructions. So, modulo of division is one from that. Initially algo been slightly different.



Alex

jj2007

Excellent, Alex! The div is slow, but I don't see any alternative. Have a look at the variant, it saves ecx.

Intel(R) Celeron(R) M CPU        420  @ 1.60GHz (SSE3)
32      cycles for Axrand
30      cycles for Axrand2

31      cycles for Axrand
30      cycles for Axrand2

40       bytes for Axrand
38       bytes for Axrand2

Antariy

Quote from: jj2007 on October 24, 2010, 01:30:26 AM
Excellent, Alex! The div is slow, but I don't see any alternative. Have a look at the variant, it saves ecx.

If change DIV  to MUL, the algorithm almost the same - HIGH DWORD of resulting QWORD in EDX would contain number between 0 and Range-1. What is needed.



Alex

Antariy

There is slightly optimized version, which is used MUL instead DIV, 2-3 times faster than previous (but not portable to HLL).


.data
Initial dd "RAND"
.code
option prologue:none
option epilogue:none
Axrand proc STDCALL dwRange:DWORD
mov eax,Initial
mul dword ptr [esp+4]
mov eax,edx
mov edx,Initial
xor edx,dword ptr [esp]
imul edx,12347
add edx,17
bswap edx
mov Initial,edx
ret 4
Axrand endp
OPTION PROLOGUE:PrologueDef
OPTION EPILOGUE:EpilogueDef


There is test of 200,000 randomly generated DWORDs in file, with ENT.EXE:

Entropy = 7.999761 bits per byte.

Optimum compression would reduce the size
of this 800000 byte file by 0 percent.

Chi square distribution for 800000 samples is 264.80, and randomly
would exceed this value 50.00 percent of the times.

Arithmetic mean value of data bytes is 127.6013 (127.5 = random).
Monte Carlo value for Pi is 3.141307853 (error 0.01 percent).
Serial correlation coefficient is -0.001857 (totally uncorrelated = 0.0).


With -b switch:
Entropy = 1.000000 bits per bit.

Optimum compression would reduce the size
of this 6400000 bit file by 0 percent.

Chi square distribution for 6400000 samples is 2.58, and randomly
would exceed this value 25.00 percent of the times.

Arithmetic mean value of data bits is 0.5003 (0.5 = random).
Monte Carlo value for Pi is 3.141307853 (error 0.01 percent).
Serial correlation coefficient is 0.000411 (totally uncorrelated = 0.0).


EDITED: In case of randomness, these results is slightly better than in DIV version.

Test by clocks:

Intel(R) Celeron(R) CPU 2.13GHz (SSE3)
16      cycles for Axrand
47      cycles for Axrand2

16      cycles for Axrand
46      cycles for Axrand2

40       bytes for Axrand
38       bytes for Axrand2



EDITED: Axrand - is new proc, with using of MUL; Axrand2 - is old proc, changed by Jochen to save ECX.

New proc with using MUL also saves an ECX.



Alex

MichaelW

Alex,

At 10 cycles running on a P3, your latest version is the fastest generator (of apparently good random numbers) that I have tested. The attachment contains the results for George Marsaglia's Diehard tests, available here.

eschew obfuscation

jj2007

Perfect! I attach your new version, Alex.

Intel(R) Celeron(R) M CPU        420  @ 1.60GHz (SSE3)
9       cycles for Axrand
30      cycles for Axrand2


brethren

alex, did you implement this prng yourself or is it from an existing algorithm?

Antariy

Quote from: brethren on October 25, 2010, 08:55:41 PM
alex, did you implement this prng yourself or is it from an existing algorithm?

I have implemented this algo myself. Of course, I cannot know - maybe someone on other side of Earth implement this algo, too.
To be honest, I have implemented this algo much before I have good connection to the Internet, and at that days I don't made search for existence of this algo - I just have no time for that.

Hopefully, this is my own, copyrighted algo  :bg



Alex

Antariy

Quote from: MichaelW on October 25, 2010, 07:38:17 PM
At 10 cycles running on a P3, your latest version is the fastest generator (of apparently good random numbers) that I have tested. The attachment contains the results for George Marsaglia's Diehard tests, available here.

Thanks, Michael !

Thanks again - I have downloaded sources of pointed program, too.


Thanks Jochen!

There is a timings for the last your archive posted:

Intel(R) Celeron(R) CPU 2.13GHz (SSE3)
16      cycles for Axrand
47      cycles for Axrand2

40       bytes for Axrand
38       bytes for Axrand2




Alex

brethren

alex, would you mind if i used axrand in my own library?

Antariy

Quote from: brethren on October 26, 2010, 01:15:08 PM
alex, would you mind if i used axrand in my own library?

Which library do you made? Can I know some details? Just curious.

Of course, you can use it in good project, if you are write about copyright of it somewhere.  :bg



Alex

brethren

nothing special, just my own library of optimized procedures that i use for cross-platform stuff:)

FORTRANS

Hi,

   Just as a comparison, here are the ENT results from a
simple 32-bit Linear Congruential "Random" number Generator.
Partly initialized using the current time.  First one million bytes
using the high byte from the DWORD random number.  A
fairly good cheap pseudorandom value.  Next a million bytes
using the low byte.  A known bad sequence as it repeats
every 256 values.

Regards,

Steve N.


One Million high bytes from DWORD (LCG) Linear Congruential "Random"
number Generator derived from Knuth/Numerical Recipies.

  ENT.EXE results.

Entropy = 7.999825 bits per byte.

Optimum compression would reduce the size
of this 1000000 byte file by 0 percent.

Chi square distribution for 1000000 samples is 242.07, and randomly
would exceed this value 50.00 percent of the times.

Arithmetic mean value of data bytes is 127.5479 (127.5 = random).
Monte Carlo value for Pi is 3.143268573 (error 0.05 percent).
Serial correlation coefficient is -0.000500 (totally uncorrelated = 0.0).


One Million low bytes from DWORD LCG Linear Congruential "Random"
number Generator derived from Knuth/Numerical Recipies.  (Known
poor to bad.)

  ENT.EXE results.

Entropy = 8.000000 bits per byte.

Optimum compression would reduce the size
of this 1000000 byte file by 0 percent.

Chi square distribution for 1000000 samples is 0.01, and randomly
would exceed this value 99.99 percent of the times.

Arithmetic mean value of data bytes is 127.4999 (127.5 = random).
Monte Carlo value for Pi is 3.218724875 (error 2.46 percent).
Serial correlation coefficient is -0.049491 (totally uncorrelated = 0.0).

dedndave

QuoteA known bad sequence as it repeats every 256 values.

that can depend on the constants used, no ?
what multiplier and addend did you use for the test routine ?