Author
|
Topic: Random Generator (Read 99991 times)
|
Antariy
|
Well, this is my random numeric generator, which is not very fast, and not very big:  .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 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
|
|
|
Logged
|
|
|
|
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
|
|
|
Logged
|
|
|
|
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
|
|
|
Logged
|
|
|
|
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
|
|
|
Logged
|
|
|
|
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
|
|
|
Logged
|
|
|
|
MichaelW
Global Moderator
Member
    
Gender: 
Posts: 5161
|
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.
|
|
|
Logged
|
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
|
|
|
Logged
|
|
|
|
brethren
|
alex, did you implement this prng yourself or is it from an existing algorithm?
|
|
|
Logged
|
|
|
|
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
|
|
|
Logged
|
|
|
|
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: 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
|
|
|
Logged
|
|
|
|
brethren
|
alex, would you mind if i used axrand in my own library?
|
|
|
Logged
|
|
|
|
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
|
|
|
Logged
|
|
|
|
brethren
|
nothing special, just my own library of optimized procedures that i use for cross-platform stuff:)
|
|
|
Logged
|
|
|
|
FORTRANS
Member
    
Gender: 
Posts: 1147
Imagine
|
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).
|
|
|
Logged
|
|
|
|
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 ?
|
|
|
Logged
|
|
|
|
|
 |