Calling GetLocalTime on windows

[dedndave]

reading any time value, whether it is from the OS or via RDTSC will be much slower than a LCG random generator
and - you won't get random stuff   :P

perhaps the best thing to do is to play with a few different methods and look at the numbers that are generated

[pelmeen]

Hmm, well i will probably never reach the MasmBasic optimisation and i cant get around the API call, if im using time as my seed.

But i could do something that dedndave said.

I could maybe tell the program to seed on like.. every 30th call? That way the API would be called much rarer and cycles count would be dramatically lowered.

Or maybe i could only seed the program through the time only at the start of the program. After that i could use the last random as the seed. I guess that would improve optimization dramatically. Then, every time user starts the small app, its still going to be different numbers.. only 1/999 chance that they are exactly the same :D

Regarding dedndave last post. Why wont i get random stuff?
EDIT:
Yea, i just realized that when i use milliseconds as seed on every call, i actually only have 999 states for my random. So i MUST use the last random as my seed at some point.
EDIT2:
I thought about it for a while and i believe that giving random seed only at the start is the best course of action. And i should also use the big number, which i can get from jj2007 second posts code. Im going to work on it tonight when i get home.

[jj2007]

Hmm, well i will probably never reach the MasmBasic optimisation and i cant get around the API call, if im using time as my seed.

If you need a good "random" seed, use either rdtsc or GetTickCount - a very fast API call, it takes about 7 cycles.

I have run a few tests with ENT concerning MasmBasic Rand() and its C equivalent, crt_rand. Both tests are limited to WORD size, because the CRT algo yields a WORD only.

MasmBasic:
Test for #0 byte
Entropy = 7.999257 bits per byte.
would exceed this value 50.00 percent of the times. <<< very good
Serial correlation coefficient is -0.002635 (totally uncorrelated = 0.0).
Test for #1 byte
Entropy = 7.999249 bits per byte.
would exceed this value 50.00 percent of the times. <<< very good
Serial correlation coefficient is -0.003110 (totally uncorrelated = 0.0).

CRT rand:
Test for #0 byte
Entropy = 7.999358 bits per byte.
would exceed this value 90.00 percent of the times. <<< bad
Serial correlation coefficient is 0.000417 (totally uncorrelated = 0.0). <<< good
Test for #1 byte
Entropy = 6.999668 bits per byte. (range is 0...32767)
would exceed this value 0.01 percent of the times. <<< very bad *)
Serial correlation coefficient is -0.002919 (totally uncorrelated = 0.0).

Overall, the MasmBasic version looks a bit better. In addition, it runs in 11 cycles instead of 30 for the CRT version.

*)

Chi-square Test
    The chi-square test is the most commonly used test for the randomness of data...
Applying this test to the output of various pseudorandom sequence generators is interesting. The low-order 8 bits returned by the standard Unix rand() function, for example, yields:

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

While an improved generator [Park & Miller] reports:

    Chi square distribution for 500000 samples is 212.53, and randomly would exceed this value 97.53 percent of the times.

Thus, the standard Unix generator (or at least the low-order bytes it returns) is unacceptably non-random, while the improved generator is much better but still sufficiently non-random to cause concern for demanding applications. Contrast both of these software generators with the chi-square result of a genuine random sequence created by timing radioactive decay events.

    Chi square distribution for 500000 samples is 249.51, and randomly would exceed this value 40.98 percent of the times.

[dedndave]

in one implementation, i pulled a 6-bit number from the clock and forced it to be between 64 and 128
then i used that value as the count N
count N pulls from the LCG later, i use the clock to reseed the LCG and get a new N
as you said - reasonably fast, and the numbers are quite random

[pelmeen]

Ahh, thank you for all of your replies. Its too late today, i must work on it tomorrow or on saturday.

Also, i gotta mention. Im really impressed on the activity rate of this community.

[pelmeen]

Using your help and links and stuff you taught me, i have put together something like this:

Code Select Expand



PUBLIC getRandom, start
include \masm32\include\masm32rt.inc

getRandom proc C
   jz getRandomCalculate
   invoke GetTickCount
   
getRandomCalculate:   
   imul eax, 1103515245
   add eax, 12345
   xor edx, edx
   mov ebx, 65536
   idiv ebx
   xor edx, edx
   mov ebx, 32768
   idiv ebx
   mov eax, edx
   ret
getRandom endp

start: m2m ebx, 10
.Repeat
invoke getRandom
print str$(eax), 13, 10
invoke Sleep, 100
dec ebx
.Until Sign?
exit
end start


What do you think?

For the real program, i wont be using the start part. Im going to call this function from a program written in C

[qWord]

Seems not  very random.
You may like the following routine, which returns a BYTE:

Code Select Expand

badRandom256 proc uses esi edi
LOCAL qw:QWORD
    rdtsc
    and eax,0ffh
    push eax
    mov esi,eax
    xor edi,edi
    .while esi
        xor edi,rv(GetTickCount)
        dec esi
    .endw
    rdtsc
    pop edx
    mul edx
    xor eax,edi
    push eax
    invoke QueryPerformanceCounter,ADDR qw
    pop eax
    xor eax,DWORD ptr qw[0]
    and eax,0ffh
    ret
   
badRandom256 endp

[jj2007]

What do you think?

"Thinking" is not a good approach to judging the randomness of a pseudo random generator. Fourmilab developed ENT for that purpose.

[donkey]

For myself if I need a large random array I use a Mersenne twister, if I just need a one-shot in a program (ie I only need a small array and only once) I use the Crypto functions. They're slow but I only use them in cases where speed is not an issue:

Code Select Expand

FillRandom FRAME pBuffer, nBytes
LOCAL hCryptProv :%HANDLE

// Fill pBuffer with nBytes of random data
// Returns 0 if successful, -1 otherwise

invoke CryptAcquireContext,offset hCryptProv,NULL,NULL,PROV_RSA_FULL,CRYPT_VERIFYCONTEXT
test eax,eax
jz >>.ERRORCONTEXT

invoke CryptGenRandom, [hCryptProv],[nBytes],[pBuffer]
test eax,eax
jz >>.ERRORGEN

invoke CryptReleaseContext, [hCryptProv], NULL
xor eax,eax
ret

.ERRORGEN
invoke CryptReleaseContext, [hCryptProv], NULL

.ERRORCONTEXT
xor eax,eax
dec eax
RET

endf