Zufallsgenerator - ungleiche Startwerte erzeugen

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.

Eine weitere Möglichkeit:

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

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

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 ;-))

1

// Ein irreduzibles Polynom vom Grad 15 über F_2, F_2 = Z mod 2Z

2

// F_{2^15} ist isomorph F_2[x] mod (POLY*F_2[x])

3

#define POLY 0xe125 // 1 + x^2 + x^5 + x^8 + x^13 + x^14 + x^15

4

5

// ein zyklischer Erzeuger von (F_{2^15})^* in der gewählten Darstellung

6

#define ROOT 0x2200 // x^9 + x^13

7

8

// Grad der Körpererweiterung

9

#define DEGREE 15

10

11

// Prinzipiell geht das auch für 8-, 32- oder 64-Bit Werte, 

12

// dann ist aber der Primkörper und der zyklischen Erzeuger

13

// seiner Einheiten neu zu bestimmen

14

typedef unsigned short poly;

15

16

poly pprod (poly, poly);

17

18

// seed darf nicht 0 sein mod POLY, kann aber ansonsten auch auf andere

19

// Startwerte initialisiert werden

20

static poly seed = 1;

21

22

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

23

24

/**

25

 * Berechnet c = a*b mod p

26

 */

27

poly pprod (poly a, poly b)

28

{

29

  const poly mask = MASK (DEGREE);

30

  poly c = 0;

31

32

  while (b)

33

  {

34

    // Ist Bit i in b gesetzt?

35

    if (b & 1)

36

      c ^= a;    // dann c = c + a * x^i

37

38

    a <<= 1;    // a = a*x

39

    if (a & mask)  // a = a mod p

40

      a ^= POLY;

41

42

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

43

  }

44

45

  return c;

46

}

47

48

// Liefert eine Pseudo-Zufallszahl x mit 1 <= x <= 2^DEGREE-1 = 32767

49

unsigned short prandom(void)

50

{

51

  return (unsigned short) (seed = pprod (seed, ROOT));

52

}

53

54

// Liefert eine Pseudo-Zufallszahl x mit 1 <= x <= 2^23-1 = 8388607

55

unsigned long prandom23(void)

56

{

57

  return prandom() ^ ((unsigned long) prandom() << 8);

58

}

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

Johann