Random: Delphi vs. Lazarus?

[AlexII]

Kennt jemand die Unterschiede?
Folgendes habe ich zu der Funktion bei Lazarus gefunden:

Zitat:

The Free Pascal implementation of the Random routine uses the Mersenne Twister to simulate
randomness. This implementation has a better statistical distribution than for example a Linear Congruential
generator algorithm, but is considerably slower than the latter. If speed is an issue, then
alternate random number generators should be considered.

Wie steht es mit dem in Delphi?

[hathor]

DELPHI2009

DELPHI RANDOM

// Quellcode entfernt - seid bitte so gut und veröffentlicht keinen Quellcode aus dem Produkt. Die Sourcen liegen nicht jeder Edition bei und daher dürfen wir sie hier auch nicht - nicht einmal auszugsweise - veröffentlichen. Sorry, ist aber so und ich möchte mich da auch Problemen heraushalten - ich bitte um Verständnis. Daniel

[gammatester]

Der in Delphi und Pascal ist seit langem der gleiche, ein linearer http://de.wikipedia.org/wiki/Kongruenzgenerator

Delphi-Quellcode:

x[n+1] = a*x[n] + 1 mod 2^32;

mit a = $08088405 = 134775813

Edit: der gleiche heißt hier, daß er sich seit TurboPascal 5/6/7 nicht geändert hat, nicht das er der gleiche wie in neueren FPC-Versionen ist.

[PC-John]

Ein Random-Generator?

Ist standardmässig eine mehr oder weniger komplizierte Formel, welche bestimmten Anforderungen genügen muss. Hauptsache bei einer solchen Formel ist, dass sie sich auch nicht im millionsten Durchlauf in eine Ecke drängt, und statistisch gesehen, laufend den ganzen Wertebereich möglichst gleichmässig abdeckt.

Wenn nun Lazarus und Delphi die gleiche Implementation verwenden, wen stört es?
Ich will ja (Pseudo-)Zufallszahlen bekommen, und nicht einen fremden Schlüssel knacken.
Nur schon, wenn ich eine bestimmte Startzahl eingebe, kommt eine gaaaaanz andere Reihenfolge heraus.

PC-John

[BUG]

Um es nochmal zusammenzufassen: Delphi verwendet einen linearen Kongruenzgenerator während FreePascal einen Mersenne Twister benutzt.

Das heißt, dass Delphi einen sehr schnellen, aber für viele ernsthafte Anwendungen von Zufallzahlen unbrauchbaren, Generator hat. Dafür ist der Generator von FreePascal langsamer.

Auf Wikipedia gibt es auch eine schöne Übersicht.

[himitsu]

Für ernsthafte Anwendung kann man ja notfalls auch einen den vielen alternativen Zufallsgeneratoren verwenden.

Im DEC war auch einer drin und wenn es ganz sicher sein muß, dann gäbe es auch spezielle hardwarebasierte Systeme.

[AlexII]

Habe ich richtig verstanden?

Delphi - linearer Kongruenzgeneratoren - 2^32 = schnell, aber nicht sehr sicher.
Lazarus - Mersenne-Twister Pseudozufallszahlengenerator - (2^19937)−1 = langsam, aber dafür viel sicherer?

Also doch sehr unterschiedlich.

[BUG]

Zitat:

Zitat von AlexII (Beitrag 1246048)

langsam, aber dafür viel sicherer?

Was heißt hier sicher? Für kryptographische Anwendungen sind beide Generator-Typen nicht geeignet.
Der Unterschied ist aber trotzdem wichtig, z.B. wenn man randomisierte Algorithmen einsetzen will (Monte-Carlo-Simulation, usw.).

Wenn du Spaß mit Verschlüsselung haben willst, programmiere lieber einen Standard nach :mrgreen:

[Gutelo]

Als Alternative zu Random kannst du auch die GUID von Windows verwenden. Nach meinen Erfahrungen sind die resultierenden Zufallswerte recht gut und liefern auch eine brauchbare Statistik. Hier ein Beispiel:

Code:

// get random number via GUID
function random_GUID(n : integer) : integer;
var Guid : TGUID;
    num : integer;
begin
    CreateGUID(Guid);
    num := Trunc(1 + (n*(Guid.D2/65535)));
    if num = 0 then num := 1;
    if num = n+1 then num := n;
    Result := num;
end;

[Namenloser]

Ist ja abenteuerlich...

[Gutelo]

Zwar abenteuerlich, aber liefert wenigstens halbwegs zufallsaehnliche Zahlen waehrend Random mit Randomize immer identische Abfolgen generiert...

