random numbers

[ghjjkl]

how can i get random number without using any 32-bit registers? How are random(N) functions implemented in old platforms like zx spectrum, c64 and others?

[jj2007]

Why don't you want to use 32-bit registers? It's possible under DOS.

[MichaelW]

Linear congruential generators are common, but there are many other possibilities, some worse and some much better.

[ghjjkl]

i just want to know as more ways to do it as possible 

[ghjjkl]

Linear congruential generators are common, but there are many other possibilities, some worse and some much better.

but i have to use pretty big integers to get long sequence of random numbers, haven't i?

[MichaelW]

If by "a long sequence" you mean a long period, from the linked page, "the period of a general LCG is at most m".

[dedndave]

Code: [Select]

        .MODEL  Small
        .STACK  4096
        .DOSSEG
        .386
        OPTION  CaseMap:None

;####################################################################################

        .DATA

;************************************************************************************

        .DATA?

wRndSeed    dw ?

;####################################################################################

        .CODE

;************************************************************************************

_main   PROC    FAR

        mov     dx,@data
        mov     ds,dx

        call    RandSeed

        call    RandNum

        call    RandNum

        mov     ax,4C00h
        int     21h

_main   ENDP

;************************************************************************************

RandSeed PROC

;seeds the random number generator

        mov     ah,0
        int     1Ah
        mov     wRndSeed,dx
        ret

RandSeed ENDP

;************************************************************************************

RandNum PROC

;returns a pseudo-random value in AX

        mov     ax,25173
        mul word ptr wRndSeed
        add     ax,13849
        adc     dx,0
        mov     wRndSeed,ax
        xchg    ax,dx
        ret

RandNum ENDP

;####################################################################################

        END     _main

[FORTRANS]

Hi,

   In the old forum, there was a thread on random numbers:

Re: Random Generator
http://www.masmforum.com/board/index.php?topic=11679.msg123138#msg123138

See Reply # 44 for my 16-bit implementation of a 32-bit linear
congruential random number generator.  This one was based on one
that was mentioned by Knuth in AoCP.  You can read the whole
thread for some good discussion of various generators.

   Search on Park Miller in both the old and current forum for another
good LCG random number routine.

HTH,

Steve N.

[ghjjkl]

Code: [Select]

        .MODEL  Small
        .STACK  4096
        .DOSSEG
        .386
        OPTION  CaseMap:None

;####################################################################################

        .DATA

;************************************************************************************

        .DATA?

wRndSeed    dw ?

;####################################################################################

        .CODE

;************************************************************************************

_main   PROC    FAR

        mov     dx,@data
        mov     ds,dx

        call    RandSeed

        call    RandNum

        call    RandNum

        mov     ax,4C00h
        int     21h

_main   ENDP

;************************************************************************************

RandSeed PROC

;seeds the random number generator

        mov     ah,0
        int     1Ah
        mov     wRndSeed,dx
        ret

RandSeed ENDP

;************************************************************************************

RandNum PROC

;returns a pseudo-random value in AX

        mov     ax,25173
        mul word ptr wRndSeed
        add     ax,13849
        adc     dx,0
        mov     wRndSeed,ax
        xchg    ax,dx
        ret

RandNum ENDP

;####################################################################################

        END     _main

but why 25173, 13849?

[MichaelW]

but why 25173, 13849?

Considering that the period of Dave's generator is 65534, I would guess that the values were carefully selected.

[dedndave]

that's right
you can google around for tables of LCG constants to see other pairs   :P

[ghjjkl]

well, alright then 
thanks, an another thing i've managed  ::)

[dedndave]

Michael's link in reply #2 is a good read   :t

[BlueMR2]

I'm a fan of the R250 PRNG.  Seed it with a regular LCG PRNG, so more code overall, but it's faster on older hardware and gives nice results.

http://www.gamedev.net/topic/449339-r250-algorithm-of-kirkpatrick-stoll-random-number/

