guter zufall (multiply-with-carry prng)

volkard

schmeißt rand() weg und nehmt den hier.

#ifndef RANDOM_HPP
#define RANDOM_HPP

#include "types.hpp"

//multiply-with-carry prng
//quelle
//http://cliodhna.cop.uop.edu/~hetrick/na_faq.html
class Random{
private:
	u64 x;
public:
	Random(u64 seed){
		x=seed|(u64(1)<<32);
	}
	u32 operator()(){
		x=1967773755*(x&0xffffffff)+(x>>32);
		return x;
	}
};

#endif

besteht auch die diehard-test-suite, siehe http://volkard.de/std.out und http://volkard.de/vh.out

Michael E.

Ich sag einfach mal danke, obwohl ich keinen Schimmer hab, wie gut dein Zufall wirklich ist.

BTW solltest du die types.hpp auch noch posten. Ansonsten muss man sich erst mal die vhlib runterladen.

rüdiger

kannst du nicht am besten (wenn vorhanden) /dev/random oder /dev/urandom benutzen?

Bashar

Michael E. schrieb:

BTW solltest du die types.hpp auch noch posten. Ansonsten muss man sich erst mal die vhlib runterladen.

Was u64 und u32 sind, kann man sich notfalls auch noch selbst denken.

volkard

kingruedi schrieb:

kannst du nicht am besten (wenn vorhanden) /dev/random oder /dev/urandom benutzen?

braucht das weniger als 17 takte pro zufallszahl? hab ja eigentlich einen gesucht, der brauchbar ist, um verschiede implemetierungen von winzigen rechenfunktionen auszumessen, welche die beste ist. und da war der mersenne twister generator zu komisch mit seinem speicherbedarf und so toll schnell isser auch nicht, wie die immer sagen. und std::rand() war mit zu plattfurmabhängig.

volkard

Michael E. schrieb:

Ich sag einfach mal danke, obwohl ich keinen Schimmer hab, wie gut dein Zufall wirklich ist.

die beiden logfiles machen eindruck. mich überzeugen die.

BTW solltest du die types.hpp auch noch posten. Ansonsten muss man sich erst mal die vhlib runterladen.

die types.hpp bietet hier nur

typedef unsigned long long u64;

typedef unsigned int u32;

nimm vielleicht selber nur unsigned __int64 oder was dein compiler anbietet.

Bashar

volkard schrieb:

braucht das weniger als 17 takte pro zufallszahl?

Das kannst du IMO mindestens verzehnfachen, wg. Kontextwechsel aufgrund des read-Aufrufs. Einen aus /dev/random gelesenen Wert kann man aber gut als seed einsetzen.

volkard

Bashar schrieb:

Einen aus /dev/random gelesenen Wert kann man aber gut als seed einsetzen.

ja, das wird wohl eingebaut, wenn es ernst wird.

volkard

Ich baue /dev/random oder ähnliche Plattformdinge nicht ein. Wer will, kann ja

Random rand(MyOperatingSystem::giveMeAGoodRandomNumber());

sagen.

Ich dachte du würdest mittlerweile einen anderen prng bevorzugen?

erik.vikinger

Hallo,

bei dem Algorithmus fehlt der, üblicherweise deutliche, Warnhinweis :

"Kein echter Zufall! Niemals in kritischen Systemen einsetzen!"

Es gibt viele Anwendungsfälle wo der Einsatz so eines Pseudo-Random-Number-Generator extrem fahrlässig ist.

Außerdem könnte dieser Algorithmus anfällig für schwache Seeds sein.

Grüße
Erik

erik.vikinger schrieb:

"Kein echter Zufall!

Nicht?

erik.vikinger

Hallo,

Tim schrieb:

Nicht?

Natürlich nicht. Woher den auch? In der gezeigten Klasse ist nichts zufälliges drin. Der Zufall muss vorher, als zufälliger Seed, rein kommen. Nach spätestens ein paar Werten aus diesem PRNG kann man auf den internen Zustand zurückrechnen und damit jeden weiteren kommenden Wert vorherberechnen. Etwas das man vorherberechnen kann ist kein Zufall.

Grüße
Erik

hustbaer