[Namenloser]

Bist du sicher, dass du Randomize auch nur einmalig aufgerufen hast? Ich hatte solche Probleme nur, wenn ich es versehentlich mehrfach aufgerufen hatte oder ganz vergessen hatte.

Deine Implementierung hat dagegen einige Probleme: Das erste if ist meiner Meinung nach komplett sinnlos, da num nach der vorherigen Zeile nie kleiner als 1 sein kann – da stellt man sich beim Lesen erst mal die Frage, ob Autor des Codes überhaupt weiß, was er tut – das sorgt nicht gerade für Vertrauen. Und das Zweite if ist noch schlimmer, denn es sorgt dafür, dass n statistisch häufiger vorkommt als alle anderen Werte.

[BUG]

Dann doch lieber selber einen der besseren Generator implementieren oder die Windows CryptAPI benutzen.
Du hast afaik keine Garantien, das die GUID in Zukunft (spätere Windowsversionen) auch noch "zufällig" genug ist. Aber interessante Idee :mrgreen:

[Namenloser]

Zitat:

Zitat von BUG (Beitrag 1246062)

Windows CryptAPI

Wobei nach den letzten Monaten wohl keiner mehr ernsthaft glaubt, dass das Ding keine Backdoor hat, oder?

[Gutelo]

Dass das erste if keinen Sinn macht gebe ich dir Recht. Ist ein Relikt einer vorherigen Implementation in der das 1+ nicht im Trunc war. Aendert aber nichts an der Funktionalitaet.

Bezueglich des zweiten ifs: Auch dieser Einwand ist richtig. Allerdings ist der Einfluss sehr gering und die resultierenden statitischen Verteilungen sind vielfach besser als bei Random. Wenn jemand eine Idee hat wie man die Randbedingung ohne Grossen Aufwand besser loest waere ich dankbar.

Randomize hatte ich nur einmal vorher aufgerufen. Sehe aber auch keinen Grund warum man es nicht oefter aufrufen duerfte. Nach meinem Verstaendnis setzt Randomize nur einen beliebigen Startpunkt fest von dem aus die weiteren Werte mit Random bestimmt werden. Da der Startpunkt zufaellig ist sollte man Randomize doch auch beliebig aufrufen duerfen, oder nicht?

[Namenloser]

Der Startpunkt ist nicht zufällig – wie auch. Man braucht ja gerade den Zufallsgenerator, um „zufällige“ Werte zu erzeugen. Wie soll man dann einen echt zufälligen Startpunkt für den Zufallsgenerator finden? Ein Computer ist nun mal deterministisch.

Randomize setzt den Startpunkt auf die aktuelle Uptime. Wenn man das in kurzen Abständen hintereinander ausführt, kommen da immer der gleiche oder sehr ähnliche Seeds bei heraus, und dadurch ergeben sich auch immer gleiche oder ähnliche Zahlenfolgen.

[cookie22]

Zitat:

Zitat von Namenloser (Beitrag 1246065)

Wenn man das in kurzen Abständen hintereinander ausführt, kommen da immer der gleiche oder sehr ähnliche Seeds bei heraus, und dadurch ergeben sich auch immer gleiche oder ähnliche Zahlenfolgen.

Ähnliche Seeds ergeben nicht ähnliche Zufallszahlen. Ausserdem kann man den Delphi RNG auch selbst via RandSeed füttern.

[Namenloser]

Zitat:

Zitat von cookie22 (Beitrag 1246112)

Zitat:

Zitat von Namenloser (Beitrag 1246065)

Wenn man das in kurzen Abständen hintereinander ausführt, kommen da immer der gleiche oder sehr ähnliche Seeds bei heraus, und dadurch ergeben sich auch immer gleiche oder ähnliche Zahlenfolgen.

Ähnliche Seeds ergeben nicht ähnliche Zufallszahlen.

Ich hab nicht im Kopf wie der RNG von Delphi genau funktioniert, ich hab nur irgendwann mal die Erfahrung gemacht. Vielleicht lief der Code auch so schnell, dass die Seeds tatsächlich häufig komplett gleich waren.

[cookie22]

Zitat:

Zitat von Namenloser (Beitrag 1246113)

Zitat:

Zitat von cookie22 (Beitrag 1246112)

Zitat:

Zitat von Namenloser (Beitrag 1246065)

Wenn man das in kurzen Abständen hintereinander ausführt, kommen da immer der gleiche oder sehr ähnliche Seeds bei heraus, und dadurch ergeben sich auch immer gleiche oder ähnliche Zahlenfolgen.

