what kinda randomgenerators are there?

[daydreamer]

I am sitting here trying to code a fast mersenne twister, but I have seconds thoughts if there arent any better suitable for the purpose I want it for: procedural texture
so can you more experienced old guys help me with advice choosing one
1: it must be good enough to generate procedural texture
2: it would be good if I could find a BAD kinda randomgenerator, bad in the sense its maybe could be possible to a specific seed, gives a pattern that is easily reversed

[FORTRANS]

Hi,

   The standard easy random number generator is the linear
congruential pseudo-random generator.

  Ran(n+1) = Ran(n) * number + (other number)


   With proper choices of the numbers, you get reasonable
sequences. 

1: it must be good enough to generate procedural texture

   Try it, it should be okay.

2: it would be good if I could find a BAD kinda randomgenerator, bad in the sense its maybe could be possible to a specific seed, gives a pattern that is easily reversed

   That can be done with this kind of generator.  If I
understand you correctly.  The least significant bits
are not very random, and the multiplier and constant
can be determined.

   Some suggested numbers.

Code Select Expand


; - - - - - -
; "Random number routine" from Knuth/Numerical Recipies
Rand32  DD      31415926        ; a la K, Use zero to test NR results
RandA   DD      1664525         ; As per NR
RandC   DD      1013904223      ; As per NR


RAND32 = RAND32 * RANDA + RANDC

HTH,

Steve N.

[dedndave]

i like that code, Steve
i suggest initializing the Rand32 seed with a reading from QueryPerformanceCounter or something
so that the sequence has a new starting place each time a program is run
i have even used QueryPerfomanceCounter, itself, to generate pseudo-random values

[FORTRANS]

Hi Dave,

   Yes, I use a RandInit routine to read a time of day
to start with different seeds.  Starting with the same
one helps in comparing two routines like different sorts.
It can also help in debugging.  If a texture needs to be
repeatable, then specifying a particular value may be
handy.  The values I gave were just to follow the
"Book Code" for a good start.

Cheers,

Steve N.

[NightWare]

try this :

Code Select Expand

.DATA
ALIGN 4
Rand_Seed DWORD ?

.CODE
ALIGN 16
;
; Initialize random numbers
;
; syntax :
; call InitRandNum
;
; Return:
; eax = number of ticks since the beginning
;
InitRandNum PROC
push ecx
push edx

invoke GetTickCount
test eax,eax
jnz Label1
mov eax,123456789
Label1: mov Rand_Seed,eax

pop edx
pop ecx
ret
InitRandNum ENDP


ALIGN 16
;
; generate a random number between 0 and max value - 1
;
; syntax :
; mov ebx,Range
; call GetRandNum
;
; return :
; eax = the random number
;
GetRandNum PROC
push edx

mov eax,987654321
mul Rand_Seed
bswap eax
xor eax,078787878h
jnz Label1
mov eax,123456789
Label1: mov Rand_Seed,eax
cmp ebx,1
je Label2
mul ebx
mov eax,edx
Label2:
pop edx
ret
GetRandNum ENDP

change the values/mask if needed...

[bruce1948]

Another from Knuth, I use rdtsc as the seed.

Code Select Expand


; Constants for the random number generator
MP  equ 2147483647                                  ; A Mersenne prime
AA  equ 48271                                       ; This does well in the spectral test
QQ  equ 44488                                       ; MM / AA
RR  equ 3399                                        ; MM % AA; It is important that RR < QQ

; Seed the simple randon number generatot
rand_seed proc USES edx
        push edx
        rdtsc
        .if sdword ptr eax < 0                      ; if seed -ve
            add eax, MP                             ; make +ve
        .endif
        mov RSeed, eax                              ; don't need the value in edx
        pop edx
        ret
rand_seed endp

align 4

