ASM:16bit Zufallszahlen ohne Wiederholung

[pps]

MADS

ct, count, copyfrom, test sind alles zeropage words
t_rand ist die Tabelle, wo die 16bit Werte abgelegt werden (also ist sie am Ende exakt doppelt so groß, we man Zahlen haben möchte.

Code: Alles auswählen

	.zpvar	.word	count,copyfrom,ct,test

	.proc gen_zufall	;800 16bit Zufallszahlen ohne Wiederholung erstellen
	mwa #0 count
	.local gen_rand16
	lda random
	sta copyfrom
@	lda random
	and #$f
	cmp #4
	bcs @-
	sta copyfrom+1
	cpw copyfrom #800	;gewünschte maximale Zahl
	bcs gen_rand16
;--- Test ob schon eingeschrieben in unserer Tabelle
	mwa #0 ct
	mwa #t_rand test
lp	ldy #1
	lda copyfrom+1
	cmp (test),y
	bcc next 	;kleiner
	bne next 	;größer
	dey
	lda copyfrom
	cmp (test),y
	beq gen_rand16	;gleich -> neue Zahl erstellen
next	inw ct
	adw test #2
	cpw count ct
	bcs lp
;---
set	lda copyfrom
chg	sta t_rand
	lda copyfrom+1
chg1	sta t_rand+1
	inw count
	adw chg+1 #2
	adw chg1+1 #2
	cpw count #799	;gewünschte Anzahl-1
	jcc gen_rand16
	.endl
	rts
	.endp
;---
t_rand
	.ds 1600

Warnung! Die Routine funktioniert, aber ES DAUERT. Ich nutze daher für mein Projekt eine am PC erstellte Liste, die dann halt nicht so ganz zufällig ist, für den Zweck ausreicht und halt sofort geht.
Ich benötigte exakt 800 Zahlen, zufällig und alle von 0 bis 799. Wenn Ihr nur einfach Zufallszahlen benötigt, die sich nicht wiederholen, kann das:

Code: Alles auswählen

	and #$f
	cmp #4
	bcs @-

und auch das:

Code: Alles auswählen

	cpw copyfrom #800	;gewünschte maximale Zahl
	bcs gen_rand16

weggelassen werden.
Wo doppelte Zahlen kein Problem sind, einfach alles zwischen den beiden ";---" weglassen. Dann ist das auch echt schnell.

[Dr. Irata]

... schöner Beitrag fürs Atari Wiki! Vielen Dank!

[pps]

Für meinen speziellen Fall habe ich einen falschen Ansatz gehabt. Ich will ja exakt 800 Zahlen von 0 bis 799 zufällig haben. Da kann ich ja einfach eine sortierte Tabelle von 0 bis 799 zufällig x mal durchtauschen und es sollte dann auch nicht mehr so lange dauern...

Im Listing oben muss man ja ewig suchen, ob die Zahl schon vorhanden ist. Manchmal ist der erste Ansatz nicht immer der Beste

Wenn man natürlich z. B. eine Liste mit 100 Zahlen haben möchte, im Bereich von 0 bis 799 ohne Dopplung, ist obige Routine wohl die Wahl. Dort sind dann ja nicht alle 800 möglichen Zahlen drin.

[pps]

So, hier der Code zu der oben skizzierten Idee. Es ist wirklich "geringfügig" schneller

Code: Alles auswählen

	.zpvar	.word	copyfrom,copyto,ct,test,test2

	.local gen_table
	mwa #0 ct
	mwa #t_rand test
lp	ldy #0
	lda ct
	sta (test),y
	iny
	lda ct+1
	sta (test),y
	inw ct
:2	inw test
	cpw ct #800
	bne lp
	.endl
;---
	.local shuffle
	mwa #0 ct
start
;--- generate 2 numbers to change
gen_rand16_1
	lda random
	sta test
@	lda random
	and #$f
	cmp #4
	bcs @-
	sta test+1
	cpw test #800
	bcs gen_rand16_1
gen_rand16_2
	lda random
	sta test2
@	lda random
	and #$f
	cmp #4
	bcs @-
	sta test2+1
	cpw test2 #800
	bcs gen_rand16_2
	cpw test test2
	beq gen_rand16_2
;--- multiply by 2 as table is a word table
	clc
	rol test
	rol test+1
	clc
	rol test2
	rol test2+1
;--- change
	adw test #t_rand copyfrom
	adw test2 #t_rand copyto
	ldy #0
lo	mva (copyfrom),y test
	mva (copyto),y (copyfrom),y
	mva test (copyto),y
	iny
hi	mva (copyfrom),y test
	mva (copyto),y (copyfrom),y
	mva test (copyto),y
	inw ct
	cpw ct #800 ;wir würfeln jetzt einfach auch 800 mal das Feld durch
	jne start
	.endl