@erik.vikinger:
Dein Kommentar hier ist total sinnfrei. Ein Algorithmus kann nie echte Zufallszahlen generieren. Das liegt in der Natur der Sache. Wieso sollte man dann einen Warnhinweis anbringen?

erik.vikinger

Hallo,

hustbaer schrieb:

Wieso sollte man dann einen Warnhinweis anbringen?

Weil man sonst den Algorithmus komplett durcharbeiten und natürlich auch verstehen müsste um zu sehen das dort keine externen Dinge drin sind die eventuell doch echten Zufall reinbringen könnten. Wer tut das schon?

Grüße
Erik

hustbaer

Man muss garnix durcharbeiten, zumindest nicht bis zu dem Punkt wo man es versteht. Man muss bloss gucken, ob irgendwo auf irgendwelche Dinge wie /dev/rand oder ähnliches zugegriffen wird. Wenn nicht, können es keine echten Zufallszahlen sein.

Davon abgesehen: Alle RNGs die ich kenne sind reine PRNGs (ich meine fertige Implementierungen in diversen Libraries). Wieso also das mit einem Warnhinweis versehen, was der Normalfall ist?
Den Fall zu dokumentieren der von der Norm abweicht, d.h. in diesem Fall einen RNG der wirklich echte Zufallszahlen liefert, ist wohl vernünftiger.

Vor allem da für die meisten Anwendungen ein PRNG, mit einem mehr oder weniger echt zufälligem Seed, vollkommen ausreichend ist.

erik.vikinger

Hallo,

hustbaer schrieb:

wie /dev/rand oder ähnliches

Gerade dieses "ähnliches" ist nicht für jeden erkennbar oder gar beurteilbar.

hustbaer schrieb:

Alle RNGs die ich kenne sind reine PRNGs

Und was ist mit "/dev/urandom"? Auf einem normalen PC (mit halbwegs aktuellem Linux o.ä.) liefert das schon recht ordentlichen Zufall (wenn auch nur wenig) und wenn dann noch ein moderner Intel-Chipsatz oder eine aktuelle VIA-CPU (beide mit Hardware-TRNG) dazu kommt hat man schon eine Rundum-Sorglos-Lösung zur Verfügung (mit bereits ordentlicher Menge).

hustbaer schrieb:

Wieso also das mit einem Warnhinweis versehen, was der Normalfall ist?

Das ist allerdings ein berechtigter Einwand. Wer sich die Mühe macht eine gute Zufalls-Quelle zu implementieren schreibt das auch möglichst dick drauf oder will gar Geld dafür. Trotzdem sollte man IMHO dem unbedarften Anfänger schon möglichst deutlich sagen das nicht überall wo Zufall drauf steht auch Zufall drin ist bzw. das es verschiedene Qualitätsstufen beim Zufall gibt. Ich finde diese PRNGs sollten nicht Zufalls-Generator sondern Sequenz-Generator heißen, einfach um den Unterschied deutlich zu machen.

EDIT : "/dev/random" liefert natürlich keinen echten Zufall, jedenfalls nicht immer

Grüße
Erik

Basher_ist_nicht_BashAr

hustbaer schrieb:

Vor allem da für die meisten Anwendungen ein PRNG, mit einem mehr oder weniger echt zufälligem Seed, vollkommen ausreichend ist.

naja, da musste schon unterscheiden. viele sind für irgendwelche simulationen ausreichend, aber für kryptografie z.b. sind sie nicht so toll.

erik.vikinger schrieb:

"Kein echter Zufall! Niemals in kritischen Systemen einsetzen!"

Du schreibst doch auch nicht auf einen Fernseher:

"Keine echte 3D Welt! Niemals hinein springen!"
Siehe Link
http://data.lustich.de/bilder/l/1120-in-den-fernseher-gesprungen.jpg

Tim schrieb:

Ich dachte du würdest mittlerweile einen anderen prng bevorzugen?

Welchen denn? Würde mich sehr interessieren

volkard

Tim schrieb:

Ich dachte du würdest mittlerweile einen anderen prng bevorzugen?

Ich kann mich nicht erinnern, das gesagt zu haben. Kürzlich drückte ich aus, daß ich den mersenne twister nicht mag (das hat sich in den letzten vier Jahren also nicht geändert).