http://www.taygeta.com/random.html

[MichaelW]

Starting with the R250 code from here, and using the static buffer:

Code: [Select]

;==============================================================================
include \masm32\include\masm32rt.inc
include \masm32\macros\timers.asm
.686
;==============================================================================
.data
;==============================================================================

    align 4
    r250_index  dd 0
    r250_buffer dd 15301,57764,10921,56345,19316,43154,54727,49252,32360,49582
                dd 26124,25833,34404,11030,26232,13965,16051,63635,55860,5184
                dd 15931,39782,16845,11371,38624,10328,9139,1684,48668,59388
                dd 13297,1364,56028,15687,63279,27771,5277,44628,31973,46977
                dd 16327,23408,36065,52272,33610,61549,58364,3472,21367,56357
                dd 56345,54035,7712,55884,39774,10241,50164,47995,1718,46887
                dd 47892,6010,29575,54972,30458,21966,54449,10387,4492,644
                dd 57031,41607,61820,54588,40849,54052,59875,43128,50370,44691
                dd 286,12071,3574,61384,15592,45677,9711,23022,35256,45493
                dd 48913,146,9053,5881,36635,43280,53464,8529,34344,64955
                dd 38266,12730,101,16208,12607,58921,22036,8221,31337,11984
                dd 20290,26734,19552,48,31940,43448,34762,53344,60664,12809
                dd 57318,17436,44730,19375,30,17425,14117,5416,23853,55783
                dd 57995,32074,26526,2192,11447,11,53446,35152,64610,64883
                dd 26899,25357,7667,3577,39414,51161,4,58427,57342,58557
                dd 53233,1066,29237,36808,19370,17493,37568,3,61468,38876
                dd 17586,64937,21716,56472,58160,44955,55221,63880,1,32200
                dd 62066,22911,24090,10438,40783,36364,14999,2489,43284,9898
                dd 39612,9245,593,34857,41054,30162,65497,53340,27209,45417
                dd 37497,4612,58397,52910,56313,62716,22377,40310,15190,34471
                dd 64005,18090,11326,50839,62901,59284,5580,15231,9467,13161
                dd 58500,7259,317,50968,2962,23006,32280,6994,18751,5148
                dd 52739,49370,51892,18552,52264,54031,2804,17360,1919,19639
                dd 2323,9448,43821,11022,45500,31509,49180,35598,38883,19754
                dd 987,11521,55494,38056,20664,2629,50986,31009,54043,59743
;==============================================================================
.code
;==============================================================================

OPTION PROLOGUE:NONE
OPTION EPILOGUE:NONE

R250 proc
      mov   ecx, r250_index
      mov   edx, ecx
      cmp   ecx, 147
      jb    L0
      sub   edx, 147
      jmp   L1
    L0:
      add   edx, 103
    L1:
      mov   eax, r250_buffer[ecx*4]
      xor   eax, r250_buffer[edx*4]
      cmp   ecx, 249
      jb    L2
      xor   ecx, ecx
      jmp   L3
    L2:
      inc   ecx
    L3:
      mov   r250_index, ecx
      ret
R250 endp

OPTION PROLOGUE:PrologueDef
OPTION EPILOGUE:EpilogueDef

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

    REPEAT 10
        call  R250
        printf("%d\t",eax)
    ENDM
    printf("\n")

    invoke GetCurrentProcess
    invoke SetProcessAffinityMask, eax, 1

    invoke Sleep, 6000
    counter_begin 1000000, HIGH_PRIORITY_CLASS
        call  R250
    counter_end
    printf("%d cycles\n\n",eax)

    inkey
    exit
;==============================================================================
end start

I get a (32-bit) procedure that runs in 7 cycles (including the call overhead) on my P3 and 2 cycles (?) on my Core i3.

And BTW, I checked the first 100 results against the first 100 results for the compiled C source.