Last modified on 23 December 2010, at 07:29

Programming:Random Number Generator

Revision as of 07:29, 23 December 2010 by Nich (Talk | contribs) (Added section on generating random numbers from BASIC, and reorganised and renamed other headings)

BASIC

The BASIC command RANDOMIZE TIME can be used to generate random numbers, using the value of the TIME variable as a seed. The TIME variable is incremented every 1/300th of a second, so it is highly unlikely that the same set of numbers will be generated each time the BASIC program is run.

However, after about five or six numbers are obtained using the RND command, the randomness of the numbers decreases dramatically. The listing below demonstrates this problem:

10 MODE 2
20 FOR a=1 TO 23
30 RANDOMIZE TIME
40 FOR b=1 TO 25
50 PRINT USING("## ");INT(RND*100);
60 NEXT b
70 PRINT
80 NEXT a

This problem can be overcome by using the commands RANDOMIZE TIME:RANDOMIZE RND instead. This re-initialises the random number seed and greatly improves the randomness of the numbers that are obtained using the RND command.

Machine code

8-bit random number generator

This is a very simple generator. Its function is x[i + 1] = (5 * x[i] + 1) mod 256. The only advantage is the small size and its simplicity.

Input: none

Output: A = a pseudo random number, period 256

Rand8	ld	a,Seed		; Seed is usually 0
	ld	b,a
	add	a,a
	add	a,a
	add	a,b
	inc	a		; another possibility is ADD A,7
	ld	(Rand8+1),a
	ret

8-bit random number generator (lookup table based)

To use this routine you need to define 1 byte of RAM for the RandomPtr.

Input: none

Output: A = a pseudo random number, period 256

RandomNumber:
        push    hl
        ld      a,(RandomPtr)
        inc     a
        ld      (RandomPtr),a
        ld      hl,RandTable
        add     a,l
        ld      l,a
        jr      nc,skip
        inc     h
.skip:  ld      a,(hl)
        pop     hl
        ret

RandTable:
        db      &3B,&02,&B7,&6B,&08,&74,&1A,&5D,&21,&99,&95,&66,&D5,&59,&05,&42
        db      &F8,&03,&0F,&53,&7D,&8F,&57,&FB,&48,&26,&F2,&4A,&3D,&E4,&1D,&D9
        db      &9D,&DC,&2F,&F5,&92,&5C,&CC,&00,&73,&15,&BF,&B1,&BB,&EB,&9E,&2E
        db      &32,&FC,&4B,&CD,&A7,&E6,&C2,&10,&11,&80,&52,&B2,&DA,&77,&4F,&EC
        db      &13,&54,&64,&ED,&94,&8C,&C6,&9A,&19,&9F,&75,&FA,&AA,&8D,&FE,&91
        db      &01,&23,&07,&C1,&40,&18,&51,&76,&3C,&BD,&2A,&88,&2D,&F1,&8A,&72
        db      &F6,&98,&35,&97,&68,&93,&B3,&0C,&82,&4E,&CB,&39,&D8,&5F,&C7,&D4
        db      &CE,&AE,&6D,&A3,&7C,&6A,&B8,&A6,&6F,&5E,&E5,&1B,&F4,&B5,&3A,&14
        db      &78,&FD,&D0,&7A,&47,&2C,&A8,&1E,&EA,&2B,&9C,&86,&83,&E1,&7B,&71
        db      &F0,&FF,&D1,&C3,&DB,&0E,&46,&1C,&C9,&16,&61,&55,&AD,&36,&81,&F3
        db      &DF,&43,&C5,&B4,&AF,&79,&7F,&AC,&F9,&37,&E7,&0A,&22,&D3,&A0,&5A
        db      &06,&17,&EF,&67,&60,&87,&20,&56,&45,&D7,&6E,&58,&A9,&B0,&62,&BA
        db      &E3,&0D,&25,&09,&DE,&44,&49,&69,&9B,&65,&B9,&E0,&41,&A4,&6C,&CF
        db      &A1,&31,&D6,&29,&A2,&3F,&E2,&96,&34,&EE,&DD,&C0,&CA,&63,&33,&5B
        db      &70,&27,&F7,&1F,&BE,&12,&B6,&50,&BC,&4D,&28,&C8,&84,&30,&A5,&4C
        db      &AB,&E9,&8E,&E8,&7E,&C4,&89,&8B,&0B,&24,&85,&3E,&38,&04,&D2,&90

16-bit random number generator

This algorithm uses a similar method, but returns much better results.

Input: none

Output: A = a pseudo random number, period 65536

Rand16	ld	de,Seed		; Seed is usually 0
	ld	a,d
	ld	h,e
	ld	l,253
	or	a
	sbc	hl,de
	sbc	a,0
	sbc	hl,de
	ld	d,0
	sbc	a,d
	ld	e,a
	sbc	hl,de
	jr	nc,Rand
	inc	hl
Rand	ld	(Rand16+1),hl
	ret

16-bit random number generator using the R register

A pseudo random generator using the R register for the first byte of the random number. It then uses this number as a seed to feed the 8-bit random number generator to generate the other byte of the random value.

Input: none

Output: HL = a pseudo random number, period 65536

Rand16	ld a,r
	ld h,a

Rand8	ld b,a
	add a,a
	add a,a
	add a,b
	inc a
	ld (Rand8 + 1),a

	ld l,a          ; HL now contains a random 16-bit number
	ret