Zufallsgenerator - ungleiche Startwerte erzeugen

[Muraer (Gast)]

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

[Detlev T. (detlevt)]

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.

[Gast (Gast)]

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

[Johann L. (gjlayde)]

Eine weitere Möglichkeit:

http://www.roboternetz.de/wissen/index.php/Zufallszahlen_mit_avr-gcc

[Muraer (Gast)]

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

[d.k.(gast) (Gast)]

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.

[Jörg (Gast)]

@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

[Muraer (Gast)]

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

[Jens_E. (Gast)]

" ... 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 ....

[Simon K. (simon)]

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

[Johann L. (gjlayde)]

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