Random Generator

[Antariy]

   The results were not what I expected.  It seems too sensitive
to variation?  Does anyone else have this coded up to compare
against?  Suggestions for another set of data to test?

What you are expected?

Michael, which version of Diehard do you used for testing of Axrand some days ago? The output is very different from output of C-port, in format of the tables, and in results (many results not shown anyway - FPU errors occurs). Program tested on different files (even not random), with different sizes.



Alex

[MichaelW]

I used the diehard.exe from the archive here (this is the Windows Software (732 Kb) link on this page):

http://www.stat.fsu.edu/pub/diehard/diehard.zip

The author admitted that the C source is a mess, having been translated from old Fortran code, so I decided not to try building it, and now it looks like I made the right decision  :bg

[Antariy]

The author admitted that the C source is a mess, having been translated from old Fortran code, so I decided not to try building it.

That is been a bit hm-m-m-m... tricky to build it, really strange port. You are decided rightly, but I'm does not know this info at that time  :bg

Thank you for link to the program!



Alex

[MichaelW]

This code is supposed to determine the period of the generated sequence:

Code Select Expand


;=========================================================================
    include \masm32\include\masm32rt.inc
;=========================================================================
    .data
        count   dq 0
        sysTime dq 0
        buffer  dd 1000 dup(0)
        hTimer  dd 0
        hThread dd 0
    .code
;=========================================================================

option prologue:none
option epilogue:none
align 16
Axrand proc STDCALL dwRange:DWORD
mov eax,Initial
mul dword ptr [esp+4]
mov eax,edx
mov edx,Initial
;xor edx,dword ptr [esp] ; for making results clearness, I have remove this, due to this line is compile-time dependent.
imul edx,12347
add edx,17
bswap edx
mov Initial,edx
ret 4
.data
align 4
Initial dd "RAND"
.code
Axrand endp
OPTION PROLOGUE:PrologueDef
OPTION EPILOGUE:EpilogueDef

;=========================================================================

ThreadProc proc lpParameter:DWORD
  @@:
    invoke WaitForSingleObject, hTimer, INFINITE
    loc 0, 0
    invoke crt_printf, cfm$("%I64d\n"), count
    jmp @B
ThreadProc endp

;=========================================================================
start:
;=========================================================================

    ;-------------------------------------------------------------------
    ; To avoid slowing down the L1 loop code, monitor the running count
    ; from a separate thread that runs only once every 2 seconds.
    ;-------------------------------------------------------------------

    invoke CreateWaitableTimer, 0, 0, 0
    mov hTimer, eax
    invoke GetSystemTimeAsFileTime, ADDR sysTime
    invoke SetWaitableTimer, hTimer, ADDR sysTime, 2000, 0, 0, 0
    invoke CreateThread, 0, 0, ThreadProc, 0, 0, 0

    mov esi, OFFSET buffer

    xor ebx, ebx
    .WHILE ebx < 1000
        invoke Axrand, -1
        mov [esi+ebx*4], eax
        add DWORD PTR count, 1
        adc DWORD PTR count+4, 0
        inc ebx
    .ENDW
  L1:
    invoke Axrand, -1
    add DWORD PTR count, 1
    adc DWORD PTR count+4, 0
    cmp [esi], eax
    jne L1
    mov ebx, 999
    xor edi, edi
  L2:
    inc edi
    invoke Axrand, -1
    cmp [esi+edi*4], eax
    jne L1
    dec ebx
    jnz L2

    inkey "Press any key to exit..."
    exit
;=========================================================================
end start


For Axrand as currently coded I get a period of 4,138,934,403. The period seems to vary a lot depending on the value of the constants in the imul and add instructions. For example, if I change the 12347 to 12346, then I get a very long period. I never reached the end of it, but the count was around 438,000,000,000 when I stopped it after the app had run for ~5 hours on my 500 MHz P3. If I change it to 12345 then I get a period of 1,937,267,874. If I restore the 12347 and change the 17 to 18, I get a period of 1,299,107,688. I didn't test the effect of these changes on the randomness of the generated sequence, but I think it might be worth trying to find other constants that will produce a good random sequence with a longer period.

[Antariy]

For Axrand as currently coded I get a period of 4,138,934,403.

I guess, period can and must repeats for nearly range of DWORD, or not? After generation of allmost all possible DWORDs, generator just impossible to not-generate the same thing. Much nearl the "end" - high value for range - the more probably can be generated previous DWORD. If the same dword is not generated after very big time (much bigger than DWORD's range) - that is not says about fact that generator generate values from other part of range, and probably - very repeatedly?



Alex

[jj2007]

Results for a shorter and faster variant:

Code Select Expand

Test for #0 byte
Entropy = 7.999208 bits per byte.
would exceed this value 25.00 percent of the times.
Serial correlation coefficient is 0.001851 (totally uncorrelated = 0.0).
Test for #1 byte
Entropy = 7.999241 bits per byte.
would exceed this value 50.00 percent of the times.
Serial correlation coefficient is -0.000120 (totally uncorrelated = 0.0).
Test for #2 byte
Entropy = 7.999224 bits per byte.
would exceed this value 50.00 percent of the times.
Serial correlation coefficient is -0.000343 (totally uncorrelated = 0.0).
Test for #3 byte
Entropy = 7.999208 bits per byte.
would exceed this value 25.00 percent of the times.
Serial correlation coefficient is 0.002037 (totally uncorrelated = 0.0).
Test for full DWORD
Entropy = 7.999803 bits per byte.
would exceed this value 25.00 percent of the times.
Serial correlation coefficient is 0.003151 (totally uncorrelated = 0.0).


Code Select Expand

Axrand3 proc STDCALL dwRange:DWORD
mov eax, Initial ; get the seed
imul eax, 127 ; randomise
add eax, 127
bswap eax ; we need the high order bits
mov Initial, eax ; save for next round
mul dword ptr [esp+4] ; multiply Initial with range
mov eax, edx ; return random number
ret 4 ; could also be returned in edx
Axrand3 endp


[Antariy]

Code Select Expand

Axrand3 proc STDCALL dwRange:DWORD
.......
mov eax, edx ; return random number
ret 4 ; could also be returned in edx
Axrand3 endp


xchg eax,edx would be smaller :P

:bg



Alex

[Antariy]

Code Select Expand


               bswap eax ; we need the high order bits


I used BSWAP not for fact of getting some "bits" (if DWORD have bad high bits - this is not make it good contrary to DWORD with bad low bits). I use this due to I have used very small step with addition and multiply, so, I used BSWAP as shuffling. Just remove BSWAP from generator...



Alex

[jj2007]

xchg eax,edx would be smaller :P

:bg

Yes, but it's a cycle slower :wink

The odd thing is when you drop the mov eax, edx, i.e. you simply use edx as return value, it's even slower, at least on my machine ::)

What about this pair:

Code Select Expand

 imul eax, -127 ; randomise
 add eax, -128


Code Select Expand

Axrand3 proc STDCALL dwRange:DWORD
mov eax, Initial ; get the seed
imul eax, -127 ; randomise
add eax, -128
bswap eax ; we need the high order bits
mov Initial, eax ; save for next round
mul dword ptr [esp+4] ; multiply Initial with range
mov eax, edx ; return random number
ret 4 ; could also be returned in edx
Axrand3 endp

Test for full DWORD
Entropy = 7.999845 bits per byte.
would exceed this value 95.00 percent of the times.

[Antariy]

when I stopped it after the app had run for ~5 hours on my 500 MHz P3.
..........
but I think it might be worth trying to find other constants that will produce a good random sequence with a longer period.

You did great thing, but probably finding of the best constants will require too long time to do.



Alex

[dedndave]

Yes, but it's a cycle slower

not so sure about that   :P

[Antariy]

Yes, but it's a cycle slower :wink

Test for full DWORD
Entropy = 7.999845 bits per byte.
would exceed this value 95.00 percent of the times.

I not say *faster*, I say - smaller  :bg
I agree that it can (and probably - must) be slower, because must use temporary place at least, or delays.

95% is bad value, as sayed in "help" for ENT, and as Steve said.



Alex

[jj2007]

95% is bad value, as sayed in "help" for ENT, and as Steve said.

ent.html: If the percentage is greater than 99% or less than 1%, the sequence is almost certainly not random. If the percentage is between 99% and 95% or between 1% and 5%, the sequence is suspect. Percentages between 90% and 95% and 5% and 10% indicate the sequence is "almost suspect"

So it is "almost suspect" but apparently still a lot better than the standard UNIX rand() function. Besides, by choosing e.g. Ciao instead of RAND for Initial, you can push all values into the green zone.

Let's not forget these are all pseudo-random generators... put the same initial value, and you will always get the same identical sequence :wink

[Antariy]

So it is "almost suspect" but apparently still a lot better than the standard UNIX rand() function. Besides, by choosing e.g. Ciao instead of RAND for Initial, you can push all values into the green zone.

Let's not forget these are all pseudo-random generators... put the same initial value, and you will always get the same identical sequence :wink

I wait your answer a long time  :bg
Well, change the Initial to other value with using of -127/-128 constants, and which is the results?

Note (again): the key is the BSWAP, not other things. Not for getting other bits - for *shuffling*.



Alex

[Antariy]

by choosing e.g. Ciao

You can use the Пока и Хайр, too  :bg



Alex