[A86] Re: Random number generator

[Prev][Next][Index][Thread]

[A86] Re: Random number generator


There are lots of different methods.  The classic method used by most C
libraries is the linear congruential method, as described by Knuth in volume
2 of The Art of Computer Programming.  I'm not suggesting that you go out
and get those books, but they definitely have a lot of interesting stuff.

A good page on LCRNG's is at the following URL:

http://probabilitynet.com/lincong.htm

There is plenty of information out there on the technique, as a quick google
search will show you.  The following routine is from Matthew Shepcar's
Bomber Bloke.  I'm fairly sure it is a linear congruent generator:

; a spiffingly excellent random number generator:

Random:
        ld hl,0
        ld de,12345
Seed =$-2
        ld a,7921 & 255
        ld bc,1000h+(7921/256)
domult16:
        add hl,hl
        rla
        rl c
        jr nc,noadd16
        add hl,de
noadd16:
        djnz domult16
        inc hl
        ld (Seed),hl ;seed=(seed*7921+1) MOD 65536
        ld a,h
        ret

It's actually pretty simple if you see through the code (Shepcar has a thing
about writing awesome code that you can never figure out).  The comment that
shows what happens to the seed is indeed correct.

It starts out by loading the seed into DE.  It starts out at 12345.  B is
used as the loop counter, to multiply.  It's loaded with $10, or 16.  A and
C are used for the multiply constant, 7921.  The loop multiplies DE by AC,
with the result in HL.  HL is then incremented, as the addition constant is
1.  The seed is then saved, so it can be used the next time.  The routine
returns the value in HL and in A.  The 8 bit value (in A) is the high byte
of the value (as is recommended by Knuth).

If you want a good routine and can get by with about 800-900 t-states (quick
guess of it's speed), then I recommend using it.

I probably should have used that routine when writing Zelda 86, but I
decided to write my own.  The routine is probably not very good, but seemed
to work ok.  It's an interesting example of just trying stuff until you get
workable results.  Don't use it if you need statistically correct numbers,
or even close to perfectly distributed numbers.  I don't think it will
return every possible value.  Then again, I'm not sure exactly what it does,
and I don't feel like figuring it out :)

; a fast, yet decent random number generator
; returns: a = psuedo random number
; destroyed: flags
RandomNumber:
 push bc
 ld a,r
 ld b,a
 ld a,($1234)
_@RandomNumberSeed =$-2
 ld c,a
 ld a,(bc)
 ld (_@RandomNumberSeed),a
 xor b
 sub b
 add a,c
 pop bc
 ret

It basically does some junk operations against the R register, the seed, and
some "random" byte pulled out of the ROM.

Another approach that should work pretty well is to use a table.  Linear
congruential is mathematically proven to be correct, so it's likely better.
But I'm pretty sure a table would be faster and with the right algorithm,
return even distribution and provide a long period.  I used this method when
doing Game Boy programming.  This is the random number generator used in
Fall Down:

Random:
 push hl
 push de
 ld hl,RandSeed
 ldi a,(hl)
 ld h,(hl)
 ld l,a
 ld de,103
 add hl,de
 ld a,l
 ld (RandSeed),a
 ld a,h
 ld (RandSeed+1),a
 cpl
 add a,l
 ld d,0
 ld e,a
 ld hl,RandTable
 add hl,de
 ld a,(hl)
 pop de
 pop hl
 ret

RandTable:
 .db $69,$ce,$9b,$b4,$54,$a5,$9e,$cd,$57,$12,$4c,$65,$14,$4d,$92,$58
 .db $35,$8b,$a9,$05,$40,$dd,$ed,$bd,$0a,$1b,$bc,$b0,$c7,$15,$e7,$8c
 .db $4b,$88,$d7,$93,$50,$63,$d9,$fa,$af,$82,$7a,$00,$5a,$b9,$09,$bb
 .db $16,$75,$e3,$72,$f3,$c8,$ba,$d6,$e9,$37,$b6,$07,$e1,$c0,$79,$db
 .db $d3,$f2,$9a,$6a,$aa,$b5,$20,$56,$04,$5c,$e6,$59,$83,$2e,$95,$b7
 .db $c1,$5b,$28,$d4,$74,$9c,$5d,$66,$ec,$23,$67,$9d,$a1,$64,$0f,$2c
 .db $6c,$8e,$bf,$08,$99,$7f,$4a,$33,$b8,$6e,$fc,$6d,$a8,$36,$89,$5e
 .db $c4,$73,$b1,$d2,$32,$fe,$7b,$85,$55,$80,$53,$a4,$0e,$7e,$d0,$c5
 .db $f8,$18,$0b,$a6,$c2,$c9,$13,$dc,$94,$71,$eb,$86,$c3,$62,$84,$46
 .db $47,$90,$3f,$da,$a3,$6f,$06,$f5,$98,$ca,$8d,$2f,$e8,$9f,$60,$de
 .db $61,$fb,$ad,$3b,$f7,$3e,$4f,$0c,$f4,$e0,$d8,$ac,$d1,$31,$c6,$34
 .db $a2,$17,$8f,$ea,$2a,$5f,$96,$81,$45,$48,$f9,$30,$21,$68,$27,$f1
 .db $fd,$4e,$ee,$cc,$78,$77,$1d,$97,$1c,$24,$3d,$a0,$2d,$26,$03,$22
 .db $e5,$11,$ef,$6b,$b2,$e2,$02,$49,$3a,$d5,$87,$76,$39,$ab,$df,$1e
 .db $29,$cb,$1f,$52,$7c,$01,$3c,$38,$0d,$41,$f6,$1a,$2b,$ae,$f0,$10
 .db $91,$b3,$43,$7d,$42,$44,$70,$8a,$cf,$ff,$25,$a7,$be,$19,$51,$e4

The table is evenly distributed with 256 bytes.  Looking back at the code,
the last part seems pretty silly.  It loads a 16 bit random seed, adds 103
to it and  saves the random seed.  It then adds the complement of the high
byte with the low byte, and retreives that position in the table as the
random number.  I think it would work just fine if only the low byte of the
seed were used.  Then again, maybe it doesn't matter.

Amazingly, I even have the C code that generated the table.  I cut the
important part:

  srand(time(0));
  for(i = 0; i < 256; i++)
    a[i] = i;
  for(i = 0; i < 256 * 16; i++)
    swap(&a[rand() % 256], &a[rand() % 256]);

Hopefully, this should answer everyone's questions about random number
generators :)

> Does anyone know how to generate a random number without using the r
> register? (I wnat to generate several in a row and using the r register
they
> are almost identical.)
Follow-Ups: References: