The MASM Forum Archive 2004 to 2012
Welcome, Guest. Please login or register.
March 24, 2023, 01:39:30 PM

Login with username, password and session length
Search:     Advanced search
128553 Posts in 15254 Topics by 684 Members
Latest Member: mottt
* Home Help Search Login Register
+  The MASM Forum Archive 2004 to 2012
|-+  General Forums
| |-+  The Laboratory (Moderator: Mark_Larson)
| | |-+  Random Generator
« previous next »
Pages: 1 [2] 3 4 ... 11 Print
Author Topic: Random Generator  (Read 99991 times)
Antariy
Member
*****
Gender: Male
Posts: 1041


Re: Random Generator
« Reply #15 on: October 24, 2010, 12:14:01 AM »

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

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  BigGrin


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
Logged
Antariy
Member
*****
Gender: Male
Posts: 1041


Re: Random Generator
« Reply #16 on: October 24, 2010, 12:17:47 AM »

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  Tongue

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
Member
*****
Gender: Male
Posts: 6011



Re: Random Generator
« Reply #17 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.

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

* AxRand.zip (2.88 KB - downloaded 359 times.)
Logged

Antariy
Member
*****
Gender: Male
Posts: 1041


Re: Random Generator
« Reply #18 on: October 24, 2010, 09:38:51 PM »

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
Member
*****
Gender: Male
Posts: 1041


Re: Random Generator
« Reply #19 on: October 24, 2010, 10:01:01 PM »

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
Logged
MichaelW
Global Moderator
Member
*****
Gender: Male
Posts: 5161


Re: Random Generator
« Reply #20 on: October 25, 2010, 07:38:17 PM »

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.


* axrand_diehard.zip (12.86 KB - downloaded 376 times.)
Logged

eschew obfuscation
jj2007
Member
*****
Gender: Male
Posts: 6011



Re: Random Generator
« Reply #21 on: October 25, 2010, 08:01:22 PM »

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

* AxRand.zip (2.8 KB - downloaded 358 times.)
Logged

brethren
Member
*****
Posts: 172



Re: Random Generator
« Reply #22 on: October 25, 2010, 08:55:41 PM »

alex, did you implement this prng yourself or is it from an existing algorithm?
Logged
Antariy
Member
*****
Gender: Male
Posts: 1041


Re: Random Generator
« Reply #23 on: October 25, 2010, 09:33:07 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  BigGrin



Alex
Logged
Antariy
Member
*****
Gender: Male
Posts: 1041


Re: Random Generator
« Reply #24 on: October 25, 2010, 09:41:29 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:
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
Logged
brethren
Member
*****
Posts: 172



Re: Random Generator
« Reply #25 on: October 26, 2010, 01:15:08 PM »

alex, would you mind if i used axrand in my own library?
Logged
Antariy
Member
*****
Gender: Male
Posts: 1041


Re: Random Generator
« Reply #26 on: October 26, 2010, 09:56:36 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.  BigGrin



Alex
Logged
brethren
Member
*****
Posts: 172



Re: Random Generator
« Reply #27 on: October 27, 2010, 11:35:10 AM »

nothing special, just my own library of optimized procedures that i use for cross-platform stuff:)
Logged
FORTRANS
Member
*****
Gender: Male
Posts: 1147


Imagine


Re: Random Generator
« Reply #28 on: October 27, 2010, 01:29:23 PM »

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
Member
*****
Posts: 12523


Re: Random Generator
« Reply #29 on: October 27, 2010, 02:49:51 PM »

Quote
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
Pages: 1 [2] 3 4 ... 11 Print 
« previous next »
Jump to:  

Powered by MySQL Powered by PHP The MASM Forum Archive 2004 to 2012 | Powered by SMF 1.0.12.
© 2001-2005, Lewis Media. All Rights Reserved.
Valid XHTML 1.0! Valid CSS!