Ähnliche Seeds ergeben nicht ähnliche Zufallszahlen.

Ich hab nicht im Kopf wie der RNG von Delphi genau funktioniert, ich hab nur irgendwann mal die Erfahrung gemacht. Vielleicht lief der Code auch so schnell, dass die Seeds tatsächlich häufig komplett gleich waren.

Darum sollte man ja Randomize nicht zu schnell zu oft aufrufen. :P

[gammatester]

Noch mal zum Thema Geschwindigkeit vs. Sicherheit bzw Periodenlänge: So einfach wie hier zusammengefaßt

Zitat:

Zitat von AlexII (Beitrag 1246048)

Delphi - linearer Kongruenzgeneratoren - 2^32 = schnell, aber nicht sehr sicher.
Lazarus - Mersenne-Twister Pseudozufallszahlengenerator - (2^19937)−1 = langsam, aber dafür viel sicherer?

ist die Lage nicht. Wenn man sich meine Tabelle http://www.wolfgang-ehrhardt.de/misc_de.html#prng ansieht, erkennt man das Delphi random nur ca 10% schneller als der Mersenne Twister ist, aber 30% langsamer als X0R4096 und immer noch 15% langsamer als mein 'Standard'-Generator Taus88. Selbst der kryptografische ISAAC-Generator ist nur ca 18% langsamer.

[AlexII]

Aber wie sieht es mit der Sicherheit der Passwörter aus? Die von Delphi sind schneller zu knacken wie ich verstehe.
Gib's eigentlich einen Cross-Platform-Zufallsgenerator, der NSA oder "Wasser und Bombenfest" ist?

[Namenloser]

Zitat:

Zitat von cookie22 (Beitrag 1246118)

Darum sollte man ja Randomize nicht zu schnell zu oft aufrufen. :P

Das habe ich doch gerade gesagt. Eigentlich sollte man es nur einmal aufrufen.

[gammatester]

Zitat:

Zitat von AlexII (Beitrag 1246128)

Aber wie sieht es mit der Sicherheit der Passwörter aus? Die von Delphi sind schneller zu knacken wie ich verstehen.
Gib's eigentlich einen Cross-Platform-Zufallsgenerator, der NSA oder "Wasser und Bombenfest" ist?

Passwörter sollte man nicht mit dem Delphi-Generator erzeugen, jedenfalls nicht algorithmisch nur mit einem Programm: Wenn der Sourcecode/PW-Algorithmus nicht gekannt ist, dann kann man nicht sicher sein, ob irgendetwas Unerwünschtes :) drin ist; wenn er bekannt ist, kann man ihn in (Milli-)Sekunden knacken, man probiert halt alle 2^32 Seeds aus (siehe zB hier für das super-geheime Passwort ylCvlgU5$wGWRmCcIyg ... LbhsjCbg).

Es gibt wohl sichere Generatoren (zB Fortuna), aber das Hauptproblem ist das Seeding bzw. Reseeding, speziell auf embedded Systemen; d.h. der eigentliche Engpaß ist ein gute (externe) Entropie-Quelle.

[himitsu]

Zitat:

Zitat von Namenloser (Beitrag 1246113)

Ich hab nicht im Kopf wie der RNG von Delphi genau funktioniert, ich hab nur irgendwann mal die Erfahrung gemacht. Vielleicht lief der Code auch so schnell, dass die Seeds tatsächlich häufig komplett gleich waren.

Es ist egal wie schnell, da der RNG von Delphi immer raufrechnet.

Es sei denn du hattes den Fehler der Fehler gemacht und Randomize zu häufig aufgerufen.

[Namenloser]

Zitat:

Zitat von himitsu (Beitrag 1246140)

Es sei denn du hattes den Fehler der Fehler gemacht und Randomize zu häufig aufgerufen.

Ja, wie oft soll ich es noch sagen? Deshalb hatte ich ja gefragt, ob er den Fehler vielleicht auch gemacht hat. Nicht nur ich hab den Fehler damals gemacht, ich hab ihn auch bei anderen Anfängern schon öfters gesehen...

Denn an sich wüsste ich nicht, wieso das normale Delphi-Random sonst „schlechte“ Zufallsfolgen ausspucken sollte. Der RNG taugt vielleicht nicht für kryptografische Zwecke, aber bemerkbare Regelmäßigkeiten treten da eigentlich nicht auf (anders als z.B. beim Standard-random von PHP).

[creed steiger]

Dazu gabs eine längere Diskussion auf der FPC Mailinglist
http://lists.freepascal.org/lists/fp...er/031464.html

