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
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
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.
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
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
> 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 | }
|
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
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?
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.
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
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
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
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
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.