Ober- und Untergrenzen beim Generieren von Zufallszahlen

Bytebreaker · 23. Dezember 2015

Hallo,

auf http://www.retro-programming.de findet man hier einen Exkurs zum Thema Zufallszahlen.

Auf die verschiedenen Möglichkeiten (Timer, SID, Rasterstrahl, Basic-RND) möchte/muss ich nicht eingehen. Was mich dagegen umtreibt ist eine vorgestellte Option zum Generieren von Zufallszahlen innerhalb bestimmter Ober- und Untergrenzen (bezogen auf 1 Byte Zahlenraum). Sinnbildlich sieht das Konzept so aus:

Code

loop:
jsr getrandom ; das kann irgendeine Subroutine sein die einen Zufallswert in den Akku zurückgibt
cmp #42-15+1 ; 42 sei die Obegrenze, 15 die Untergrenze, die +1 braucht man wegen Carry Flag. Warum?
bcs loop: ; so lange der Wert im Akku > 28, würfle neue Zahl.
adc #15 ; Wenn der Wert im Akku zwischen 0 und 27, addiere 15. D.h. Werte zwischen 15 und 42 sind die Folge

Ich verstehe das Prinzip, aber nicht, warum man +1 für das Carry Flag in die cmp-Formel mit einrechnet.
Positive Werte nach CMP-Vergleich (ohne dass das Ergebnis in den Akku geschrieben wird, nur die Flags werden gesetzt) führen aufgrund der 6502 Arithmetik dazu, dass das C-Flag gesetzt wird. Resultiert nach dem CMP ein negativer Wert, wird das C-Flag nicht gesetzt. Warum das so ist, weiß, bzw. verstehe ich. Ich verstehe daher auch die Abfrage bcs an dieser Stelle.

Was mir nicht in den Kopf geht ist das bewusste Einbauen von +1 in den CMP-Parameter, "wegen des Carry Flags". Der Kursautor gibt keine nähere Erläuterung.

Liegt es daran, dass wenn die Zufallsroutine eine 27 erwürfelt und man 27 anstatt 28 abzieht, das Carry Flag ja gesetzt wird weil 0 ja vom 6502 "positiv" gesehen wird. D.h. die Obergrenze 42 würde niemals erwürfelt werden und um das zu verhindern zieht man vorsichtshalber immer 1 mehr ab als man muss.

Stimmt das?

Wenn ich mir überlege wie einfach das in BASIC ohne 795 Hirnwindungen gegangen wäre ich denke lieber an den Geschwindigkeitszuwachs .. schon gehts mir besser!

Gold Beaver · 23. Dezember 2015

Zitat von Bytebreaker

Was mir nicht in den Kopf geht ist das bewusste Einbauen von +1 in den CMP-Parameter, "wegen des Carry Flags". Der Kursautor gibt keine nähere Erläuterung.

Das hängt mit dem CMP-Befehl zusammen, der sowohl bei Accu > Vergleichsoperand als auch schon bei = das Carry-Flag setzt, wenn man das nicht berücksichtigt hätte man einen off-by-one Error bei der Obergrenze.

Diese +1 Schreibweise ist nicht unüblich, um das zu verdeutlichen, und durch das 42-15 davor erkennt man dann auch auf den ersten Blick Unter- und Obergrenze der zulässigen Werte.

Bytebreaker · 23. Dezember 2015

Ok vielen Dank. Dann ist es also so wie ich vermutet habe. Die Obergrenze würde sonst nie als Wert vorkommen, sondern immer nur Obergrenze minus 1.

Gold Beaver · 23. Dezember 2015

Exakt!

Mike · 23. Dezember 2015

Die '+1' kommt meines Erachtens woanders her:

Das CMP selbst benötigt kein definiertes Carry-Flag im voraus. Im Anschluß wird das Ergebnis des Generators aber nicht direkt verwendet, sondern als Offset der Basis-Zahl A hinzugezählt. Damit kann man dann vorweg nur die Zahlen 0 = A-A bis B-A gebrauchen, und B-A+1 wäre wiederum schon zu groß.

