mikrocontroller.net

Forum: Compiler & IDEs Zufallsgenerator - ungleiche Startwerte erzeugen


Autor: Muraer (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo zusammen,

ich nutze den Zufallsgenerator random() aus der stdlib, um Zufallszahlen 
von 0 bis 42 zu erzeugen (Das Resultat der random-Funktion wird mit 
Modulo zurechtskaliert).

Nun ist es aber so, dass diese Funktion immer dieselbe Zahlenfolge 
rauslässt...

Wie könnte man das biegen, dass das ein bisschen variiert?
Das Ganze läuft auf einem ATmega32. Müsste man wohl das EEPROM zu Rate 
ziehen und da erst kürzlich aufgerufene Startwerte ablegen, und dann die 
random()-Funktion ein paar mal laufen lassen, bis man etwas Neues hat? 
Oder geht das irgendwie einfacher?

Gruss
Mario

Autor: Detlev T. (detlevt)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hängt vom Prozessor ab. srand() mit einem Wert aus dem EEPROM, dass man 
bei jedem Start ändert (z.B. mit dem Ergebnis von rand() ) wäre ein Weg. 
Hat dein Prozessor Zugriff auf eine (gepufferte) Real Time Clock, könnte 
man auch daraus einen Seed-Wert generieren.

Autor: Gast (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Mit den verrauschten LSB eines ADC lässt sich auch ganz gut ein 
Zufallsgenerator bauen.

Autor: Johann L. (gjlayde) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert

Autor: Muraer (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hmm, Okee, das schaut schon vielversprechend aus.
Sehe ich das richtig, dass der Unterschied zwischen rand() und srand() 
darin besteht, dass man bei srand() einen seed-wert vorgeben kann, 
wohingegen rand() immer den gleichen Anfangswert hat?

Gruss und Danke

Mario

Autor: d.k.(gast) (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
korrekt.

rand() ist quasi ein buch mit vielen seiten voll von zufallszahlen.

mit srand(time(NULL)) z.b. gibst du mit der systemzeit eine seite vor, 
wo die zufallszahl dann gezogen wird. ohne srand fängt rand immer bei 
seite 1 an.

Autor: Jörg (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@Muraer,

falls du nicht sehr anspruchsvolle Zufälligkeit brauchst, kannst du
den Modulo-Operator verwenden; ist quasi ein Abschneiden der höheren
Bits. Falls du aber die Qualität der rand()/srand()-Funktionen nicht
einschränken willst, solltest du z.B. rand()*41/RAND_MAX für Werte
zwischen 0..41 verwenden.

Gruss

Jörg

Autor: Muraer (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hmm, die "Qualität" der Zufallsergebnisse spielt nicht so eine grosse 
Rolle, Hauptsache, es kommt nicht immer dieselbe Folge raus.
Aber hab unterdessen eine Lösung gefunden (Roboternetz-Idee)

Gruss und Danke

Mario

Autor: Jens_E. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
" ... buch mit vielen seiten voll von zufallszahlen ... "

glaube ich nicht, würde ja massig Speicher kosten. Die Dinger werden 
errechnet mit XOR-Vergleichen, dann geschoben usw., so wie man auch in 
Assembler eben Zufallszahlen erzeugen würde. Das heißt aber eben, es 
sind immer, wenn auch zufällig wirkend, die gleichen Folgen von Zahlen.

Müsste mal in den header-Dateien nachsehen ....

Autor: Simon K. (simon) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Jens_E. wrote:
> " ... buch mit vielen seiten voll von zufallszahlen ... "
>
> glaube ich nicht, würde ja massig Speicher kosten. Die Dinger werden
> errechnet mit XOR-Vergleichen, dann geschoben usw., so wie man auch in
> Assembler eben Zufallszahlen erzeugen würde. Das heißt aber eben, es
> sind immer, wenn auch zufällig wirkend, die gleichen Folgen von Zahlen.

Das war auch eigentlich nur übertragen gemeint, so wie ich das verstehe. 
Der Standard C-rand hat aber nichts mit XOR zu tun:

Dazu lassen sich relativ viele Seiten im Internet finden, mir fehlt aber 
gerade der geeignete Suchbegriff. Standardmäßig benutzt man Additionen 
und Modulo-Operationen mit Primzahlen.

EDIT: Hier: http://en.wikipedia.org/wiki/Linear_congruential_generator

Autor: Johann L. (gjlayde) Benutzerseite
Datum:
Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
Simon K. wrote:
>
> Dazu lassen sich relativ viele Seiten im Internet finden, mir fehlt aber
> gerade der geeignete Suchbegriff. Standardmäßig benutzt man Additionen
> und Modulo-Operationen mit Primzahlen.
>
> EDIT: Hier: http://en.wikipedia.org/wiki/Linear_congruential_generator

Häufig zu finden, ja. Aber gerade dort, wo Division recht teuer ist 
(etwa auf AVR), gibt es eine recht einfache Alternative. Man arbeitet 
dann nicht auf einem endlichen Körper modulo Prinzahl, sondern auf einem 
endlichen Körper modulo Zweierpotenz. Das hat den Vorteil, daß die 
verwendeten Operationen alle sehr einfach auf Rechenwerken 
implementierbar sind: Addition zweier Werte ist zum Beispiel einfach ein 
XOR (wegen 1+1=0).

Als Beispiel hier eine Implementierung, wie ich sie verwende (Libs 
benutzen kann ja jeder ;-))
// Ein irreduzibles Polynom vom Grad 15 über F_2, F_2 = Z mod 2Z
// F_{2^15} ist isomorph F_2[x] mod (POLY*F_2[x])
#define POLY 0xe125 // 1 + x^2 + x^5 + x^8 + x^13 + x^14 + x^15

// ein zyklischer Erzeuger von (F_{2^15})^* in der gewählten Darstellung
#define ROOT 0x2200 // x^9 + x^13

// Grad der Körpererweiterung
#define DEGREE 15

// Prinzipiell geht das auch für 8-, 32- oder 64-Bit Werte, 
// dann ist aber der Primkörper und der zyklischen Erzeuger
// seiner Einheiten neu zu bestimmen
typedef unsigned short poly;

poly pprod (poly, poly);

// seed darf nicht 0 sein mod POLY, kann aber ansonsten auch auf andere
// Startwerte initialisiert werden
static poly seed = 1;

#define MASK(b)   (((poly) 1) << (b))

/**
 * Berechnet c = a*b mod p
 */
poly pprod (poly a, poly b)
{
  const poly mask = MASK (DEGREE);
  poly c = 0;

  while (b)
  {
    // Ist Bit i in b gesetzt?
    if (b & 1)
      c ^= a;    // dann c = c + a * x^i

    a <<= 1;    // a = a*x
    if (a & mask)  // a = a mod p
      a ^= POLY;

    b >>= 1;        // nächstes Bit von b
  }

  return c;
}

// Liefert eine Pseudo-Zufallszahl x mit 1 <= x <= 2^DEGREE-1 = 32767
unsigned short prandom(void)
{
  return (unsigned short) (seed = pprod (seed, ROOT));
}

// Liefert eine Pseudo-Zufallszahl x mit 1 <= x <= 2^23-1 = 8388607
unsigned long prandom23(void)
{
  return prandom() ^ ((unsigned long) prandom() << 8);
}

Selbst in einer Assembler-Implementierung sind das nur ne handvoll 
Instruktionen.

Johann

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.