Zufallsgenerator

supertux

Hi

für einen selbstgeschriebenen Mikrokernel möchte ich einen möglichst einfachen und effizienten Zufallsgenerator einbauen. Leider ist Stochastik nicht mein starker Bereich in Mathe also stehe ich ein bisschen auf dem Schlauch.

Ich brauche das, da ich Rechenzeit simmulieren soll, da habe ich eine Task, die im Prinzip eine Anzahl von Zyklen als Parameter bekommen soll und versucht genauso viele Zyklen zu verbrauchen. Damit kann ich die Rechenzeit für meine experimente modillieren. Was mir fehlt, ist ein guter Zufallsgenerator.

Da ich bis jetzt nur kleine Tests gemacht habe, habe ich einen "trivialen" Generator geschrieben (hab ihn aus der manpage von srand implementiert)

volatile static unsigned long __seed__;

void srand(unsigned int seed)
{
    __seed__ = seed;
}

int rand(void)
{
    __seed__ = __seed__ * 1103515245 + 12345;

    return((unsigned)(__seed__/65536) % (RAND_MAX + 1));
}

aber ich bin nciht sicher, ob das gut genug ist. Leider finde ich im Netz Hauptsächlich, wie man rand() und srand effizient verwendet, aber ich will/muss diese Funktionen implementieren. Oft finde ich auch nur Hinweise darauf, dass es sich um ein komplexes Gebiet handelt und dass man mehr Infos darüber im Buch "Numerical Recipes in C" oder auch "The Art of Computer Programming" findet.

Kennt jemmand eine gute Seite, Paper oder was weiß ich, wo man einen guten und kleinen Zufallsgenerator erklärt wird, bzw. zumindest die Konzepte erläutert werden, so dass ich damit arbeiten kann? Oder ist das, was ich bereits implementiert habe, ausreichend?

Könnte dich interessieren: http://www.c-plusplus.net/forum/viewtopic-var-t-is-118802-and-highlight-is-*prng*.html
Edit: ich würde mir auch überlegen das Ding gleich reentrant auszulegen.

volkard

http://en.wikipedia.org/wiki/List_of_pseudorandom_number_generators
ich denke, du wirst beim Xorshift landen.

supertux

Tim schrieb:

Könnte dich interessieren: http://www.c-plusplus.net/forum/viewtopic-var-t-is-118802-and-highlight-is-*prng*.html

hmm, sieht nicht schlecht aus, werde es mir nachher genauer anschauen.

Tim schrieb:

Edit: ich würde mir auch überlegen das Ding gleich reentrant auszulegen.

das ist eine gute Idee, da ich keine mutex habe, kann ich __seed__ nicht schützen.

volkard schrieb:

http://en.wikipedia.org/wiki/List_of_pseudorandom_number_generators
ich denke, du wirst beim Xorshift landen.

danke für die Liste. Hab mir Xorshift angeschaut. Da werden die static Variablen mit festen Zahlen initialisiert, würde das Verfahren dann nicht da immer die gleiche Sequenz von Zahlen ausgeben?

hustbaer

supertux schrieb:

Tim schrieb:

Edit: ich würde mir auch überlegen das Ding gleich reentrant auszulegen.

das ist eine gute Idee, da ich keine mutex habe, kann ich __seed__ nicht schützen.

Hast du denn andere Dinge wie eine Spinlock oder wenigstens CAS um das ganze Thread-Safe zu bekommen? Wenn nicht, fragt ich mich wie du das Thread-Safe bekommen willst
(reentrant ist hier IMO nicht der richtige Ausdruck, da ein Zufallszahlengenerator ja wohl kaum irgendwelche Callbacks aufrufen wird. D.h. weitere Aufrufe können hier nur aus anderen Threads kommen)

supertux

hustbaer schrieb:

Hast du denn andere Dinge wie eine Spinlock oder wenigstens CAS um das ganze Thread-Safe zu bekommen?

nein, sowas habe ich auch nicht. An sich ist es nicht wirklich tragisch, dass es nicht thread-safe ist, weil die Threads selber 'rand()' nicht aufrufen werden, sondern nur zur dynamische Erzeugung von Threads mit ihrer Echtzeitspezifikation.

hustbaer

Ah, OK.

Falls es um C++ geht würde ich den Generator in eine eigene Klasse packen (ohne Synchronisation, die ja sowieso nicht möglich wäre). Einfach und IMO vollkommen ausreichend.

Bei C wäre ich vermutlich zu faul, wenn der Generator sowieso nur an einer Stelle gebraucht wird.