Vergleicht man jetzt also mit B-A+1, dann ist bei allen Zahlen strikt kleiner das Carry-Flag gelöscht, darum kann dann die Schleife beendet werden. Ansonsten zieht man eine neue Zahl, solange bis die Bedingung erfüllt ist. Zuguterletzt wird die Basis-Zahl A addiert und man hat jetzt Zahlen von A bis B inklusive.

Um den Preis eines weiteren Vergleichs, aber vielleicht leichter verständlich, ginge das genauso gut so:

Code

loop:
jsr getrandom
cmp #15
bcc loop ; kleiner 15? Dann erneut würfeln
cmp #42+1
bcs loop ; größer oder gleich 43 (=42+1)? Dann erneut würfeln

Edit: Mist. Cold Sewers war schneller.

Hexworx · 23. Dezember 2015

Oder du musst den Code auf BCC umbauen:

Code

loop:
jsr getrandom
cmp #42-15 ; OHNE "+1"!
bcc weiter:
jmp loop:
weiter:
adc #15

Theoretisch wäre das auf den ersten Blick ja langsamer (durch den zusätzlichen JMP); kommt aber halt drauf an, welcher Fall öfter zutrifft. Das eine C in BCC steht übrigens für 'cleiner' .

Ja, ich war zu langsam. Ich komm' noch nicht so ganz klar...

Mike · 23. Dezember 2015

Nö. BCS und BCC sind exakt invers in der Bedingung, darum verhält sich die Sequenz ".loop:[...]:BCC skip:JMP loop:.skip" genauso wie ".loop:[...]:BCS loop". CMP braucht darum ebenfalls die "#42-15+1" als Grenze.

Hexworx · 23. Dezember 2015

Natürlich, Mike. Was is' bloß mit mir los .

Vernunftmensch · 20. August 2018

Ich sehe den Welt vor lauter Bäume nicht...

Welches Stück ASM kann sowohl im Emulator als auch auf der echten Maschine nahezu gleichverzeilte Zahlen zwischen 0 und 255 erzeugen?

Draco · 20. August 2018

Ich würde ein einfaches LFSR implementieren und mir die benötigten 8 Bits herausschneiden. So ähnlich, wie http://codebase64.org/doku.php?id=base:small_fast_8-bit_prng, nur mit mehr Bits, damit es sich nicht zu schnell wiederholt.
Hier gibt's eine ganze Reihe von Zufallszahlengeneratoren: http://www.codebase64.org/doku.php?id=base:6502_6510_maths

Vernunftmensch · 20. August 2018

Code

lda seed
beq doEor
clc
asl
beq noEor ;if the input was $80, skip the EOR
bcc noEor
doEor eor #$1d
noEor sta seed

Liefert schlechte Rauschzeichen:

<EDIT MOD>Bild unbrauchbar weil zu klein. Vergrösserte Version eingefügt.

Draco · 20. August 2018

Dann sind, wie schon angemerkt, 8-Bit für das LFSR zu wenig. Ein Größeres mit gescheitem Seed müsste bessere Ergebnisse liefern, die sich nicht zu schnell wiederholen.

Vernunftmensch · 20. August 2018

Schon ein paar Seeds ausprobiert. Löst aber leider nicht das Problem.

Vernunftmensch · 20. August 2018

Code

.export ___zufallszeichen
seed:
.byte $8d
verw:
.byte 10
___zufallszeichen:
lda #10
sta verw
verwerfen:
lda seed
beq doEor2
clc
asl
beq noEor2 ;if the input was $80, skip the EOR
bcc noEor2
doEor2: eor #$1d
noEor2: sta seed
dec verw
bne verwerfen
rts

Alles anzeigen

Nicht jede Zahl sofort nehmen, ist die Lösung, siehe Anhang.

<EDIT MOD>Bild unbrauchbar weil zu klein. Vergrösserte Version eingefügt.

Draco · 20. August 2018

Die modifizierte Version vom Boulderdash-Zufallsgenerator wäre auch einen Versuch wert: https://csdb.dk/forums/?roomid…picid=3351&showallposts=1
Ist allerdings nicht portabel.