; Taken from Knuth
; RSeed = AA * (RSeed % QQ) - RR * (RSeed / QQ)
random proc USES esi ebx ecx edx edi
        mov ecx, QQ
        mov esi, RR
        mov edi, AA
        xor edx, edx
        mov eax, RSeed
        div ecx
        ; Quotient in eax, Remainder in edx
        mov ebx, edx                                ; save remainder in ebx
        mul esi                                     ; eax = RR * (RSeed / QQ)
        xchg eax, ebx                               ; save above result in ebx and get RSeed % QQ into eax
        mul edi                                     ; eax = AA * (RSeed % QQ)
        sub eax, ebx                                ; eax = = AA * (RSeed % QQ) - RR * (RSeed / QQ)
        .if sdword ptr eax < 0                      ; is eax -ve
            add eax, MP                             ; make eax +ve
        .endif
        mov RSeed, eax                              ; Save result as new seed
        ret                                         ; and return the random number
random endp




Bruce

[Kresha7]

i was searching for this kind of code too this post was helpfull for me too :P thx you guys

[dedndave]

lol - guess i'll toss my hat in the ring, too

;--------------------------------------------------------------------------

Randm   PROC

;Random ASCII character generator
;generates numbers 0-9, letters a-z and A-Z

;Call With: Nothing

;  Returns: eax = al = pseudo-random ASCII character

        INVOKE  Sleep,0
        sub     esp,8
        INVOKE  QueryPerformanceCounter,esp
        pop     eax
        pop     edx
        xor     eax,edx
        xor     edx,edx
        mov     ecx,62
        div     ecx
        xchg    eax,edx
        add     eax,30h     ;'0'
        cmp     al,39h      ;'9'
        jbe     Randm0

        add     eax,7

        cmp     al,5Ah      ;'Z'
        jbe     Randm0

        add     eax,6

Randm0: ret

Randm   ENDP

;--------------------------------------------------------------------------

[MichaelW]

I don't actually know, but I would guess that procedural textures would not require high-quality random numbers, and based on this I'm assuming that execution speed is the most important characteristic. George Marsaglia posted the C implementations for eight random number generators here, and guessing that the quality of the bits in the last half of the 32-bit number that it generates would be unlikely to affect the intended use, I selected CONG. And I'm also guessing that the range of each generated number needs to be controllable, so I added a parameter and code to do this, scaling the return value to the range [0, base). I tested the cycle counts for several other generators for comparison. I don't have an implementation of mersenne twister to test, but I seem to recall that the implementations I have tested were not at all fast.

Code Select Expand


; «««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««
    include \masm32\include\masm32rt.inc
    .686
    include \masm32\macros\timers.asm
; «««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««
    .data
      counts dd 10 dup(0)
    .code
; «««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««

;--------------------------------------------------------
; This is an asm implementation of a simple congruential
; generator by George Marsaglia.
;--------------------------------------------------------

.data
    cong_seed dd 380116160
.code

OPTION PROLOGUE:NONE
OPTION EPILOGUE:NONE

align 4

cong proc
    mov eax, cong_seed
    mov ecx, 69069
    mul ecx
    add eax, 1234567
    mov cong_seed, eax
    ret
cong endp

; «««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««

;----------------------------------------------------------
; This is the above generator with a base parameter added,
; performing the mod operation with a multiply.
;----------------------------------------------------------

align 4

congb proc base:DWORD
    mov eax, cong_seed
    mov ecx, 69069
    mul ecx
    add eax, 1234567
    mov cong_seed, eax
    mov ecx, [esp+4]
    mul ecx
    mov eax, edx
    ret 4
congb endp

OPTION PROLOGUE:PrologueDef
OPTION EPILOGUE:EpilogueDef

; «««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««

;----------------------------------------------------------
; This is the above generator with a base parameter added,
; performing the mod operation with a division.
;----------------------------------------------------------

align 4

congb2 proc base:DWORD
    mov eax, cong_seed
    mov ecx, 69069
    mul ecx
    xor edx, edx
    add eax, 1234567
    mov cong_seed, eax
    div dword ptr [esp+4]
    mov eax, edx
    ret 4
