[A86] Re: Random number generator
[Prev][Next][Index][Thread]
[A86] Re: Random number generator
Thanks a lot, that really helped.
David Phillips <david@acz.org> wrote:
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.)
Martin Smithsmity42@yahoo.com
---------------------------------
Do You Yahoo!?
Find a job, post your resume on Yahoo! Careers.
References: