Forum: Mikrocontroller und Digitale Elektronik Gleichverteilte Zufallszahlen in bestimmtem Bereich?


von Bartholomäus S. (sam_vdp)


Lesenswert?

Hallo allerseits,

ich baue gerade einen kleinen Elektrowürfel und brauche dafür 
Zufallszahlen zwischen 1 und 6, die natürlich gleichverteilt sein 
sollen. rand()%6+1 fällt daher flach, siehe:
http://members.cox.net/srice1/random/crandom.html
("Do NOT use y = rand()  %  M;
as this focuses on the lower bits of rand(). For linear congruential 
random number generators, which rand() often is, the lower bytes are 
much less random than the higher bytes.")

Alle anderen Algorithmen die zu diesem Thema im Web zu finden sind 
nutzen Fließkommaarithmetik, was ich gerne vermeiden möchte.
Was gibt's da für Möglichkeiten?

Vielen Dank im Voraus und beste Grüße,
Bartl

von Michael U. (Gast)


Lesenswert?

Hallo,

wenn es wirklich ein Würfel ist, muß ja jemand würfeln...

Einen Zähler mit entsprechend hohoer Zählfreuenz starten, wenn der 
Würfeltaster gedrückt wird, den Wert benutzen, den der Zähler hat, wenn 
losgelassen wird.

Früher war es ein 7400 als Oszillator und Tasten-Flip-Flop, ein 
TTL-Zähler, ein 7-Segment-Decoder.

Keine Ahnung, wieviel µC man heute dafür nimmt. ;)

Gruß aus Berlin
Michael

von Bartholomäus S. (sam_vdp)


Lesenswert?

Ja, da würfelt schon jemand und dein Verfahren verwende ich um den 
Zufallsgenerator zu sähen (oder wie auch immer man das nennt ^^).
Allerdings würde ich danach gerne die rand() Funktion nehmen, weil ich 
mir nicht so sicher bin, wie's mit der Zufälligkeit von mehreren Werten 
aus der "Zählermethode" bestellt ist.

von Peter D. (peda)


Lesenswert?

Ich habs mal gemacht, es ist alles andere als einfach, hat ne Weile 
gedauert, ehe es funktionierte.

Man nimmt am besten einen Timer, der genau gleich lange Intervalle 
erzeugt und in diesen wird dann der Taster als unabhängiges zufälliges 
Ereignis abgefragt.

Zusätzlich habe ich noch nen Pseudowürfel im Vordergrund laufen, damit 
der Eindruck entsteht, man könnte den Würfel zur richtigen Zeit stoppen.

http://home.tiscali.de/peterd/appl/soft/c51/dice/index.htm


Peter

von Bartholomäus S. (sam_vdp)


Lesenswert?

So hatte ich es gerade eben ausprobiert (16-bit Zähler zählt mit 8MHz 
hoch und wird beim loslassen des Tasters modulo 6 genommen), aber damit 
sind recht komische Zahlen rausgekommen. Allerdings habe ich schon zu 
lange keine Stochastik mehr gehabt, um sinnvoll nachrechnen zu können, 
ob ich einen Laplacewürfel gebaut habe... Ich werde nochmal eine 
Versuchsreihe starten.

Vielen Dank für Tipps und beste Grüße,
Bartl

von yalu (Gast)


Lesenswert?

> Allerdings würde ich danach gerne die rand() Funktion nehmen

Kannst du auch!

Der Zufallsgenerator in der AVR-Libc ist komplexer aufgebaut als der
in deinem Link beschriebene "congruential random number generator" und
weist m. W. dessen Problem der wenig zufälligen niederwertigen Bits
nicht auf.

Deswegen ist
1
rand() % 6 + 1
prinzipiell schon ok.

Der einzige Fehler in dieser Lösung liegt darin, dass die Zahlen 1 und
2 etwas häufiger als die Zahlen 3 bis 6 erscheinen, da RAND_MAX+1
(=2**15) nicht durch 6 teilbar ist:

P(1) = P(2)               = 5452 / 32768 ~ 0.1666870
P(3) = P(4) = P(5) = P(6) = 5451 / 32768 ~ 0.1666565

Das kann, wenn FP-Berechnungen vemieden werden sollen, dadurch
korrigiert werden, dass der Wertebereich der ursprünglichen
Zufallszahlen auf die nächstkleinere durch 6 teilbare Zahl begrenzt
wird:
1
int roll_dice() {
2
  int r;
3
  while((r = rand()) >= (int)(((unsigned long)RAND_MAX + 1) / 6 * 6));
4
  return = r % 6 + 1;
5
}

  

von Peter D. (peda)


Lesenswert?

Bartholomäus Steinmayr wrote:
> So hatte ich es gerade eben ausprobiert (16-bit Zähler zählt mit 8MHz
> hoch und wird beim loslassen des Tasters modulo 6 genommen), aber damit
> sind recht komische Zahlen rausgekommen.

Ja, so gehts nicht, das ist nicht zufällig.

Je nach Befehl in der Mainloop hast Du eine unterschiedliche 
Interruptlatenz und damit unterschiedliche Häufigkeiten. Ich hatte es 
auch probiert, es war absolut nicht brauchbar.

Deshalb habe ich für den Abfragetimer und den Timer der Mainloop 2 
unterschiedliche Primzahlen genommen.


Eine Rand-Funktion hat der Keil C51 auch, aber die wird ja beim 
Einschalten initialisiert, d.h. man hätte nach einem Batteriewechsel 
immer die gleiche Folge von Pseudozufallswerten. Daher habe ich die 
echte Zufallsfunktion vorgezogen.


Peter

von zigmi (Gast)


Lesenswert?

Hallo,
sehr interessante Diskussion.
Das mit dem Timer und der resultierenden schlechten Statistik hab ich 
nicht genau verstanden.
Habt Ihr
- einen freilaufenden (16bit, 8Mhz ) Timer, der dann bei Tastendruck 
abgefragt und %6 genommen wird oder
- startet Ihr den Timer jedesmal neu bei Tastendruck und messt quasi die 
Tastendruckdauer und nehmt die dann %6?


von yalu (Gast)


Lesenswert?

Autsch, jetzt sehe ich gerade, dass Bartholomäus gar nicht geschrieben
hat, um welche Controller es hier geht. Ich hatte da noch irgendwas
aus einem anderen Thread im Kopf.

Falls es also nicht um AVR mit GCC und AVR-Libc geht, dann betrachtet
mein Post weiter oben als gegenstandslos.

Oder doch nicht ganz: Falls die auf dem verwendeten Controller
eingesetzte C-Bibliothek tatsächlich eine problembehaftete
rand-Funktion enthält, kann man doch einfach diejenige aus der
AVR-Libc kopieren (Open Source mit wenig restriktiver Lizenz).

Generell verstehe ich nicht ganz, warum sich hier alle auf die
Zählermethode einschießen, bei der es trotz des unbestritten echt
zufälligen Verhaltens offensichtlich nicht ganz leicht ist, die
Gleichverteilung der erzeugten Zufallszahlen nachzuweisen. Diese ist
bei ein Würfelspiel aber eines der Haupkriterien und für einem
Pseudozufallsgenerator mathematisch bewiesen.

Der Startwert kann, wie von Bartholomäus bereits realisiert, per
Zählermethode generiert werden, um gleiche Sequenzen zu vermeiden. Da
die Zählermethode nur ein einziges mal beim Einschalten angewandt
wird, beeinflussen ungünstige Interruptlatenz- und Befehlausführungs-
zeiten die Gleichverteilung nicht negativ.

von Bartholomäus S. (sam_vdp)


Lesenswert?

Also, es geht um einen AtTiny2313 mit AVRGCC Entwicklungsumgebung.

@zigmi: > einen freilaufenden (16bit, 8Mhz ) Timer, der dann bei 
Tastendruck
abgefragt und %6 genommen wird
So habe ich es gemacht.

@yalu: Ich würde eigentlich auch die rand() Methode bevorzugen, 
allerdings stellt sich dabei das Problem, dass mein Würfel nur "an" ist, 
wenn auch tatsächlich gewürfelt wird (weil ich das ganze mit einem 
Spannungsregler an einer 9V Batterie betreibe kann ich keinen Sleepmodus 
verwenden).
Das heißt, ich müsste den letzten Wert jeweils in EEPROM schreiben. Wo 
ich gerade darüber nachdenke, ist das wahrscheinlich die beste Option. 
Mit 128 byte und jeweils 100000 Schreibzyklen sollte das eigentlich 
ausreichen.

Beste Grüße,
Bartl

von Sven S. (Gast)


Lesenswert?

Wiso eigentlich einen freilaufenden Timer nehmen. Ich würd einen nehmen 
der sich bei 5 wieder auf 0 setzt und bei einem Tasten interrupt 
abgefragt wird. Ist dann auch auf jeden fall Zufällig, bei einer 
Frequenz von 8mhz.

gruss sven

von Peter D. (peda)


Lesenswert?

zigmi wrote:

> Das mit dem Timer und der resultierenden schlechten Statistik hab ich
> nicht genau verstanden.

Mal ein einfaches Beispiel:

Du hast nen Mainloop aus nur einem Sprungbefehl (2 Zyklen), dann kann 
der externe Interrupt nur nach Ende des Befehls auslösen und Du hast je 
nach Startwert nur gerade oder ungerade Timerwerte.

Ideal für Zufallswerte wäre es, wenn jeder Befehl nur einen Zyklus 
dauert.

Oder man macht es so wie ich, daß nicht jeder Zyklus, sondern ein 
wesentlich größeres Intervall (Primzahl) den Zählwert ändert und dabei 
den Pin einliest.


Peter

von Bartholomäus S. (sam_vdp)


Lesenswert?

Ich habe gerade die EEPROM Routinen fertig gestellt und benutze jetzt 
die random() Funktion von der libc und speichere jeweils den letzten 
Wert. Für einen richtig umfangreichen Test fehlt mir gerade der Nerv, 
aber nach etwas über 100 "Würfen" siehts relativ gut aus.

Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.