Random Generator

[Antariy]

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

Code:

.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:

Code:

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 


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"   



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 

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.

Code:

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]

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).

Code:

.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:

Code:

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:

Code:

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.

[jj2007]

Perfect! I attach your new version, Alex.

Code:

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]

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 



Alex

[Antariy]

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:

Code:

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]

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. 



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]

A 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 ?