Besseres Random() - eure Vorschläge

[DieDolly]

Rein interessehalber habe ich gerade mit Zufallswerten und deren "Zufälligkeit" zu tun.
Dabei ist mir aufgefallen, dass das normale Delphi-Random und auch das von JavaScript wenig Zufälligkeiten bieten.
Bei Schlüsseln könnte man daraus vermutlich eine sich wiederholende Sequenz ablesen.

Unten sind zwei Links zu Grafiken (die sind zu groß für einen Anhang im Forum). Das obere ist die Darstellung vom Delphi-Random und das untere eine andere Implementierung (Google).
Das Beispielprogramm ist auch angehängt.

Kennt ihr noch bessere Random-Funktionen? Ich frage rein aus Interesse. Ich muss nix verschlüsseln oder sonst was.

Standard
https://img42.com/lyaT_

Custom
https://img42.com/Zr2-x

Bitte nur funktionsfähige Codes und Techniken anbieten, die auch mit Windows Delphi kompilierbar sind.
Bitte auch nur o.g. anbieten, wofür man nicht extra Bibliotheken benötigt.

[Stevie]

https://wiki.freepascal.org/A_simple...rsenne_twister

[DieDolly]

Ist es normal, dass man das mit Delphi 10.3.3 nicht kompilieren kann?
Die Theorie dahinter ist jedenfalls interessant.

[KodeZwerg]

Random Generators von Primož Gabrijelčič

[Luckie]

Terror 502, Bad Gateway.

Man kann Grafiken auch verkleinern.

[DieDolly]

Zitat:

Man kann Grafiken auch verkleinern.

Das ist eine ziemlich schlechte Idee bei Grafiken, bei denen es aufs Detail ankommt.

[Neutral General]

random.org bietet auch eine API an.
Da hast du echten Zufall. Ist die Frage ob sowas für dich in Frage kommt.

[DieDolly]

Ne. Keine webservices oder sowas. Nur Delphi und Theorie.
Mir gefällt bisher der Ansatz des Mersenne am besten.

[Frickler]

Well 1024a

Siehe http://www.delphipraxis.net/175061-w...generator.html

Aus dem verlinkten Artikel:

Zitat:

Der Vorteil des Well gegenüber Mersenne-Twister ist, das der Well-Generator schon nach ~ 100 Schritten "eingelaufen" ist, während Mersenne-Twister dazu ~ 70000 Schritte braucht.

"Einlaufen" heisst, man muss entsprechend viele Zufallszahlen abrufen und wegwerfen, bevor man mit guten gleichverteilten Zahlen rechnen kann.

[DieDolly]

Kann man Mersenne und WellRng1024 denn vergleichen? Weil WellRng1024 bietet keine Range die man angeben kann.

Beides sehr sehr interessante Methoden. Funktioniert Well1024 auch mit einem Maximum? RandomRange brauche ich eher weniger (wäre trotzdem schön!).

[TurboMagic]

1. Ich bekomme bei beiden Links von dir 502 - Bad Gateway.

2. Die DEC hat auch einen Zufallszahlengenerator, aber frage mich
bitte nicht zu dessen Qualität. Du darfst aber gerne so eine
Verteilungskurve anfertigen, würde mich auch interessieren.

https://github.com/winkelsdorf/Delph...tionCompendium

Grüße

TurboMagic

[DieDolly]

Vom DEC habe ich noch keine Verteilungsgrafik. Aber die vom Wel1024 ist interessant denn die sieht genau so schlimm aus wie die vom standard Random.
Das liegt meiner Meinung nach an der Initialisierung, die mit Random stattfindet.

