Possible replacement for nrandom

[lingo]

Abel,

Two rows less in your code (1-2 clocks less)
but I have with all reserve about   
1st jump -> if N > ffffffffh (less unlikely)  :wink

Code Select Expand


OPTION PROLOGUE:NONE
OPTION EPILOGUE:NONE
align 4
rand32 proc   base:DWORD
       mov    eax, 16807       
       mov    ecx, 80000001h
       mul    rand32_seed      ;edx:eax == a*seed == D:A
       add    edx, edx         ;edx = 2*D
       add    eax, edx         ;N = A + 2*D
       mov    edx, 0
       jnc    @F               ;if N > ffffffffh (less unlikely)
       add    eax, ecx
@@:    cmovns ecx, edx         ;if N > 7fffffffh (50:50)
       add    eax, ecx
       mov    rand32_seed, eax ; save new seed
       div    dword ptr [esp+4]; base
       mov    eax, edx
       ret    4
rand32 endp
OPTION PROLOGUE:PrologueDef
OPTION EPILOGUE:EpilogueDef
Regards,
Lingo

[ecube]

Anytime lingo posts is becomes a thread of epic proportions  :U

[Abel]

Lingo,
Thanks for the polish.  I'm picking up echoes off the bottom of the barrel.

The most obvious remaining weak point is the closing DIV.  I think the rules are to recreate the Park-Miller sequence as expeditiously as possible. 
Hutch may have some reservations about using .686 code in library functions.  What else should be returned apart from the Park-Miller sequence
is a moot point.  We've assumed integers modulo a given base.  Others may want floating points 0->1 or integers modulo 2^n.

DIV gets integers using the lowest bits of the Park-Miller seeds.  In another thread several years ago, Michael suggested replacing DIV with a MUL
which emphasizes the highest bits of the Park-Miller seeds and chi-square tests didn't turn up any problems.  This option reduces my cycle tallies
from 40-41 to 29-32.

Code Select Expand


OPTION PROLOGUE:NONE
OPTION EPILOGUE:NONE
align 4
rand32 proc base:DWORD
    mov eax, 16807              ;a = 7^5
    mul rand32_seed             ;edx:eax == a*seed == D:A
    mov ecx, 7fffffffh          ;ecx = m
    add edx, edx                ;edx = 2*D
    add eax,edx                 ;N = A + 2*D
    mov edx,0
    jnc @F                      ;if N > ffffffffh (less likely)
    sub eax,ecx                 ;  N = N-m
@@: cmovns  ecx,edx             ;if N > 7fffffffh (50:50)
    sub eax, ecx                ;  N = N-m
    mov rand32_seed, eax        ; save new seed
   
;Using LoBits
;    div dword ptr [esp+4]      ;base

;Using HiBits
    shl eax,1
    mul dword ptr [esp+4]       ;base

    mov eax, edx
    ret 4
rand32  endp

OPTION PROLOGUE:PrologueDef
OPTION EPILOGUE:EpilogueDef



RNG Plugin: Rand32-Hi.dll
Array Length:  1000000
Array Modulus:  256
Current Seed: 0x02016D88
                Array           Difference      Integrated      Seed   
Run 1           0.15352543      0.17302848      0.82842721      0x00000001     
Run 2           0.25338037      0.42654848      0.30013492      0x4926DB93     
Run 3           0.69406418      0.33732162      0.95430686      0x6BC734A8     
Run 4           0.24896364      0.85992266      0.04448574      0x43F74886     
Run 5           0.75102686      0.95050725      0.93853727      0x32C4F04F     
Run 6           0.25241672      0.51695021      0.62466855      0x70674CF8     
Run 7           0.88426325      0.89111771      0.98547929      0x4F3663CA     
Run 8           0.94895542      0.33389802      0.21863232      0x1ADA2BEF     
Run 9           0.66103225      0.51705909      0.71129295      0x4AAF4320     
Run 10          0.09923830      0.05070660      0.85115210      0x127E8BCE     
Run 11          0.99092664      0.11889222      0.03941943      0x69694A50     
Run 12          0.52057062      0.74912639      0.40157083      0x2E262867     
Run 13          0.92096010      0.94554446      0.01294125      0x1D2315AE     
Run 14          0.06210419      0.15717322      0.37764770      0x252C27AD     
Run 15          0.46503752      0.99448840      0.35831148      0x6C383ED7     
Run 16          0.04933810      0.45469887      0.21313750      0x22D0F0A3     
Run 17          0.93996576      0.99498513      0.48553769      0x02ED5997     
Run 18          0.96162106      0.51362063      0.00314153      0x1704DF49     
Run 19          0.99891330      0.92949402      0.93302415      0x65CD6E31     
Run 20          0.00951699      0.01706214      0.46989837      0x40AE419A     
Mean (x2)       1.08658207      1.09321456      0.97517472             
Variance (x12)  1.59148875      1.37225082      1.35854662             


The rather high variances don't show up in continued runs or shorter array sizes and could just be a statistical fluke associated
with the chosen starting seed.  (With small seeds, the high bits of the next several Park-Miller values will also be zero.  There are
suggestions for choosing a value higher than 16807, but that's another issue.)

Abel

[lingo]

"There are suggestions for choosing a value higher than 16807,.."
You can try 48271

Regards,
Lingo

[hutch--]

> Hutch may have some reservations about using .686 code in library functions.

The trick is to save the last 486 compatible version which was faster than the older Park Miller algo and put it into the library as the standard procedure and add the faster CMOVxx version as an extra. The only difference is documentation so that a prospective user does not try and use the standard version on an old box that does not support the CMOVxx familiy of instructions.

My main concern with an algo of thsi type is that it continues to test well on the range of random data tests which is actually more important than the more recent speed gains.

[Abel]

Under the heading "What I don't understand about ..."


Yesterday for 29-30 cycles:

Code Select Expand


rand32 proc base:DWORD
    mov eax, 16807              ;a = 7^5
    mul rand32_seed             ;edx:eax == a*seed == D:A
    mov ecx, 7fffffffh          ;ecx = m
    add edx, edx                ;edx = 2*D
....
    ret 4
rand32  endp



Today for 20-21 cycles:

Code Select Expand


rand32 proc base:DWORD
    mov eax, 16807              ;a = 7^5
    mov ecx, 7fffffffh          ;ecx = m
    mul rand32_seed             ;edx:eax == a*seed == D:A
    add edx, edx                ;edx = 2*D
....
    ret 4
rand32  endp


Couldn't 'chimp' similar effect in the rand32lingo code.

Abel