[cookie22]

Zitat:

Zitat von Namenloser (Beitrag 1246132)

Eigentlich sollte man es nur einmal aufrufen.

Nein, das ist eigentlich egal, solang du nicht den gleichen Seed hast.

Also Randomize NICHT zu oft aufrufen, dann kann so etwas passieren.:warn:

[Namenloser]

Zitat:

Zitat von cookie22 (Beitrag 1246156)

Zitat:

Zitat von Namenloser (Beitrag 1246132)

Eigentlich sollte man es nur einmal aufrufen.

Nein, das ist eigentlich egal, solang du nicht den gleichen Seed hast.

Also Randomize NICHT zu oft aufrufen, dann kann so etwas passieren.:warn:

Auch wenn du einen anderen Seed setzt, verkürzt du auf jeden Fall die Periode. Mir fällt auch kein vernünftiger Grund ein, es mehr als einmal aufzurufen.

[himitsu]

Früher ging Randomize mal auf GetTickCount, welches meistens in einem Intervall von 16 Millisekunden hochzählte. (glaub ich)

Aber da Zuviele zuviele Fehler machenten, wurde es umgebaut.
Inzwischen wird wohl QueryPerformanceCounter verwendet, damit sich solche Fehler nicht all zu sehr auswirken.
Und für die, welche Randomize vergessen aufzurufen, macht das jetzt die VCL einmal, beim Start.


Man könnte zwar Randomize oder den Seed öfters aufrufen/setzen, aber der Zufallsgenerator hat irgendwie soeine durchschnittliche "Gleichverteilung" und diese Verteilung der Zufallswerte könnte man damit negativ beeinflussen.
Also, im Normalfall kommen alle Zufallszahlen, über einen ausreichend großen Bereich hinweg, ungefähr gleich oft vor.


Ein "Vorteil" am Delphi-Random ist, daß man, ausgehend von einem bestimmten Seed, immer die selben Zahlen bekommt. (solange keiner die zugrundeliegende Berechnung verändert)

[cookie22]

Zitat:

Zitat von himitsu (Beitrag 1246160)

...und diese Verteilung der Zufallswerte könnte man damit negativ beeinflussen.

Ist der Seed unterschiedlich, sollte das völlig egal sein.

[Gutelo]

Namenloser,

wenn du moechtest kannst du mal folgendes ausprobieren:

1) Lasse dir ein paar Millionen Lottotips generieren fuer Lotto 6 aus 49
2) Danach erstelle eine Statistik fuer die Zahlen 1 bis 49 an welcher Stelle die Zahl in jedem Tipp vorkommt. Plotte die resultierenden sechs Hauefigkeitskurven (erste Stelle, zweite Stelle, ...) ueber die Zahlen 1 bis 49.

Wenn du das einmal mit Delphi random machst und einmal mit einem besseren Generator machst wirst du sehen dass die Delphi random Werte schlecht sind und die Statistik stark verzerren.

[JamesTKirk]

Zitat:

Zitat von himitsu (Beitrag 1246160)

Früher ging Randomize mal auf GetTickCount, welches meistens in einem Intervall von 16 Millisekunden hochzählte. (glaub ich)

GetTickCount zählt zumindest auf NT Systemen in Millisekunden hoch, da es auf dem genaueren internen Counter des Kernels aufsetzt, siehe auch hier, Zeile 445.

Zitat:

Zitat von himitsu (Beitrag 1246160)

Ein "Vorteil" am Delphi-Random ist, daß man, ausgehend von einem bestimmten Seed, immer die selben Zahlen bekommt. (solange keiner die zugrundeliegende Berechnung verändert)

FPC's Random hat die selbe Eigenschaft (ist ja schließlich auch ein PRNG).

Gruß,
Sven

[Furtbichler]

Zitat:

Zitat von JamesTKirk (Beitrag 1246205)

Zitat:

Zitat von himitsu (Beitrag 1246160)

Früher ging Randomize mal auf GetTickCount, welches meistens in einem Intervall von 16 Millisekunden hochzählte. (glaub ich)

GetTickCount zählt zumindest auf NT Systemen in Millisekunden hoch, da es auf dem genaueren internen Counter des Kernels aufsetzt, siehe auch hier, Zeile 445.

Hab ich kein NT-System? Na, zumindest habe ich kein ReactOS.:stupid:

Delphi-Quellcode:

procedure TForm1.Button1Click(Sender: TObject);
var
  c0,c,c1 : Cardinal;

begin
  c := GetTickCount;
  c0 := c;
  repeat
    c1 := GetTickCount;
    if c<>c1 then begin
      memo1.lines.add(intToStr(c-c0));
      c := c1;
    End;
  until c1-c0>100;
end;

Zitat:

Zitat von MemoBox1

0
15
31
47
62
78
93

16ms war schon immer so.

[hathor]

"The resolution of the GetTickCount function is limited to the resolution of the system timer, which is typically in the range of 10 milliseconds to 16 milliseconds."

http://msdn.microsoft.com/en-us/libr...=vs.85%29.aspx

[tigernut]

Zitat:

Zitat von gammatester (Beitrag 1245983)

Der in Delphi und Pascal ist seit langem der gleiche, ein linearer http://de.wikipedia.org/wiki/Kongruenzgenerator

Delphi-Quellcode:

x[n+1] = a*x[n] + 1 mod 2^32;

mit a = $08088405 = 134775813

Edit: der gleiche heißt hier, daß er sich seit TurboPascal 5/6/7 nicht geändert hat, nicht das er der gleiche wie in neueren FPC-Versionen ist.

Hallo,

weisst du wie die Funktion random(pWert:integer):integer arbeitet? Ist das einfach:

Delphi-Quellcode:

random:=zufallszahl mod pWert;

Gruß

[himitsu]

Nee

Delphi-Quellcode:

function Random(const ARange: Integer): Integer;
{$IFDEF PUREPASCAL}
var
  Temp: Longint;
begin
  Temp := RandSeed * $08088405 + 1;  // berechne den nächsten Wert
  RandSeed := Temp;  //
  Result := (UInt64(Cardinal(ARange)) * UInt64(Cardinal(Temp))) shr 32;
end;

Es ist im Prinzip eher etwas wie

Delphi-Quellcode:

Result := Random * pWert;  // Random liefert ja 0 bis 0.999999 (oder war es 0 bis 1?)

[tigernut]

Hi Himitsu.

Zwei Dinge verstehe ich nicht.

1. In der Rekursionsformel für den Zufallsgenerator heißt es x[n+1] = (a*x[n] + 1) mod 2^32
   Es wird der Rest der Division durch 2^32 als neue Zufallszahl ausgegeben. Ist das gleichbedeutend mit shr 32? shr ist doch eher äquivalent zu div?
2. Wie liefert Radom eine Kommazahl, wenn wir ausschließlich mit Ganzzahlen rechnen?

[BUG]

Zitat:

Zitat von tigernut (Beitrag 1247040)

In der Rekursionsformel für den Zufallsgenerator heißt es x[n+1] = (a*x[n] + 1) mod 2^32
Es wird der Rest der Division durch 2^32 als neue Zufallszahl ausgegeben. Ist das gleichbedeutend mit shr 32? shr ist doch eher äquivalent zu div?

Das mod 32 wird schon durch den Wertebereich von longint erledigt. Das Shiften ist zum Aufbereiten der Ausgabe.

Zitat:

Zitat von tigernut (Beitrag 1247040)

Wie liefert Radom eine Kommazahl, wenn wir ausschließlich mit Ganzzahlen rechnen?

Man kann das auf Bitebene regeln. Andererseits kann man einfach 2^32-1 durch die 32bit Zufallszahl teilen (nicht durch 0 teilen).
Satty67 hat sich hier auch ein paar Möglichkeiten überlegt.

[himitsu]

Zitat:

Zitat von tigernut (Beitrag 1247040)

Wie liefert Radom eine Kommazahl, wenn wir ausschließlich mit Ganzzahlen rechnen?

Indem dort anders gerechnet wird?

Delphi-Quellcode:

function Random: Extended;
const
  two2neg32: double = ((1.0/$10000) / $10000);  // 2^-32
{$IFDEF PUREPASCAL}
var
  Temp: LongInt;
  F: Extended;
begin
  Temp := RandSeed * $08088405 + 1;
  RandSeed := Temp;
  F  := Temp;
  Result := F * two2neg32;
end;

[gammatester]

Zitat:

Zitat von himitsu (Beitrag 1247052)

Delphi-Quellcode:

  //...
  F  := Temp;
  Result := F * two2neg32;
end;

Dieser Code liefert allerdings Zahlen im Intervall [-0.5,0.5). Für das normalerweise von

Delphi-Quellcode:

random

verwendete Interval [0,1) kann man

Delphi-Quellcode:

  //...
  Result := (Temp + 2147483648.0) / 4294967296.0;
end;

benutzen, und eine ähnliche Formel wenn man mehr als 32 Bit braucht.