Delphi 11 kein RandomRange für 64-bits?

[TurboMagic]

Wenn jemand einen brauchbaren Verletzungsalgorithmus beisteuert nehme ich den gerne auf.

[TurboMagic]

Ich meinte natürlich "Verlängerungsalgorithmus". Da hat unbemerkt die Autokorrektur des Tablets zugeschlagen gehabt...
Aber: was würde eigentlich dagehen sprechen das ungefähr so umzusetzen:

Delphi-Quellcode:

var
  r1, r2: UInt32;
  r: UInt64;
begin
  r1 := Random; // oder eine unbiased Alternative
  r2 := Random;
  r := (r1 shl 32)+r2;

[Gausi]

Zitat von TurboMagic:

Aber: was würde eigentlich dagehen sprechen das ungefähr so umzusetzen:

Das kommt dann darauf an, wie "random" implementiert ist. Ich kann mich z.B. an eine Vorlesung erinnern, wo es um lineare Kongruenzgeneratoren als Pseudo-Zufallsgeneratoren ging.

Wenn man damit beispielsweise 1000 Zufallszahlen erzeugt, und je zwei aufeinanderfolgende Zahlen als x/y-Koordinaten nimmt und diese grafisch darstellen lässt, dann erkennt man recht deutliche Muster in der Ausgabe - alle Punkte lagen auf parallelen Geraden, wobei die Anzahl der Geraden von der Primzahl p abhängt, die dem ganzen zugrunde liegt.

Jetzt ist diese Form der Zufallszahlen-Ermittlung ohnehin nicht für kryptografische Anwendungen geeignet, aber es kann durchaus sein, dass es auch bei anderen Verfahren bei so einer Koppelung zu Nebeneffekten kommt, die die Qualität des Zufalls mindern.

[Michael II]

Zitat von TurboMagic:

Ich meinte natürlich "Verlängerungsalgorithmus". Da hat unbemerkt die Autokorrektur des Tablets zugeschlagen gehabt...
Aber: was würde eigentlich dagehen sprechen das ungefähr so umzusetzen:

Delphi-Quellcode:

var
  r1, r2: UInt32;
  r: UInt64;
begin
  r1 := Random; // oder eine unbiased Alternative
  r2 := Random;
  r := (r1 shl 32)+r2;

Falls die von deinem random erzeugte 0-1 Folge völlig zufällig ist, dann geht das. Dann kannst du beliebig viele Bits aneinanderreihen.

Aber wie Gausi (und weiter oben Uwe) schreibt: Beim von Delphi verwendeten Generator sind die Zahlen alles andere als zufällig. Der Generator erzeugt die immer gleiche Zahlenfolge; alle Zahlen werden genau einmal erzeugt, bis wir wieder bei der ersten landen. Durch randseed legst du lediglich den Startwert der Zahlenfolge fest.

Wenn du einen solchen Generator wie du oben vorschlägst erweiterst, dann haust du massive Löcher in die Wertemenge.
(Ist fast ein wenig wie wenn du vorschlägst einen Text 2x512Bit zu verschlüsseln statt einmal mit 1024Bit.)

Sehr vereinfachend beschrieben:
Nimm an du hättest einen Generator, welcher immer die aus 10 Elementen bestehende Folge
0 1 2 3 4 5 6 7 8 9 (und dann wieder 0 1 2...) erzeugt.
Mit deiner Konstruktion würde der neue Generator
01 23 45 67 89 und dann wieder 01 erzeugen. Dein Generator hätte nur einen Bruchteil der von dir gewollten 100 Zahlen 00 bis 99 erzeugt.

Auf https://de.wikipedia.org/wiki/Kongruenzgenerator siehst du das von Gausi erwähnte typische Hyperebenenverhalten des in Delphi verwendeten Generators graphisch dargestellt.


Du könntest den 32Bit Delphi Generator natürlich für komplexere 64Bit Konstruktionen verwenden (zum Beispiel mehrere Generatoren mit verschiedenen randseeds verwenden und je nur eine Dezimalstelle (oder nur 4 Bits) berechnen). Aber das feste Muster wird dir viele Fallen stellen. Und der Speed wird dabei so fest leiden, dass du lieber zu einer 64Bit Lösung greifst.

