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 Range1. What is needed. Alex



Logged




Antariy

There is slightly optimized version, which is used MUL instead DIV, 23 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 crossplatform stuff:)



Logged




FORTRANS
Member
Gender:
Posts: 1147
Imagine

Hi,
Just as a comparison, here are the ENT results from a simple 32bit 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





