www.mikrocontroller.net

Forum: Mikrocontroller und Digitale Elektronik Zufallszahlen für Würfel


Autor: cody (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo alle zusammen,

ich muß mich mal an Euch wenden, da ich im Moment nicht so richtig 
weiterkomme:

Ich möchte eine Schleife in Assembler programmieren für den ATMega8, die 
Zufallszahlen ausgibt.  Als Zufallszahlen werden hier an einem Port 
einfach Kombinationen von Low und High ausgegeben, mit denen man dann 
die Würfelpunkte durch LED's darstellt.

Das Problem ist, ich bekomme einfach zu viele gleiche Werte 
hintereinander.
Das ganze läuft im Moment so ab:

Durch Betätigung eines Tasters läuft eine Schleife an. Der Zählerstand 
wird dabei immer beim Start vom Wert 6 aus vermindert bis 0. Diese 0 
wird abgefragt und wenn ja, wird der Zählerstand wieder auf 6 gebracht 
usw.
Die Schleife läuft solange, bis der Taster wieder losgelassen wird.

Vor  Abfrage des Tasters wird natürlich der Ausgabewert (momentaner Wert 
der Schleife) in ein Register geladen. Das alles funktioniert ja auch. 
Nun sollte man meinen, mit einer Taktfrequenz von 4 MHz wird die 
Schleife immer irgendwo zufällig verlassen. Das scheint aber nicht so. 
Woran könnte denn das liegen?

In einem Buch von G. Schmitt war die Konzeption so, daß die Schleife 
immer läuft, und ich mit dem Tastendruck dann irgendwo abbreche.

In meiner Konstruktion ist es ja so, daß ich mit dem Tastendruck erst 
die Schleife anlaufen lasse, gewöhnlich eine Zeit da auf dem Taster 
bleibe und dann mit dem loslassen des Tasters den Wert erhalte.

Wie seht Ihr das?

Autor: Stefan Oberpeilsteiner (stefano)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo,

Eventuell hast du den Tastereingang nicht "entprellt" und daher ist die 
Zeit in Wirklichkeit immer circa gleich lang.

lg Stefan

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
cody wrote:
> Wie seht Ihr das?

Ohne Code sehen wir gar nichts.

Autor: AVRFan (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ja, die Taste muss unbedingt entprellt werden, sonst stoppt die 
Schleife von Dir unbemerkt schon nach z. B. 1 ms (Zeitpunkt des ersten 
Prellers) und Deine Zufallszahlen sind Murks.

Ansonsten hier mal ein paar "echte" Zufallszahlen von 1 bis 6.  Wenn Du 
die studierst, wirst Du feststellen, dass das zwei- oder dreimalige 
Aufeinanderfolgen desselben Werts durcaus nicht so selten vorkommt, wie 
man vielleicht vermuten würde.  Vielleicht hilft Dir das, den Output 
Deines Programms besser beurteilen zu können (ist er am Ende doch 
korrekt?)

451466531525614326266421664161546646615132532534465441252221
552466662315233363352453151635334525126613511365521652422314
324642256522521164614636244452445252254323425665225352462241
144241216155423263223546563411454435226244423221442246642141
163411261356351244136563254521245514366342425412534654435442
111123631342616221524146511525622544315641654144662256133353
323456144646526166546634635163363631361661264531356542255152
261165555321364544222323631324331246265221221156131131655223
634566336352641454563513551521655425166612655265635221251131
122535234425523121411664336556546441562125266321126465311652
311413124655355243222261564253124644465151455236532162423263
235156621255135415363461324134452446254142253261321361544654
311431451241141355633635662641131426525131216142636122266655
366464313652233165545453216646465144611126425524611236452623
414123353426511514336514465211153311216432442462244241414412
144666526421365156554245432462153353514455632662126226526316

Autor: zebrafalke (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Wie hast du denn echte Zufallszahlen hingekriegt? --> 
http://de.wikipedia.org/wiki/Pseudozufall

Autor: AVRFan (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ich hab eine Tüte mit Konfetti (gut, dass gerade Fasching iss) in sechs 
verschiedenen Farben genommen, mit Schwung in die Luft geworfen (bis 
hierhin wars noch einfach), die Fitzelchen anschließend mit verbundenen 
Augen auf dem Boden in eine Reihe gelegt (stöhn), und dann in den 
Rechner getippt: rot = 1, gelb = 2... (ächz)

Zufrieden? ;-)

Und trotzdem hab ich noch "echte" in Anführungszeichen gesetzt... lach

Autor: mr.chip (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Du hättest es dir auch einfach machen und bei ein paar Elektronen den 
Spin oder sonst irgend eine Eigenschaft messen können :-)

Autor: Peter Dannegger (peda)
Datum:

Bewertung
0 lesenswert
nicht lesenswert

Autor: Peter X. (vielfrass)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Habe hier eine kleines Programm für Rauschen/Zufallszahlen.
Einmal in Assmbler für MSP430... (ein 16 Bit'er)
            mov     #004C1h,R12
            mov     #01DB7h,R13
            mov     #0,R14
            mov     #1,R15       ;Startwert 0x00000001
kein_xor
            nop                  ;nop's gleichen Laufzeit aus
            nop
            nop
            nop
Mainloop
            mov.b   R15,&P1OUT   ;R15 unteres Byte an Port1 ausgeben
            rla     R15
            rlc     R14
            jnc     kein_xor
            xor     R12,R14
            xor     R13,R15
            jmp     Mainloop

und jetzt in C
  unsigned long int my_random = 0x80000000;

  while (1)
  {
    if (my_random & 0x00000001)
    {
            my_random >>= 1;
            my_random ^= 0xEDB88320;
    }
    else
    {
            my_random >>= 1;
    }
    P1OUT = my_random;
  }   
0xEDB88320 bitreverse = 0x04C11DB7

Autor: Peter X. (vielfrass)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Uups, noch was vergessen:

1.  Ein oder mehrere Byte's der Zufallszahl mit 6 malnehmen.
Vom Ergebnis nur das obere Byte behalten.
INC Oberes_Byte und wir haben eine Zufallszahl von 1 bis 6

2.  Das Zufallszahlenprogramm liefert natürlich immer die selbe 
Zahlenfolge, die aber (2^32) - 1 lang ist. Jemand mit sehr gutem 
Gedächnis könnte die Zahlenfolge auswendig lernen und beim Würfeln 
schummeln.
Deshalb den Würfel so bauen, das der Zufallszahlengenerator frei läuft 
und manuell durch Tastendruck gestoppt werden muss.

Autor: AVRFan (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>1.  Ein oder mehrere Byte's der Zufallszahl mit 6 malnehmen.
>Vom Ergebnis nur das obere Byte behalten.
>INC Oberes_Byte und wir haben eine Zufallszahl von 1 bis 6

Eben so sollte man es lieber nicht machen. Jemand, der Deinen Würfel 
einem Härtetest unterziehen würde (10000 Runs über Nacht sind kein 
Problem, wenn man den Taster mit einem PC-gesteuerten Relais 
überbrückt), würde nämlich feststellen, dass er gezinkt ist.  Denn die 
Würfelzahlen 3 und 6 erscheinen mit der Wahrscheinlichkeit 1/256 weniger 
oft als die 1, 2, 4 und 5 (bei Auswertung eines Zufallszahlen-Bytes). 
Den Grund dafür kannst Du Dir selbst überlegen.  Was würdest Du auf den 
Vorwurf, dass der Output Deines Würfelsimulators nicht gleichverteilt 
ist, antworten?

>2.  Das Zufallszahlenprogramm liefert natürlich immer die selbe
>Zahlenfolge, die aber (2^32) - 1 lang ist. Jemand mit sehr gutem
>Gedächnis könnte die Zahlenfolge auswendig lernen und beim Würfeln
>schummeln.

So ist es.

>Deshalb den Würfel so bauen, das der Zufallszahlengenerator frei läuft
>und manuell durch Tastendruck gestoppt werden muss.

lach... na klar... fragt sich nur, warum es dann nicht auch eine simple 
Schleife 1, 2, 3, 4, 5, 6, 1, 2, 3, 4, 5, 6, 1, 2, 3... genauso tut, wie 
von cody realisiert?  Damit läßt sich die Gleichverteilung auch sehr 
leicht erreichen.

Autor: Christian L. (lorio)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>>Deshalb den Würfel so bauen, das der Zufallszahlengenerator frei läuft
>>und manuell durch Tastendruck gestoppt werden muss.
>
> lach... na klar... fragt sich nur, warum es dann nicht auch eine simple
> Schleife 1, 2, 3, 4, 5, 6, 1, 2, 3, 4, 5, 6, 1, 2, 3... genauso tut, wie
> von cody realisiert?  Damit läßt sich die Gleichverteilung auch sehr
> leicht erreichen.

Klar ist eine Pseudozufallszahlengeneration (theoretisch) sicherer, aber 
mal ehrlich: Angenommen der Zufallszahlengenerator läuft mit 1MHz, dann 
müsste man auf die Mikrosekunde genau drücken, damit man gewollt eine 
bestimme Zahl herbei führt. Für nen lockeren Spieleabend dürfte das 
reichen, meine ich.

Klar, für eine Spielhalle müsste man einiges an Vorschriften und 
Sicherheitsrichtilinien beachten wie starke Pseudozufallsgeneration, 
Schutz gegen erneutes Drücken, etc.

Gruß
Christian

PS.: Ich hätte die aufgabe spontan mit einem NE555er und nem Zähler 
gelöst...
Obwohl es ja schon fast billiger ist nen Tiny zu benutzen statt den 
ganzen BCD->7-Segment Encodern ^^

Autor: Detlev T. (detlevt)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@cody
Mit mehr Informationen bräuchte ich meine Kristallkugel nicht zu 
bemühen. Welche Zahl kommt denn häufiger? War es die 6? Wie groß war die 
Stichprobe?

Da du bei 0 wieder zurück auf 6 gehst, verbringt der µC vergleichsweise 
viel Zeit bei der Abarbeitung dieser Bedingung. Die Wahrscheinlichkeit 
des Abbruchs vor (und damit bei) einer 6 ist also deutlich höher als bei 
den anderen Zahlen. Du müsstest die Schleife so programmieren, dass 
diese Zeit für alle Zahlen gleich ist (oder einen Hardware-Timer 
bemühen)

Autor: Marcel (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Wenn du den "Würfel" dort weiter laufen lässt wo er das letzte mal 
angehalten hat macht sogar das Prellen des Tasters nichts mahr aus.
Detlev T.'s gedanke ist auch sehr gut und muss auch beachtet werden.

Autor: AVRFan (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>Angenommen der Zufallszahlengenerator läuft mit 1MHz, dann
>müsste man auf die Mikrosekunde genau drücken, damit man gewollt eine
>bestimme Zahl herbei führt.

Richtig, das gezielte Erwirken einer bestimmten Zahl ist durch das 
rasend schnelle Durchlaufen der Schleife ausgeschlossen. Damit ist aber 
noch nicht die Gleichverteilung der Zahlen 1 bis 6 garantiert.  Um 
diese zu erreichen, muss man sogar höllisch aufpassen - sonst bekommt 
man einen Würfel, bei dem manche Zahlen öfter erscheinen als andere.

Man könnte z. B. auf die Idee kommen, statt nach dem Schema "1...6, 
1...6, 1..." ein Register einfach "0...255, 0...255, 0..." zählen zu 
lassen, und nach dem Loslassen der Taste seinen Wert modulo 6 zu nehmen 
(plus Addition von 1).  Das Ergebnis?  Die 1, 2, 3 und 4 würden etwas 
häufiger auftreten als die 5 und 6!

>Da du bei 0 wieder zurück auf 6 gehst, verbringt der µC vergleichsweise
>viel Zeit bei der Abarbeitung dieser Bedingung. Die Wahrscheinlichkeit
>des Abbruchs vor (und damit bei) einer 6 ist also deutlich höher als bei
>den anderen Zahlen. Du müsstest die Schleife so programmieren, dass
>diese Zeit für alle Zahlen gleich ist (oder einen Hardware-Timer
>bemühen)

Exakt.  Dem muss unbedingt Rechnung getragen werden.  Übrigens sollte 
man den Ausbruch aus der Schleife auch blos nicht mit Interrupts (z. B. 
Taste an INT0 mit Flankenerkennung) realisieren.  Da die Abarbeitung der 
Instruktionen unterschiedlich lange dauert (z. B. 'inc' 1 Taktzyklus, 
'rjmp' aber 2), ein Sprung zum Interruptvektor jedoch nur nach 
vollständig ausgeführtem Befehl erfolgt, kann man sich auch damit wieder 
eine Ungleichverteilung der Zahlen einhandeln.

Autor: Dickmann (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>Da die Abarbeitung der
>Instruktionen unterschiedlich lange dauert (z. B. 'inc' 1 Taktzyklus,
>'rjmp' aber 2), ein Sprung zum Interruptvektor jedoch nur nach
>vollständig ausgeführtem Befehl erfolgt, kann man sich auch damit wieder
>eine Ungleichverteilung der Zahlen einhandeln.

Kapier ich nicht wirklich, gib mal ein Beispiel.

Autor: avrkiller (Gast)
Datum:
Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
Nen Würfel hab ich vor kurzem auch mal programmiert.
Nicht sehr schöner code, funzt aber.

Autor: AVRFan (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>Kapier ich nicht wirklich, gib mal ein Beispiel.

Stell Dir vor, jemand realisiert den Würfel wie folgt.

(1) Damit die Durchlauffrequenz so hoch wie möglich ist, wird Timer1 
ohne Prescaler im CTC-Modus verwendet. Mit passendem Compare-Match-Wert 
zählt er nach dem Start 0, 1, 2, ..., 5, 0, 1, 2, ... 5, 0, 1, 2... mit 
voller Taktfrequenz (8 MHz) durch.

(2) Nach Drücken des Tasters wird Timer1 auf Null gesetzt, um einen 
definierten Startzustand zu gewährleisten. Danach tritt das Programm in 
die angegebene Endlosschleife ein:
clr temp
out TCNT1H, temp
out TCNT1L, temp

Loop:
  nop
  nop
  nop
  nop
  rjmp Loop

(3) Die Würfel-Start-Stop-Taste hängt am externen Interrupt INT0.  Der 
Interrupt ist so konfiguriert, dass er bei einer 
Taste-losgelassen-Flanke getriggert wird.  Im Interrupthandler wird der 
Zählerstand von Timer1 ausgelesen: TCNT1L + 1 ist der Würfelwert.

Fertig.

Was ist dazu zu sagen? Man könnte glauben, das müsse einen äußerst guten 
Würfel ergeben.  Die Wahrheit ist, dass er völlig unbrauchbar wäre, weil 
eine der Zahlen 1 bis 6 niemals erscheinen würde.

Hätte man in der Loop-Schleife statt der 'nop's irgendwelchen Code 
stehen, der z. B. die LEDs während die Taste gedrückt ist blinken läßt, 
wäre der Effekt nicht so drastisch, aber die Zahlen wären wahrscheinlich 
auch nicht völlig gleichverteilt.

Autor: AVRFan (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>Nen Würfel hab ich vor kurzem auch mal programmiert.
>Nicht sehr schöner code, funzt aber.

Der Code in der Schleife ist nicht laufzeitkompensiert. Er wird etwas 
mehr Zeit brauchen, wenn i = 7 ist, denn nur für i = 7 wird die 
Anweisung i = 1 ausgeführt.  Die zugehörige Würfelzahl wird entsprechend 
etwas häufiger auftreten als die anderen. Wenn Du Deinen PC über ein 
geeignetes Interface ein paar tausend mal würfeln und ein Histogramm 
erstellen ließest, würde Dir der längere Balken sofort auffallen.

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.