Eine Frage, die ich schon lange stellen wollte ;) :

Wie funktioniert ein Zufallsgenerator ?

Und warum muss man den immer initialisieren ? (srand(...))

wenn du den zufallsgenerator nicht initialisierst, liefert er immer die gleiche folge an zahlen. dies kann für das debuggen einer software von vorteil sein.

die meisten zufallsgeneratoren basieren afaik auf der systemzeit. es wird z.b. die systemzeit gemessen, und dann sekunden * minuten / stunden o.ä. gerechnet. die herstellung solcher algorithmen für "zufallszahlen" ist quasi eine eigene wissenschaft und es gibt sicher noch weit mehr wege zufallszahlen zu erzeugen.

sccar

...das is zwar der uebelst gehackteste kleine bastard, den ich je gesehen habe, aber dafuer sauschnell. {Tron}

rand() ist kein Zufallszahlengenerator sondern ein Pseudo-Zufallszahlengenerator (PRNG). Ein PRNG arbeitet zumeist nach einem einfachen Prinzip. Dabei wird ein "Carry" im Hauptspeicher behalten, und bei jedem Aufruf von rand() wird eine Operation (Carry * A) + B ausgeführt. Das Ergebnis wird dann zurückgegeben, und die höherwertigen Bits, die im Ergebnis keinen Platz haben werden zum neuen Carry. Es gibt auch komplexere Algorithmen, aber die meisten arbeiten so oder so ähnlich.

Beim Programmstart ist dieses Carry auf 0 initialisiert. Da es sich aber bei rand() um eine exakte mathematische Operation handelt heißt das, daß bei jedem Programmablauf genau die gleiche Reihenfolge an Zufallszahlen erzeugt werden würde. Deswegen gibt es die Funktion srand(), mit der man das Carry setzen kann. Du kannst das Carry entweder auf eine Konstante setzen; damit kannst du dann vorhersagbare Programmabläufe auch mit Zufallszahlen erzwingen. Oder aber du setzt das Carry auf eine Zahl, die möglichst bei jedem Programmstart anders ist, und dafür eignet sich eben die Systemzeit, die von time() zurückgegeben wird.

Es gibt natürlich auch zufälligere Methoden, um an Zahlen zu kommen. Auf Unixen gibt's da z.B. das Gerät /dev/random . Da sammelt der Kernel aus bestimmten Datenquellen (besonders IRQs, evtl. aber auch Netzwerkverkehr usw.) möglichst zufällige Daten und gibt diese an Userspaceprogramme weiter. Ganz zufällig ist natürlich auch das nicht.

cu,
Prefect

Widelands - Gemütliche Aufbaustrategie, Free Software
Noch ein Blog - Lerne, wie die Welt wirklich ist, aber vergiss niemals, wie sie sein sollte.

Was meinst du damit : " Die höherwertigen Bits [...] werden zum neuen Carry" ? Bin ich jetzt blöd ;) ? Wieso haben die kein Platz im Ergebnis ?

Quellcode:
#ifndef cRandom_h
#define cRandom_h

#include "Inc\Types.h"

class cRandom
{
  public:
    inline cRandom(const UInt = 0);

    inline const UInt LastRandom() const;
    inline const UInt Random();
    inline       Void Seed(const UInt);

  private:
    UInt mRandom;
};

cRandom::cRandom(const UInt pSeed) : mRandom(pSeed)
{}


const UInt cRandom::LastRandom() const
{
  return mRandom >> 16;
}

const UInt cRandom::Random()
{
  return (mRandom = mRandom * 214013L + 2531011L) >> 16;
}

Void cRandom::Seed(const UInt pSeed)
{
  mRandom = pSeed;
}

#endif


sodele, um dieses wirrwarr etwas zu entwirren hab ich mal den source meiner pseudo-zufallsgenartor-klasse (was'n wort) gepostet.
die eigentlich interessante zeile ist diese:
Quellcode:
return (mRandom = mRandom * 214013L + 2531011L) >> 16;

hier wird die letzte 'zufallszahl' mit einem konstanten faktor multipliziert und danach noch eine konstante zahl addiert.
dies ergibt die neue 'zufallszahl'; davon werden aber nur die oberen 16 bit zurueckgegeben, da die unteren bits recht regelmaesige muster durchlaufen und daher als 'zufallszahlen' ungeeignet sind.
natuerlich gibt es noch andere verfahren, um 'zufallszahlen' zu erzeugen, aber dies ist eines der einfachsten und reicht fuer 'normale' (z.b. spiele) zwecke aus.

p.s. wer sich fragt was UInt fuer ein typ ist: typedef unsigned int UInt

'KEINE PANIK' - aus der Triologie in fuenf Baenden von Douglas Adams

'FÜR DEINN FERD' - aus 'Gevatter Tod' von Terry Pratchett

ah jetzt wirds mir klarer, aber heißt das jetzt Carry oder Seed ?

Carry = Übertrag, also das, was im Hintergrund gespeichert wird

Seed = Saat, also die Zahl, mit der das Carry initialisiert (gesät) wird

cu,
Prefect

Widelands - Gemütliche Aufbaustrategie, Free Software
Noch ein Blog - Lerne, wie die Welt wirklich ist, aber vergiss niemals, wie sie sein sollte.

Okay es gibt aber noch seeehr viele andere Algos die sehr schnell sind und auch gute (besonders wichtig bei den Zufallsgeneratoren ist eine gute Verteilung der Zahlen) Ergebnisse liefern. Es gab vor längerer Zeit einen Thread in dem ich eine Methode beschrieben habe, um die Geschwindigkeit von unterschiedlichen Programmiersprachen zu testen. Der Algo der dort beschreiben wird stammt von HP und generiert in der optimierten Fassung eine Million Zufallszahlen in knapp 250msec (bei einem Duron 900). Die Ergebnisse sind beeindruckend gut. Hier der Thread:

http://www.thewall.de/ThWboard/showtopic.php3?threadid=16821&time=1005754521

void CHudSayText :: EnsureTextFitsInOneLineAndWrapIfHaveTo( int line ) -- Aja?