Forum: Mikrocontroller und Digitale Elektronik Zufallszahl erzeugen


von Sascha (Gast)


Lesenswert?

Hallo!

Wie erzeugt man eigentlich Zufallszahlen?

Ich möchte jetzt nicht wissen, wo es irgendwo eine Bib-Funktion gibt,
die sowas macht, sondern ich möchte so eine Funktion selber
implementieren.

Der Hintergrund: Ich bin gerade dabei mir ein Videospiel selber zu
bauen. Ich greife dabei nicht auf irgendeinen MC zurueck, sondern
verwende meinen eigenen Prozessor, der (wenn er mal fertig ist - happy
debugging) in einen CPLD gebrutzelt wird.

Desshalb muss ich mir so eine Routine selber schreiben.

Ich kann mir da überhaupt nicht vorstellen, wie man eine Zufallszahl
erzeugt. Vielleicht kann mir jemand auf die Sprünge helfen?

von Jürgen Schuhmacher (Gast)


Lesenswert?

Einen sehr schnellen Zähler mit einem von einem aeusseren Einfluss
abhängigen Intervall abfragen. Der Zähler muss genügend oft loopen. Bei
einem AVR würde ich das Rauschen eines offenen AD-Eingangs heranziehen.

von Karl H. (kbuchegg)


Lesenswert?

echte Zufallszahlen kannst du in einem Rechner nur dann
erzeugen, wenn du irgendeine Hardware hast, die sie
dir liefert, zb. wird oft das Rauschen von irgendwelchen
Dingen benutzt um daraus Zufallszahlen abzuleiten.

Hast du sowas aber nicht zur Verfügung, dann bleibt dir nur
der Weg über Pseudozufallszahlen. Das ist eine Rechenvorschrift,
die in der Lage ist eine Folge von Zahlen zu generieren, deren
statistische Eigenschaften denen von echten Zufallszahlen
möglichst nahe kommen. Gute Algorithmen sind dabei erstaunlich
schwer zu finden, sodass ich dir nur davon abraten kann selbst
einfach eine Formel zu benutzen. Weiters kommt hinzu: gute
Zufallszahlengeneratoren sind erstaunlich aufwändig, sodass
man immer die Frage des Laufzeitaufwandes berücksichtigen
muss.

Eine gerne benutzter Art von Generator sieht in C zb so aus

http://www.mikrocontroller.net/forum/read-1-401097.html#new

von Michael U. (Gast)


Lesenswert?

Hallo,

für ein Videospiel könnte die Routine reichen, die ich für ein
Kaminfeuer im Modellpuppenhaus meiner Frau benutze...
Beruht auf rückgekoppeltem Schieberegister, liefert eine durchaus
brauchbare Folge.
Du mußt Dir allerdings einen zufälligen Startwert beschaffen, dafür
geht aber zum Beispiel ein Counter, der ab Reset zählt bis die erste
Taste gedrückt wird oder ähnliches.

Die Routine stammt irgendwo aus den Weiten des WWW, ich habe eine
ähnliche mal vor -zig Jahren auf einem Z80 benutzt.

Gruß aus Berlin
Michael

von Hagen (Gast)


Lesenswert?

Für ein CPLD werden die Shift Register wohl die beste Wahl sein. Suche
mal nach LFSR -> Linear Feedback Shift Register oder auch nach SR-LFSR.
Auf einem CPLD dürfte sowas sehr effizient umzusetzen sein, so lange man
das/die Polynom/e hardcoded reinbaut.

Für Spiele und auch viele andere Anwendung sind die
Pseud-Zufalls-Generatoren den echten RNGs zu bevorzugen. Diese PRNGs
sind nämlich reproduzierbar im Gegensatz zu echten RNGs, und dies ist
ein enormer Vorteil bei der Entwicklung.

Um dann zur Laufzeit immer andere Sequenzen zu erzeugen musst du nur
beim Startup das LFS-Register mit einem Wert initalisieren. Dieser Seed
könnte im EEPROM abgespeichert werden. Dazu lade ich meistens diesen
Seed beim Startup aus dem EEPROM und speichere diesen im LFSR. Dann
wird der gleiche Seed einfach verändert, zb. Seed := (Seed*Seed) +1 mod
2^31 und dieser Wert als nächster Startwert ins EEPROM gespeichert. Das
läuft alles im Startup ab.

Gruß Hagen

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.