[Uwe Raabe]

Zitat von Michael II:

Wenn du einen solchen Generator wie du oben vorschlägst erweiterst, dann haust du massive Löcher in die Wertemenge.

Ich denke, es kommt auf die konkreten Anforderungen an. Selbst bei einem Generator, der die vollständige Wertemenge liefern kann, wird diese ja vermutlich zu Lebzeiten des Entwicklers nicht generiert werden. Somit bleiben auch so Lücken in den generierten Werten. Werden dann auch nur zufällige Zahlen gebraucht, ohne irgendwelche kryptografische Sicherheitsanforderungen, dann sollten 2 x 32 Bit vermutlich ausreichen.

Etwas trickreicher wird allerdings die gleichmäßige Reduktion auf den gewünschten Wertebereich.

[Michael II]

Zitat von Uwe Raabe:

Zitat von Michael II:

Wenn du einen solchen Generator wie du oben vorschlägst erweiterst, dann haust du massive Löcher in die Wertemenge.

Ich denke, es kommt auf die konkreten Anforderungen an. Selbst bei einem Generator, der die vollständige Wertemenge liefern kann, wird diese ja vermutlich zu Lebzeiten des Entwicklers nicht generiert werden. Somit bleiben auch so Lücken in den generierten Werten. Werden dann auch nur zufällige Zahlen gebraucht, ohne irgendwelche kryptografische Sicherheitsanforderungen, dann sollten 2 x 32 Bit vermutlich ausreichen.

Etwas trickreicher wird allerdings die gleichmäßige Reduktion auf den gewünschten Wertebereich.

Dass man eh nie alle Werte nutzt und dass Lücken im Wertebereich vorhanden sind sind zwei paar Schuhe.

Ja, es kommt immer darauf an, was man mit einem Generator testen will. Wenn man die Zahlen zum Testen von Systemen oder Programmen verwendet und zum Beispiel erwartete/berechnete Wahrscheinlichkeiten mit dank dem Generator gemessenen vergleichen will, dann ist es wichtig, dass möglichst keine Lücken im Wertebereich vorhanden sind. Es kann sonst sein, dass relevante Testfälle gar nicht, zu selten oder zu oft auftreten: Im obigen Beispiel mit den Zahlen 0 bis 9, können durch Aneinanderhängen zweier Werte nur noch 10% (01 12 23 34 45... 89 90) aller möglichen Fälle erreicht werden. Bei Konkatenation zweier 2^32 Bit "Delphi random Werte" werden nur 2^32 von möglichen 2^64 Zahlen erzeugt (random erzeugt 2^32 voneinander verschiedene Werte z. Ein erneuter Aufruf von random erzeugt für jedes z immer denselben Nachfolger n(z)). Oder anders: Nur jeder 2^32ste Fall kann überhaupt auftreten. Und das ist mir für meine Dinge weit zu wenig. Kurz: Ich bin in den allermeisten Anwendungsfällen nicht damit einverstanden, dass die Lücken keine Rolle spielen.

Die gleichmässige Reduktion erreicht man meistens durch Einteilen der Definitionsmenge in ARange gleich grosse und möglichst grosse Intervalle. Wenn die Anzahl der möglichen Zufallszahlen nicht durch ARange teilbar ist bleibt ein Restintervall R. Wird eine Zufallszahl in R erzeugt, wird die Zufallszahl verworfen.
Wenn man alle erzeugten Zufallsbits verwenden (also nix verwerfen) will, dann wird's natürlich trickreicher.

Ich bin dann mal weg .

[Stevie]

Hier mal visualisiert, was Michael erklärt hat - genutzt habe ich den Algorithmus, der in dieser Stackoverflow Antwort zu hash functions genutzt wurde, um deren Verteilung zu visualisieren.

Random.png zeigt die Verteilung von Random(MaxInt) und Random64.png die oben vorgeschlagene Implementierung. (ja, da sind 2 Bilder - die Vorschau des 2. sieht durch die Streifen weiß aus, einfach drauf klicken)