congb2 endp

OPTION PROLOGUE:PrologueDef
OPTION EPILOGUE:EpilogueDef

; «««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««
start:
; «««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««

    ;----------------------
    ; A quick visual test.
    ;----------------------

    mov ebx, 1000
    .WHILE ebx
      invoke congb, 0100h
      print uhex$(eax),9
      dec ebx
    .ENDW

    print chr$(13,10)
    inkey
    print chr$(13,10)

    ;-----------------------------------
    ; A quick test of the distribution.
    ;-----------------------------------

    mov ebx, 100000000
    .WHILE ebx
      invoke congb, 10
      inc DWORD PTR counts[eax*4]
      dec ebx
    .ENDW
    print ustr$(counts),13,10
    print ustr$(counts+4),13,10
    print ustr$(counts+8),13,10
    print ustr$(counts+12),13,10
    print ustr$(counts+16),13,10
    print ustr$(counts+20),13,10
    print ustr$(counts+24),13,10
    print ustr$(counts+28),13,10
    print ustr$(counts+32),13,10
    print ustr$(counts+36),13,10

    print chr$(13,10)
    inkey
    print chr$(13,10)

    invoke Sleep, 3000

    counter_begin 1000, HIGH_PRIORITY_CLASS
      invoke nrandom, 100
    counter_end
    print ustr$(eax)," cycles, nrandom",13,10

    counter_begin 1000, HIGH_PRIORITY_CLASS
      invoke crt_rand
    counter_end
    print ustr$(eax)," cycles, crt_rand",13,10

    counter_begin 1000, HIGH_PRIORITY_CLASS
      invoke cong
    counter_end
    print ustr$(eax)," cycles, cong",13,10

    counter_begin 1000, HIGH_PRIORITY_CLASS
      invoke congb, 100
    counter_end
    print ustr$(eax)," cycles, congb",13,10

    counter_begin 1000, HIGH_PRIORITY_CLASS
      invoke congb2, 100
    counter_end
    print ustr$(eax)," cycles, congb2",13,10,13,10

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


The cycle counts running on a P3:

Code Select Expand


86 cycles, nrandom
60 cycles, crt_rand
5 cycles, cong
8 cycles, congb
30 cycles, congb2


Edit: The attachment contains the test app above, along with a separate app that does "scatterplot" test.

[Slugsnack]

in cong, is the 'xor edx, edx' superfluous ?

[MichaelW]

in cong, is the 'xor edx, edx' superfluous ?

Yes it is, and also for congb, but not for congb2. Thanks for pointing that out. The code I started with was essentially that for congb2, and I failed to notice that the xor edx, edx was not necessary for the others.

[daydreamer]

thanks everyone

[daydreamer]

here is my first attempt, see if I can find some suitable numbers for 16bit, maybe pmulhw it better suitable?

Code Select Expand


seed dw 31415   
.code
    mov ax,seed ;seed
    mov ebx,56789
    mov edx,263
    movd MM0,eax
    movd MM1,ebx
    movd MM2,edx
    pmullw MM0,MM2
    paddw MM0,MM1
    movd eax,MM0 ;new seed
    mov seed,ax


[dedndave]

why not make "seed" a 32-bit value ?
or....

        movzx   eax,word ptr seed

of course, you ARE trying to get random numbers - lol

[Astro]

it would be good if I could find a BAD kinda randomgenerator, bad in the sense its maybe could be possible to a specific seed, gives a pattern that is easily reversed

All PRNGs do this, unless you are using a truly random source for input such as radioactive decay.

Have a look at the Alternating Step Generator LFSR.

You could either seed it randomly or with known values. You must "tap" in specific places though based on the length of the LFSR in order to get the maximum period, which is all combinations except zero (zero would always produce zero output).

http://en.wikipedia.org/wiki/Alternating_step_generator

Best regards,
Astro.