Die beste Verteilung mit der besten Performance und dem wenigstens Overhead hat bisher MT19937 (Mersenne Twister, vom 21.6.2000: http://www.rksolution.cz/delphi/dtip0008.txt ) aber damit gibt es Probleme mit 64bit wie man hier sieht
https://www.delphipraxis.net/202655-...ml#post1452105

[Frickler]

Zitat:

Zitat von DieDolly (Beitrag 1452095)

Kann man Mersenne und WellRng1024 denn vergleichen? Weil WellRng1024 bietet keine Range die man angeben kann.

Beides sehr sehr interessante Methoden. Funktioniert Well1024 auch mit einem Maximum? RandomRange brauche ich eher weniger (wäre trotzdem schön!).

RandomFloat gibt eine Zahl zwischen 0 und 1. Daraus kann man jeden beliebigen Range selbst stricken.

[Codehunter]

Echte Zufallszahlen in der IT sind doch von Beginn an ein Streitthema ^^

https://www.heise.de/ct/artikel/Linu...te=5#nav__a__0

[TurboMagic]

Zitat:

Zitat von DieDolly (Beitrag 1452114)

Vom DEC habe ich noch keine Verteilungsgrafik.

Du könntest ja mal versuchen eine zu machen, dann würden wir sehen, ob die auch so schlimm aussieht.

[DieDolly]

Zitat:

Zitat von TurboMagic (Beitrag 1452113)

1. Ich bekomme bei beiden Links von dir 502 - Bad Gateway.

2. Die DEC hat auch einen Zufallszahlengenerator, aber frage mich
bitte nicht zu dessen Qualität. Du darfst aber gerne so eine
Verteilungskurve anfertigen, würde mich auch interessieren.

https://github.com/winkelsdorf/Delph...tionCompendium

Grüße

TurboMagic

Der DEC 6.0 beta 1 Random ist sehr langsam verglichen zu anderen. 10x langsamer bei mir. Die Resultate. Die Bilder sind in der Originalgröße, damit keine Details verloren gehen!
Info: ich musste die Bilder auf einen Discordserver hochladen, da meine favorisierte Seite img42.com nach dem Upload von 5x4 MB (5.242.880‬ Pixel) offline ging. 4MB pro Bild.

1024x1024 Durchgänge. Test-CPU: Intel Core i7 4790K

Random-DEC 6.0, 11539ms
https://cdn.discordapp.com/attachmen...64/unknown.png

Random-Delphi, 1057ms
https://cdn.discordapp.com/attachmen...68/unknown.png

Random-MT19937, 1063ms
https://cdn.discordapp.com/attachmen...37/unknown.png

Random-1-Zeiler, 1095ms
https://cdn.discordapp.com/attachmen...88/unknown.png

Random-Well1024, 1185ms
https://cdn.discordapp.com/attachmen...84/unknown.png

Random-Poisson
https://cdn.discordapp.com/attachmen...76/unknown.png

Random-DEC und Random-MT19937 schneiden am besten ab.
Well1024 ist durch die anfängliche Initialisierung mit dem Delphi-Random natürlich im Prinzip nur ein aufgemotztes "Standard-Random" mit denselben Auffälligkeiten.

[TurboMagic]

Danke für die Grafiken. Wäre es möglich den Quellcode
des erzeugenden Programms zu bekommen?

[DieDolly]

Ist tatsächlich nur das hier

Delphi-Quellcode:

procedure TForm1.RandomClick(Sender: TObject);
var
 x, y: Integer;
 bmp: TBitmap;
begin
 bmp := TBitmap.Create;
 try
  // 4 MB files
  bmp.Width := 1024;
  bmp.Height := 1024;

  for x := 0 to bmp.Width - 1 do
   begin
    for y := 0 to bmp.Height - 1 do
     begin
      bmp.Canvas.Pixels[x, y] := RandomLong; // Aufrufen was man braucht ..
     end;
   end;
 finally
  bmp.SaveToFile('Random-' + TButton(Sender).Caption + '.bmp');
  bmp.Free;
 end;
end;

[Codehunter]

Zitat:

Zitat von DieDolly (Beitrag 1452239)

Random-DEC und Random-MT19937 schneiden am besten ab.
Well1024 ist durch die anfängliche Initialisierung mit dem Delphi-Random natürlich im Prinzip nur ein aufgemotztes "Standard-Random" mit denselben Auffälligkeiten.

Wie interpretiert man diese Grafik eigentlich? Ich wollte mir die mal genauer anschauen aber wie es scheint, ist irgendwo in der Kette zwischen deiner Delphi-Routine und dem Discord-Server eine JPEG-Konvertierung dazwischen gerutscht. Verlustbehaftete Komprimierung, damit wertlos geworden. Mir fehlt aber auch die Zeit, die verschiedenen Random-Algos zusammen zu suchen und ein eigenes Programm aufzusetzen.

EDIT: Wäre jedenfalls spannend, dieses Programm mitsamt aller nötigen externen Libs hier zur Verfügung zu stellen und auf verschiedenen Systemen zu testen. Wenn ich mich nicht irre, sind manche Algos von den CPUs und Mainboards abhängig.

[Sherlock]

Zitat:

Zitat von Codehunter (Beitrag 1452330)

Wie interpretiert man diese Grafik eigentlich?

Es geht um die Gleichmäßigkeit des Rauschens. Je weniger Form darin zu erkennen ist, desto zufälliger soll der Algorithmus sein. Allerdings ist das ein recht subjektiver Test. Eine simple Balkengrafik hätte ich für besser auswertbar gehalten.

Sherlock

[Codehunter]

Zitat:

Zitat von Sherlock (Beitrag 1452332)

Zitat:

Zitat von DieDolly (Beitrag 1452057)

Zitat:

Man kann Grafiken auch verkleinern.

Das ist eine ziemlich schlechte Idee bei Grafiken, bei denen es aufs Detail ankommt.

Besser als nix zu sehen... Und manchmal reicht es auch ein anderes Format zu wählen.

Das seh ich aber ganz anders. DieDolly hat das eigentlich völlig richtig gemacht. Erst als BMP erzeugt und dann als PNG umgewandelt. GIF wäre IMHO auch gegangen oder TIFF. Wobei keines davon einen wesentlichen Unterschied in der Dateigröße hätte bewirken können. Schließlich ging es ja absichtlich um Random Noise und der lässt sich für gewöhnlich nicht komprimieren. Man könnte auch sagen: Je geringer das Kompressionsverhältnis zwischen BMP und PNG, umso besser war der Random-Algo ^^

Dass es bei den hier verlinkten Bildern JPEG-Artefakte gibt deutet darauf hin, dass irgendwo, ob gewollt oder nicht, eine doppelte Konvertierung vorgenommen wurde. Wenn man ein Noise-PNG hochlädt, dieses dann erst in JPEG-Pixelpampe umgewandelt und dann wieder in PNG zurück konvertiert wird, dann ist das PNG hinterher tatsächlich kleiner als vorher. Nur ist die Aussagekraft im vorliegenden Fall fast Null. Das gleiche würde zutreffen, wenn man ein Bild in der Größe verändert: Pixelpampe.

Was mir beim Betrachten des Random-DEC-Bildes auffällt: Zumindest macht es in der zermatschten JPG-Darstellung den Eindruck als hätte der Algo einen hohen 0-Anteil. Es kommen jedenfalls wesentlich mehr dunkle Pixel (= niedrige Int-Werte) vor als bei den anderen. Ob die nun tatsächlich schwarz (= 0) oder nur sehr dunkel waren, kann man wegen der Pixelpampe nicht mehr beurteilen.

[DieDolly]

Hier noch einmal alles in Originalgröße und völlig unkomprimiert als BMP im Archiv. Es ist leider eine Sache der Unmöglichkeit diese Bilder auf img42.com hochzuladen.
Dort kann man angeblich Bilder unkomprimiert hochladen aber immer wenn ich ein 4MB-Bild dort hochlade, ist die Seite kurz darauf offline!
Hier im Forum kann ich gerade auch nichts hochladen. Deswegen so...

Teil 1 des Archivs
https://cdn.discordapp.com/attachmen.../Random.7z.001

Teil 2 des Archivs
https://cdn.discordapp.com/attachmen.../Random.7z.002

[Rollo62]

Delphi-Quellcode:

bmp.Canvas.Pixels[x, y] := RandomLong; // Aufrufen was man braucht ..

Ich frage mich wie man das optisch interpretieren sollte.
Auf den ersten Blick würde ich Erwarten das es grau wird (als Mittelwert aller Farben),
das manche Bilder eher weiss, manche eher schwarz wirken finde ich schonmal seltsam.

Das man da keinerlei Muster erkennen sollte ist auch klar.

Vielleicht macht es Sinn aus den Pixeln die Helligkeitswerte o.ä. zu berechnen,
um dann den "Grauwert" zu bekommen, der sollte ja eigentlich wirklich in der Mitte liegen.
(Weder hell noch dunkel).

Oder sehe ich das falsch (Zugegeben, ich bin jetzt kein Statistikbild-Experte) ?

[Codehunter]

Naja, es spielt ja auch der Faktor subjektive Wahrnehmung mit rein. Unser Hirn sucht automatisch nach Mustern und sieht auch welche wo keine sind.

Da ein Farbpixel aus wenigstens 3 Byte besteht, müsste demnach ein gutes Zufallsmuster nach dem hier verwendeten Mechanismus aus vielen bunten und unterschiedlich hellen Pixeln bestehen. Je einheitlicher die Helligkeitswerte (Grauwerte) würden, umso weniger zufällig wären die Zahlen.

[jobo]

Zitat:

Zitat von DieDolly (Beitrag 1452339)

Hier noch einmal alles in Originalgröße ...

Also ich könnte nicht behaupten, dass mein Monitor dafür geeignet ist, aber bei WELL sehe ich Wellen.

Das entspricht auch meiner Wahrnehmung, wenn ich bei Siedler immer verliere, die Würfel liefern kein Rauschen, sondern lassen mich gnadenlos im Wellental absaufen.
;)

