Zufallszahlen in Assembler

[Olix]

... sollte doch gehen indem man das Vorfiltern mit dem AND anpasst....

also falls du 0-8 willst dann

and #15

[LarsImNetz]

Wenn Du größere Randomwerte brauchst, musst Du den "Vorfilter" (das AND) vergrößern.

Mögliche "Vorfilter" sind halt $03, $07, $0f, $1f, $3f, $7f. Also entsprechend immer die Bits für das AND setzen. Das könnte man auch weglassen, nur dann läuft die Schleife bei kleinen modvalue Werten halt viel länger.

Willst Du es richtig dynamisch:

Code: Alles auswählen

; modulo im Akku vorausgesetzt:
  ldx #0
  cmp #4
  bcc ?less
  inx
  cmp #8
  bcc ?less
  inx
  cmp #16
  bcc ?less
  inx
  cmp #32
  bcc ?less
  inx
  cmp #64
  bcc ?less
  inx
  
?less
   lda RANDOM
   and ?filter,x         ; Vorfilter!
   
   sec
?modulus   
   sbc modvalue
   bcs ?modulus
   adc modvalue
   rts
  
?filter
 .byte $07,$0F,$1F,$3F,$7F,$FF

Ist halt etwas fummelig im Atari 2^n-1 bits für ein AND richtig zu setzen.

LG
Lars

[Irgendwer]

Bei Eurem Ansatz komme ich relativ stabil auf Verteilungswerte von knapp 3% bis 33% wobei hier die Zahlen 5 und 0 auffällig unterdurchschnittlich repräsentiert werden - irgendwas stimmt hier nicht. Das sieht fast schon aus wie eine Gaußsche Normalverteilung...

...und da hast Du vollkommen recht. Nachdem ich nochmal kurz überlegt habe, komme ich zum Schluß, dass der Ansatz nicht tauglich ist.
(Aber wenigstens bin nicht nur ich darauf hereingefallen... )

Eine "Random"-Zahl binär wie
01101010 oder
10101100
ergibt in der Addition immer 4 - wenn ich jetzt nicht schon wieder einen Denkfehler habe besteht die Wahrscheinlichkeit dafür 70 zu 256 also gut 27%.
Hingegen gibt es nur eine Kombination von
00000000 oder
11111111 mit der Wahrscheinlichkeit von 1/256 also knapp 0,4%.

Aber vielleicht kann man das Prinzip ja dann für Logik verwenden, bei der eine solche Gewichtung (häufige/seltene Ereignisse) von Vorteil ist...

[Irgendwer]

Wenn Du größere Randomwerte brauchst, musst Du den "Vorfilter" (das AND) vergrößern.

Hier gibt es IMHO aber auch ein Problem: Der Vorfilter manipuliert nämlich auch die Wahrscheinlichkeit für bestimmte Reste...

[LarsImNetz]

Ja, das stimmt.
Aber IMHO kommt es meist darauf an recht zügig einen Random-Wert zu bekommen der in gewissen Grenzen liegt.
Und mir ist es ehrlich gesagt humpe, ob er gewisse Wahrscheinlichkeiten nicht so ganz erfüllt. Hauptsache flott.

Als brauchbare Näherung reicht es für meine Zwecke völlig aus.

[Dr. Irata]

... mit dem größeren Vorfilter passt!

Schon cool, was man aus so einer "kleinen" Sache alles machen kann!!
Was mich ein wenig stört ist allein die Tatsache, daß die meisten Ansätze die eigentlichen Random-Zahlen verändern... letztlich wartet man auf Zahlen zwischen 0-5 (oder andere Bereiche) und schneidet alles andere weg.
Ob das mathematisch, statistisch korrekt ist??

Mein letzter ("toller") Ansatz behebt dieses Dilemma eindeutig:

Code: Alles auswählen

random = 53770
zufall	.by 00
tmp	.by 00

		mva random zufall
	
		#if .byte zufall<#43
		mva #0 tmp
		#end
		#if .byte zufall>=#43 .and .byte zufall<#86
		mva #1 tmp
		#end
		#if .byte zufall>=#86 .and .byte zufall<#128
		mva #2 tmp
		#end
		#if .byte zufall>=#128 .and .byte zufall<#170
		mva #3 tmp
		#end
		#if .byte zufall>=#170 .and .byte zufall<#212
		mva #4 tmp
		#end
		#if .byte zufall>=#212 
		mva #5 tmp
		#end
		
		lda tmp

[pps]

Wenn man das nun umgekehrt abfragt, kann man auch deutlich kürzeren Code erzeugen...

[Dr. Irata]

wie würdest du das dann abfragen?

[pps]

wie würdest du das dann abfragen?

Code: Alles auswählen

random = 53770

                ldy #0
		lda random
                cmp #212
                bcs zero
                cmp #170
                bcs one
                cmp #128
                bcs two
                cmp #86
                bcs three
                cmp #43
                bcs four
;five
                iny
four            iny
three           iny
two             iny
one             iny
zero            tya

[Dr. Irata]

der Code ist chic

[cas]

Super spannende Diskussion.

Hat jemand Motivation daraus einen kleinen Artikel fuer das Magazin zu machen?

[Dr. Irata]

... ja ich finde auch, daß die Diskussion hier mega spannend und befruchtend ist! Was man alles lernen kann...

Wenn sich keine findet, würde ich daraus einen kleinen Artikel machen und das von 0-5 auf 0-7 erweitern, da man dann noch einen anderen Ansatz diskutieren könnt

Aber wie gesagt, wenn jemand anderes das Thema gerne präsentieren möchte - gerne!!

[Erhard]

Hi,

ich muß ehrlich gestehen, daß ich nie gedacht hätte, daß das Generieren einer Zufallszahl in Assembler so schwierig ist.