[DieDolly]

Well basiert bein der Initialisierung auf dem Standard-Random. Von daher ist alles was folgt "wellig".

[Rollo62]

Zitat:

Zitat von Codehunter (Beitrag 1452368)

Naja, es spielt ja auch der Faktor subjektive Wahrnehmung mit rein. Unser Hirn sucht automatisch nach Mustern und sieht auch welche wo keine sind.

Da ein Farbpixel aus wenigstens 3 Byte besteht, müsste demnach ein gutes Zufallsmuster nach dem hier verwendeten Mechanismus aus vielen bunten und unterschiedlich hellen Pixeln bestehen. Je einheitlicher die Helligkeitswerte (Grauwerte) würden, umso weniger zufällig wären die Zahlen.

Ja, ich meinte ja auch zusätzlich die Helligkeitsverteilung, nicht statt der Farbe:
1. Farbe: gut zum Suchen nach Mustern
2. Grau : gut zum checken ob es gleichmäßiges Rauschen um eine mittlere Helligkeit ist

Zu 2. meine ich, wenn man dann über alle Pixel eine Statistik bildet müsste der Mittelwert bei exakt 127 liegen, und die Verteilung möglichst gleichmäßig.
Es wäre aber die Frage ob ein Random eines LongInt auch ein Random seiner einzelnen Bytes erzeugt (davon gehe ich mal gefühlsmäßig aus),
kenne die tiefere Methematik aber nicht.