Einige der angedachten Lösungen funktionieren nicht oder nicht richtig, ein weiterer Teil ist handgeschnitzt auf den zu erzielenden Wertebereich und den größten Teil hab ich auf die Schnelle beim Durchlesen nicht mal verstanden.

Ich wäre vermutlich sehr faul gewesen und hätte es eher wie in BASIC gemacht und einfach die Fließkommaroutinen verwendet und dann sowas wie MAXZAHL*RANDOM/255.

Von den benötigten Zyklen sprengt das natürlich jeden Rahmen und ist für die Verwendung innerhalb zeitkritischer Operationen völlig untauglich.

Dann hab ich gerade noch überlegt, daß Integer Multiplikation und Division beschränkt auf 16 Bit ja schneller sein müßte als FP. Aber allein die Erläuterung der bestehenden Algorithmen ist so abschreckend abgehoben - ne danke.

Vielleicht könnte man für Dezimalzahlen mit wenigen stellen sowas machen:

Man nehme einen zehnseitigen Würfel (0-9). Den würfelt man für jede Dezimalstelle und setzt aus den Ergebnissen die Zahl zusammen. Die Routine für 0-9 wäre dann fix. Nachteilig wäre, daß pro Dezimalstelle ein zusätzlicher Durchlauf benötigt wird und daß vielleicht eine Routine abschließend führende Nullen ausblenden muß.

Da fällt mir gerade auf: gewünscht waren ja eine Zufallszahl von 0-5 oder eine mit max 23. Das geht mit so einem zehnseitigen Würfel auch wieder nicht.

Bin echt gespannt, wie es in dem Thema weiter geht.

CU, Erhard

[Dr. Irata]

... ich werde in den nächsten Tagen noch einen weiteren Ansatz hier posten. Theoretisch mathematisch recht einfach und oben schon angedeutet will ich die Zufallszahl von 0-255 - also das, was RANDOM ausgibt durch 43 teilen.
Warum 43? die 43 steckt 5,93 mal in 255 drin - also bekomme ich durchs teilen Werte zwischen 0 und 5,9 und das auch ganz gleichmäßig verteilt!
Nun ist teilen in Assembler ja bekanntlich nicht so einfach, aber wir haben ja einen Computer!
Teilen einer Zahl a durch eine andere Zahl b ist ja nichts anderes, als von a solange b abzuziehen, bis wir 0 oder kleiner bekommen.
Wenn ich also von der Zufallszahl 43 subtrahiere und direkt in einen Minusbereich komme (Overflow), dann ist die Routine schon fertig und wir bekommen das Ergebnis 0 .
Wenn kein Overflow subtrahieren wir weiter, erhöhen das Ergebnis jeweils um 1 bis der Overflow kommt.
Relativ einfach also.... daraus kann man eine feine kleine Routine machen. Braucht man höhere Zahlen, teilt man nicht durch 43, sondern durch kleine Zahlen...

Gruß
Peter

[Dr. Irata]

na gut...
hab es gleich gemacht

Code: Alles auswählen

		lda #43 
		sta tmp
		
		ldx #0
		lda random
		sbc tmp
		bvs exit
		inx
		sbc tmp
		bvs exit
		inx
		sbc tmp
		bvs exit
		inx
		sbc tmp
		bvs exit
		inx
		sbc tmp
		bvs exit
		inx		
	exit	txa

[Dr. Irata]

hier noch etwas schlanker angepasst:

Code: Alles auswählen

	
		ldx #255
		lda 53770
		sec
lp		inx
		sbc #43
		bcs lp
		txa

[Dietrich]

Vorsicht: Das Overflow-Flag ist für Arithmetik im Zweier-Komplement (Zahlenbereich von -128 bis +127) vorgesehen. Daher funktioniert das so im allgemeinen nicht. Beispiel: Nach lda #129 : sec : sbc #2 ist das Overflow-Flag gesetzt, da 129 im Zweier-Komplement -127 entspricht und wenn man da noch 2 abzieht, kommen wir auf -129, was nicht mehr im Zweier-Komplement darstellbar ist, d.h. die CPU setzt das Overflow-Flag.

Ersetze einfach bvc durch bcs, dann klappt es, da nun das Carry-Flag entscheidet (ist auch eine Art Overflow, aber im Bereich 0 bis 255, was hier ja gewünscht ist).

[Dr. Irata]

... ich habe das gerade mal mit bcs getestet und entsprechend den Code geändert!
Danke für den Hinweis! Ich hatte mich beim testen auch schon über komische Effekte bei höheren Subtraktionen gewundert ab 128

Mit den ganzen branch-Befehlen bin ich noch nicht so im Detail auf du-und-du - da muss ich noch nachlegen, dann kann ich in kritischen Programmteilen auch besser und sinnvoller meine #if Anweisungen reduzieren!

[Dietrich]

Ja, ich hatte damals (vor knapp 40 Jahren) auch etwas gebraucht, bis ich das verstanden hatte - war eine spannende Zeit damals.

Die wichtigsten Branch-Befehle sind BEQ und BNE (oft in Verbindung mit CMP/CPY/CPX), dann BCC und BCS (ebenso und mit ADC/SBC), dann mit Abstand BPL und BMI (meist für kurze Schleifen mit 0-Durchlauf: ldy #6 : loop ... dey : bpl loop, das zählt Y von 6 bis 0 einschließlich). BVC und BVS benutze ich nur höchst selten (fast nur in Verbindung mit BIT, um Bit #6 zu testen).

[LarsImNetz]

@Dietrich, vielleicht sollten wir für das Thema lda/cmp/bxx ein neues Thema öffnen?

[Dr. Irata]

super Idee

[Olix]

... wie gewünscht habe ich einen entsprechenden neuen Thread begonnen ...