[Luckie]

Dolly: "Random-DEC und Random-MT19937 schneiden am besten ab."
Sherlock: "Es geht um die Gleichmäßigkeit des Rauschens. Je weniger Form darin zu erkennen ist, desto zufälliger soll der Algorithmus sein."

Also gerade bei den beiden sehe ich auffällige Muster. Zumindest hier auf dem Tablet.

[Sherlock]

Zitat:

Zitat von Luckie (Beitrag 1452382)

Dolly: "Random-DEC und Random-MT19937 schneiden am besten ab."
Sherlock: "Es geht um die Gleichmäßigkeit des Rauschens. Je weniger Form darin zu erkennen ist, desto zufälliger soll der Algorithmus sein."

Also gerade bei den beiden sehe ich auffällige Muster. Zumindest hier auf dem Tablet.

Das ist nur meine Interpretation der ganze Geschichte hier...ich tendiere nur dazu, jeden Blödsinn, den ich von mir gebe mit reichlich Autorität zu unterlegen, darum glaubt man mir. Dennoch fände ich ein Balkendiagramm verständlicher. Gauss hat für seine Glockenkurve auch nicht Punkte auf einem Blatt Papier verteilt, sondern eben Häufigkeiten in ein geeignetes Koordinatensystem eingetragen. Und da kann man Häufungen auf den ersten Blick erkennen.

Sherlock

[Michael II]

Irgendwelche erkennbare Muster in den Bildern deuten daraufhin, dass der Pseudo-Zufallsgenerator eher P als Z ist ;-). Umgekehrt bedeuten Bilder ohne erkennbare Muster nicht unbedingt, dass der Generator gut ist.

Man muss die Bilder unkomprimiert betrachten. Aber auch unkomprimiert ergeben sich bei Dollys "Experiment" Muster beim Delpi Generator.

Auf HD Monitoren (oder schlechter und generell) sollte man beachten, dass die Bilder "in Originalgrösse" betrachtet werden. Werden die Bilder vom Anzeigeprogramm skaliert entstehen Muster, welche im Originalbild nicht vorhanden sind.

Für Tests mit dem Delphi Generator empfehle ich dir einen Initialwert randseed := ... zu setzen, dann werden - wenn andere experimentieren - die gleichen Zahlenfolgen erzeugt.

Wenn man den in asm geschriebenen Delphigenerator (Delphi 10.3.3) betrachtet, dann ist es nicht erstaunlich, dass die erzeugten Zahlen weit weg von "echtem Zufall" sind (hier asm Code in Delphi umgesetzt):

Delphi-Quellcode:

function ra( arange : integer ): integer;
(*
        PUSH    EAX
        IMUL    EAX,RandSeed,08088405H
        INC     EAX
        MOV     RandSeed,EAX
        POP     EDX
        MUL     EDX
        MOV     EAX,EDX
        *)
var eax, edx : cardinal;
    edxeax : Uint64;
begin
  eax := randseed * 134775813; // 3*17*131*20173
  inc( eax );
  randseed := eax;
  edxeax := arange*eax;
  edx := edxeax shr 32;
  Result := edx;
end;

Du erreichst u.U. eine bessere Verteilung, wenn du den Generator statt einmal eine grosse Zahl drei mal Zahlen in einem kleineren Intervall erzeugen lässt, zum Beispiel im Intervall [0,256[ (dabei spielt die Rechengenauigkeit des Generators eine wesentliche Rolle):

Delphi-Quellcode:

  hb := TBitMap.Create;
 try
  hb.SetSize( 1024,1024 );
  hb.PixelFormat := pf32bit;

  for x := 0 to hb.Width-1 do
    for y  := 0 to hb.Height-1 do
      begin
        hb.Canvas.Pixels[x,y] := RGB(random(256),random(256),random(256)); // statt random( $1000000 );
      end;

  hb.SaveToFile( 'C:\Users\micha\Desktop\bm2.bmp' );
 finally
  hb.Free;
 end;

Wenn du die Qualität eines P Zufallgenerators testen willst, reichen diese Bilder natürlich nicht.

[Frickler]

Haste die Generatoren einlaufen lassen? Also erstmal jeweils ein paar tausend Werte abgefragt, bevor Du ihn benutzt?

[Stevie]

Solang eh nur 32bit Zahlen rauskommen isses eh Mumpitz, damit kannst nicht mal nen Skatspiel (!32) vernünftig mischen.

[DieDolly]

Was beim Mersenne übrigens scheinbar kein bisschen zu funktionierern scheint ist es Integer einfach in Int64 umzuschreiben
Hier mal die komplette Unit wenn die jemanden interessiert

Delphi-Quellcode:

unit Shared.Math.Random.MT19937;

{$R-} {range checking off}
{$Warnings OFF}
// {$Q-} {overflow checking off}
{----------------------------------------------------------------------
 Mersenne Twister: A 623-Dimensionally Equidistributed Uniform
 Pseudo-Random Number Generator.

 What is Mersenne Twister?
 Mersenne Twister(MT) is a pseudorandom number generator developped by
 Makoto Matsumoto and Takuji Nishimura (alphabetical order) during
 1996-1997. MT has the following merits:
 It is designed with consideration on the flaws of various existing
 generators.
 Far longer period and far higher order of equidistribution than any
 other implemented generators. (It is proved that the period is 2^19937-1,
 and 623-dimensional equidistribution property is assured.)
 Fast generation. (Although it depends on the system, it is reported that
 MT is sometimes faster than the standard ANSI-C library in a system
 with pipeline and cache memory.)
 Efficient use of the memory. (The implemented C-code mt19937.c
 consumes only 624 words of working area.)

 home page
 http://www.math.keio.ac.jp/~matumoto/emt.html
 original c source
 http://www.math.keio.ac.jp/~nisimura/random/int/mt19937int.c

 Coded by Takuji Nishimura, considering the suggestions by
 Topher Cooper and Marc Rieffel in July-Aug. 1997.

 This library is free software; you can redistribute it and/or
 modify it under the terms of the GNU Library General Public
 License as published by the Free Software Foundation; either
 version 2 of the License, or (at your option) any later
 version.
 This library is distributed in the hope that it will be useful,
 but WITHOUT ANY WARRANTY; without even the implied warranty of
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
 See the GNU Library General Public License for more details.
 You should have received a copy of the GNU Library General
 Public License along with this library; if not, write to the
 Free Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
 02111-1307  USA

 Copyright (C) 1997, 1999 Makoto Matsumoto and Takuji Nishimura.
 When you use this, send an email to: [e-mail]
 with an appropriate reference to your work.

 REFERENCE
 M. Matsumoto and T. Nishimura,
 "Mersenne Twister: A 623-Dimensionally Equidistributed Uniform
 Pseudo-Random Number Generator",
 ACM Transactions on Modeling and Computer Simulation,
 Vol. 8, No. 1, January 1998, pp 3--30.


 Translated to OP and Delphi interface added by Roman Krejci (6.12.1999)

 http://www.rksolution.cz/delphi/tips.htm

 Revised 21.6.2000: Bug in the function RandInt_MT19937 fixed
 ----------------------------------------------------------------------}

interface

{Period parameter}
const
 MT19937N = 624;

type
 TMT19937StateArray = array [0 .. MT19937N - 1] of Int64; // the array for the state vector

procedure sgenrand_MT19937(seed: Int64); // Initialization by seed
procedure lsgenrand_MT19937(const seed_array: TMT19937StateArray); // Initialization by array of seeds
procedure randomize_MT19937; // randomization
function randInt_MT19937(Range: Int64): Int64; overload; // Int64 Random with positive range
function randInt_MT19937(Min, Max: Int64): Int64; overload; // Int64 Random with positive range between min and max
function genrand_MT19937: Int64; // random Int64 (full range);
// function randFloat_MT19937: Double; // float RANDOM on 0..1 interval

implementation

{Period parameters}
const
 MT19937M = 397;
 MT19937MATRIX_A = $9908B0DF; // constant vector a
 MT19937UPPER_MASK = $80000000; // most significant w-r bits
 MT19937LOWER_MASK = $7FFFFFFF; // least significant r bits

 // Tempering parameters
 TEMPERING_MASK_B = $9D2C5680;
 TEMPERING_MASK_C = $EFC60000;

type
 Int64Rec = packed record
  case Integer of
   0:
    (Lo, Hi: Cardinal);
   1:
    (Cardinals: array [0 .. 1] of Cardinal);
   2:
    (Words: array [0 .. 3] of Word);
   3:
    (Bytes: array [0 .. 7] of Byte);
 end;

var
 mt: TMT19937StateArray;
 mti: Int64 = MT19937N + 1; // mti=MT19937N+1 means mt[] is not initialized

 // Initializing the array with a seed
procedure sgenrand_MT19937(seed: Int64);
var
 i: Int64;
begin
 for i := 0 to MT19937N - 1 do
  begin
   mt[i] := seed and $FFFF0000;
   seed := 69069 * seed + 1;
   mt[i] := mt[i] or ((seed and $FFFF0000) shr 16);
   seed := 69069 * seed + 1;
  end;

 mti := MT19937N;
end;

{
 Initialization by "sgenrand_MT19937()" is an example. Theoretically,
 there are 2^19937-1 possible states as an intial state.
 This function (lsgenrand_MT19937) allows to choose any of 2^19937-1 ones.
 Essential bits in "seed_array[]" is following 19937 bits:
 (seed_array[0]&MT19937UPPER_MASK), seed_array[1], ..., seed_array[MT19937-1].
 (seed_array[0]&MT19937LOWER_MASK) is discarded.
 Theoretically,
 (seed_array[0]&MT19937UPPER_MASK), seed_array[1], ..., seed_array[MT19937N-1]
 can take any values except all zeros.
}

procedure lsgenrand_MT19937(const seed_array: TMT19937StateArray);
var
 i: Int64;
begin
 for i := 0 to MT19937N - 1 do
  mt[i] := seed_array[i];

 mti := MT19937N;
end;

function genrand_MT19937: Int64;
const
 mag01: array [0 .. 1] of Int64 = (0, MT19937MATRIX_A);
var
 y, kk: Int64;
begin
 if mti >= MT19937N then // generate MT19937N Int64 at one time
  begin
   if mti = (MT19937N + 1) then // if sgenrand_MT19937() has not been called,
    sgenrand_MT19937(4357); // default initial seed is used

   for kk := 0 to MT19937N - MT19937M - 1 do
    begin
     y := (mt[kk] and MT19937UPPER_MASK) or (mt[kk + 1] and MT19937LOWER_MASK);
     mt[kk] := mt[kk + MT19937M] xor (y shr 1) xor mag01[y and $00000001];
    end;

   for kk := MT19937N - MT19937M to MT19937N - 2 do
    begin
     y := (mt[kk] and MT19937UPPER_MASK) or (mt[kk + 1] and MT19937LOWER_MASK);
     mt[kk] := mt[kk + (MT19937M - MT19937N)] xor (y shr 1) xor mag01[y and $00000001];
    end;

   y := (mt[MT19937N - 1] and MT19937UPPER_MASK) or (mt[0] and MT19937LOWER_MASK);
   mt[MT19937N - 1] := mt[MT19937M - 1] xor (y shr 1) xor mag01[y and $00000001];
   mti := 0;
  end;

 y := mt[mti];
 Inc(mti);
 y := y xor (y shr 11);
 y := y xor (y shl 7) and TEMPERING_MASK_B;
 y := y xor (y shl 15) and TEMPERING_MASK_C;
 y := y xor (y shr 18);

 Result := y;
end;

// Delphi interface

procedure randomize_MT19937;
var
 OldRandSeed: Integer;
begin
 OldRandSeed := System.RandSeed; // save system RandSeed value
 System.Randomize; // randseed value based on system time is generated
 sgenrand_MT19937(System.RandSeed); // initialize generator state array
 System.RandSeed := OldRandSeed; // restore system RandSeed
end;

// rewritten to delphi code due to 64bit compatibility
// Uwe Raabe -  delphipraxis.com
function randInt_MT19937(Range: Int64): Int64;
begin
 Result := Int64Rec(Int64(Range) * Cardinal(genrand_MT19937)).Hi;
end;
// bug fixed 21.6.2000.
// asm
// PUSH EAX // Parameter 1 = Range auf Stack sichern
// CALL genrand_MT19937 // Random Int64 aufrufen, Ergebnis steht in EAX (keine Parameter)
// POP EDX // Range vom Stack in EDX holen
// MUL EDX // EAX mit EDX multiplizieren, Ergebnis steht in EDX,EAX
// MOV EAX,EDX // Die h�heren 32-Bits in EDX als Result in EAX zur�ckgeben
// end;

function randInt_MT19937(Min, Max: Int64): Int64;
begin
 Result := randInt_MT19937(Max - Min) + Min;
end;

// function randFloat_MT19937: Double;
// const
// Minus32: Double = -32.0;
// asm
// CALL    genrand_MT19937
// PUSH    0
// PUSH    EAX
// FLD     Minus32
// FILD    qword ptr [ESP]
// ADD     ESP,8
// FSCALE
// FSTP    ST(1)
// end;

initialization

// added 25.11.2019
randomize_MT19937;

end.

[Michael II]

Zitat:

Zitat von Stevie (Beitrag 1452396)

Solang eh nur 32bit Zahlen rauskommen isses eh Mumpitz, damit kannst nicht mal nen Skatspiel (!32) vernünftig mischen.

Ja wenn Z die Menge aller Zufallszahlen und V die Menge aller Kartenverteilungen ist und du jedem z aus Z eine Kartenverteilung v aus V zuordnen willst, dann ist die Funktion F:Z->V natürlich nicht surjektiv. (V mächtiger als Z.)

Das ist aber kein Problem, da du eine beliebige Anzahl von Zufallszahlen erzeugen kannst und so immer eine Funktion F:ZxZ..xZ -> V findest, welche alle Elemente von V trifft.

Es reicht also bereits ein 1 Bit Zufallsgenerator.

Problematisch ist u.U. die Periodenlänge: Bei vielen P-Zufallsgeneratoren werden ausgehend von einem Startwert s (von Startwerten s[i]) n Bit P-Zufallszahlen berechnet. Irgendwann wird dabei wieder der Startwert erreicht und alles beginnt von vorne. Dabei werden oft nicht alle möglichen 2^n Werte durchlaufen.

[Michael II]

Kennt jemand eine Delphi "Übersetzung" von David Zuckermans und Eshan Chattopadhyays Arbeit?

Infos:

https://www.chip.de/news/Diese-Nachr..._97383944.html

https://news.utexas.edu/2016/05/16/c...cybersecurity/

Paper:

https://eccc.weizmann.ac.il//report/2015/119/

[markus5766h]

Bei Ansicht dieses Artikels sind mir meine alten
Spielereien zur Zahl Pi eingefallen . . . hier
die Monte-Carlo-Methode ...

Beim Screenshot im Anhang wurde der blaue Graph mit der Methode aus Post #30 erzeugt,
beim roten Graph mit Randomize ... x:=Random, y := Random

Die Unterschiede sind mit steigender Zahl der Durchläufe eher als vernachlässigbar zu bezeichnen . . .

Die Graphen wurden mittels 2500000 Durchläufen zur Berechnung von Pi erstellt.

[Michael II]

Post #30 zeigt wie Delphi (in 10.3.3) random() berechnet.

Es ist also nicht erstaunlich, wenn random und random :) zu einem ähnlichen (schlechten Zufalls-)Resultat führen. Bei gleichem Startwert randseed sollten sogar die gleichen Zahlenreihen entstehen.

Interessant wäre wie bereits erwähnt eine Übersetzung der Arbeit von Zuckerman & Chattopadhyay (Link weiter oben) ins Delphische.

[himitsu]

Inzwischen sind die Funktionen "auch" als Pure-Pascal verfügbar (für andere Platformen wo dieser Assembler nicht läuft)
und was ich grad bemerkte und als besonders praktisch empfand, wurden dort irgendwann zwei Variablen eingebaut, so dass man da ein eigenes Random (IntRandom) und Randomize registrieren und es somit auch "überall" im Delphi austauschen kann. :shock:

PS: Das aus #30 noch ein bissl zusammengefasst, dann kommt das bei raus.

Delphi-Quellcode:

function ra(aRange: Integer): Integer;
begin
  RandSeed := RandSeed * 134775813 + 1; // 3*17*131*20173
  Result := (Int64(aRange) * RandSeed) shr 32;  // aka Result := MulDiv(aRange, RandSeed, $100000000);
end;

Aber die Grundlagen des "deterministic linear congruential generator with 134775813 as a and 1 as c" haben sich nicht geändert.
Das ist seit über 20 Jahren konstant. Nur wurde vor längerer Zeit mal das GetTickCount gegen QueryPerformanceCounter im Randomize ersetzt, womit ein "falsch" benutztes und zu oft/schnell aufgerufenes Randomize keine großen Nachteile bringt.

Delphi-Quellcode:

type
  TRandom32Proc = function: UInt32;
  TRandomizeProc = procedure(NewSeed: UInt64);

function DefaultRandom32: UInt32;
procedure DefaultRandomize(NewSeed: UInt64);

var
  Random32Proc: TRandom32Proc = DefaultRandom32;
  RandomizeProc: TRandomizeProc = DefaultRandomize;

procedure Randomize;

function Random(const ARange: Integer): Integer; overload;
function Random: Extended; overload;



function DefaultRandom32: UInt32;
{$IFDEF PUREPASCAL}
begin
  Result := UInt32(RandSeed) * $08088405 + 1;
  RandSeed := Result
end;
{$ELSE !PUREPASCAL}
asm
{     <-EAX     Result  }
{$IFDEF PIC}
        PUSH    EBX
        CALL    GetGOT
        MOV     EBX,EAX
        MOV     ECX,[EBX].RandSeed
        IMUL    EAX,[ECX],08088405H
        INC     EAX
        MOV     [ECX],EAX
        POP     EBX
{$ELSE !PIC}
        IMUL    EAX,RandSeed,08088405H
        INC     EAX
        MOV     RandSeed,EAX
{$ENDIF !PIC}
end;
{$ENDIF !PUREPASCAL}

function Random(const ARange: Integer): Integer;
{$IFDEF PUREPASCAL}
var
  Temp: UInt32;
begin
  Temp := Random32Proc;
  Result := (UInt64(UInt32(ARange)) * UInt64(Temp)) shr 32;
end;
{$ELSE !PUREPASCAL}
asm
{     ->EAX     Range   }
{     <-EAX     Result  }
{$IFDEF PIC}
        PUSH    EBX
        PUSH    EAX
...

[Michael II]

Es ist mir bewusst, dass der Code aus #30 zusammengefasst werden kann. Es ging ja darum den ASM Code Zeile für Zeile in Delphi zu schreiben.

Deine Zusammenfassung von #30 liefert bei mir bei einem Startwert von randseed=1 bereits beim zweiten Aufruf von random(1000000) nicht mehr den korrekten Wert zurück. Es liegt wahrscheinlich an meinen Compilerschaltern (?). Wenn du's so geschrieben hättest...

Delphi-Quellcode:

function random(aRange: Integer): Integer;
begin
{$Q-}
{$R-}
  RandSeed := RandSeed * 134775813 + 1; // 3*17*131*20173
  Result := (aRange * Cardinal(RandSeed)) shr 32; // aka Result := MulDiv(aRange, RandSeed, $100000000);
end;

...dann wäre auch mein australisches Delphi zufrieden.

Infos zum Verfahren:
https://de.wikipedia.org/wiki/Kongruenzgenerator

[Rollo62]

@himitsu
QueryPerformanceCounter ist aber auch nur für Windows relevant ...

Ich habe jetzt nicht die hohen Ansprüche daran herauszufinden ob der Zufall in unserem Universum überhaupt existiert und gleichverteilt geblieben ist über die letzten 13 Mrd. Jahre,
aber gut dass die Funktionen jetzt im Source vorhanden sind, ist eine gute Sache. :thumb: