Delphi 11 kein RandomRange für 64-bits?

[softtouch]

Ich suche eine RandomRange Funktion die mit int64 anstatt integer arbeitet.
Habe leider bisher nichts gefunden.
Ich muss eine Zufallszahl zwischen 100000 und 9999999999 erzeugen.

[Andreas13]

Hallo Softtouch,
Du kannst die Routine System.Mathe.RandomRange(..) einfach abwandeln:

Delphi-Quellcode:

Function RandomRange(Const AFrom, ATo: UInt64): UInt64; Overload;
Begin
  IF AFrom > ATo Then
    Result:= Random(AFrom - ATo) + ATo
  Else
    Result:= Random(ATo - AFrom) + AFrom;
End;

Da das Result von Random eine Extended-Zahl ist, hast Du genug (bis zu 18..19) zufällige Ziffern, was knapp auch für den obersten Bereich von UInt64 (9223372036854775810) ausreichen dürfte.

Grüße, Andreas

[Edit]: Für Deinen Zahlenbereich zwischen 100000 und 9999999999 reicht es alle mal.

[softtouch]

Zitat:

Zitat von Andreas13 (Beitrag 1504999)

Hallo Softtouch,
Du kannst die Routine System.Mathe.RandomRange(..) einfach abwandeln:

Delphi-Quellcode:

Function RandomRange(Const AFrom, ATo: UInt64): UInt64; Overload;
Begin
  IF AFrom > ATo Then
    Result:= Random(AFrom - ATo) + ATo
  Else
    Result:= Random(ATo - AFrom) + AFrom;
End;

Da das Result von Random eine Extended-Zahl ist, hast Du genug (bis zu 18..19) zufällige Ziffern, was knapp auch für den obersten Bereich von UInt64 (9223372036854775810) ausreichen dürfte.

Grüße, Andreas

[Edit]: Für Deinen Zahlenbereich zwischen 100000 und 9999999999 reicht es alle mal.

Das erzeugt einen range check error, da ato-afrom immer noch mehr als ein integer ist.

[Andreas13]

Sorry, in der Tat. Ich habe es leider nur in der Nähe Deines oberen Breichs

Delphi-Quellcode:

Von:= 9999999999 - 500;
Bis:= 9999999999;

getestet. :oops:

Andreas

[Uwe Raabe]

Vielleicht klappt dies besser:

Delphi-Quellcode:

Function RandomRange(Const AFrom, ATo: UInt64): UInt64;
Begin
  Result:= Round(Random*(ATo - AFrom)) + AFrom;
End;

[KodeZwerg]

Vor Jahren irgendwo gefunden. Es leistete gute Dienste.

Delphi-Quellcode:

var
  vLehmerRandSeed64: Int64 = 0;
  vLehmerMultiplierA64: Int64 = 636413622384679305;
  vLehmerAdditiveConstantC64: Int64 = $1;

procedure SingleAdd(const A: LongWord; const B: LongWord; const CarryIn: LongWord; var Sum: LongWord; var CarryOut: LongWord);
var
  Temp: array [0 .. 1] of LongWord;
begin
  UInt64(Temp) := UInt64(A) + UInt64(B) + UInt64(CarryIn);
  Sum := Temp[0];
  CarryOut := Temp[1];
end;

function LehmerRandom64(ParaLehmerModulesM64: int64): int64;
var
  A: array [0 .. 1] of LongWord;
  B: array [0 .. 1] of LongWord;
  C: array [0 .. 3] of LongWord;
  vAindex: LongWord;
  vBindex: LongWord;
  vCindex: LongWord;
  vTransport: array [0 .. 1] of LongWord;
  vTransport1Index: LongWord;
  vTransport2Index: LongWord;
begin
{$RANGECHECKS OFF}
{$OVERFLOWCHECKS OFF}
  vLehmerRandSeed64 := vLehmerRandSeed64 * vLehmerMultiplierA64;
  vLehmerRandSeed64 := vLehmerRandSeed64 + vLehmerAdditiveConstantC64;
  C[0] := 0;
  C[1] := 0;
  C[2] := 0;
  C[3] := 0;
  Int64(A) := ParaLehmerModulesM64;
  Int64(B) := vLehmerRandSeed64;
  for vBindex := 0 to 1 do
  begin
    vTransport[0] := 0;
    vTransport[1] := 0;
    for vAindex := 0 to 1 do
    begin
      vCindex := vAindex + vBindex;
      Uint64(vTransport) := Uint64(A[vAindex]) * Uint64(B[vBindex]);
      for vTransport1Index := vCindex to 4 - 1 do
      begin
        if vTransport[0] = 0 then
          Break;
        SingleAdd(C[vTransport1Index], vTransport[0], 0, C[vTransport1Index], vTransport[0]);
      end;
      for vTransport2Index := vCindex + 1 to 4 - 1 do
      begin
        if vTransport[1] = 0 then
          Break;
        SingleAdd(C[vTransport2Index], vTransport[1], 0, C[vTransport2Index], vTransport[1]);
      end;
    end;
  end;
  Result := Int64(Pointer(@C[2])^);
{$OVERFLOWCHECKS ON}
{$RANGECHECKS ON}
end;

function RandomRange64(const AFrom, ATo: Int64): Int64;
begin
  if AFrom > ATo then
    Result := LehmerRandom64(AFrom - ATo) + ATo
  else
    Result := LehmerRandom64(ATo - AFrom) + AFrom;
end;

Man muss nur im Hinterkopf haben das erst ab dem zweiten Durchlauf die Zahlen variieren.

[himitsu]

Zitat:

Da das Result von Random eine Extended-Zahl ist, hast Du genug (bis zu 18..19) zufällige Ziffern, was knapp auch für den obersten Bereich von UInt64 (9223372036854775810) ausreichen dürfte.

So ganz stimmt es nicht.
Intern wird der Extended aus einem Int32 generiert, also entspricht es nur einem Single.

In diesem Fall würde ich zwei Mal Random verwenden, wenn Abs(ATo-AFrom) größer MaxInt ist.
Am Einfachsten den Abs(ATo-AFrom) halbieren, also die Bits, für das Random verwenden und es multiplizeren.

[Uwe Raabe]

Probleme bereiten könnte die Skalierung auf den Range. Bei 32-Bit wird das im 64-Bit Bereich erledigt. Für 64-Bit müsste dann 128-Bit Arithmetik verwendet werden. Ein simples Teilen und Zusammensetzen von zwei 32-Bit Randoms wird nicht so richtig funktionieren.

[peterbelow]

Zitat:

Zitat von softtouch (Beitrag 1504997)

Ich suche eine RandomRange Funktion die mit int64 anstatt integer arbeitet.
Habe leider bisher nichts gefunden.
Ich muss eine Zufallszahl zwischen 100000 und 9999999999 erzeugen.

Erzeuge eine GUID (System.SysUtils.CreateGUID) und säge 64 bits von den 128 ab, dann hast Du eine 64-bit random uint. Die mußt Du dann nur noch auf den gewünschten Range justieren :wink:

[himitsu]

Wird auch nicht ganz klappen, auf Grund der Structur von GUIDs.

Das Result nahezu immer im oberen Bereich liegen also bei 9999999999 fast immer im Bereich von 0200000000 bis 9999999999,
was dann gegen eine Normalverteilung von Zufallszahlen spricht.

[softtouch]

Zitat:

Zitat von Uwe Raabe (Beitrag 1505002)

Vielleicht klappt dies besser:

Delphi-Quellcode:

Function RandomRange(Const AFrom, ATo: UInt64): UInt64;
Begin
  Result:= Round(Random*(ATo - AFrom)) + AFrom;
End;

Dies scheint soweit die bisher einzige Lösung zu sein, die funktioniert und doch angenehm kurz ist. Ich denke, damit kann ich leben. Danke dafür.

[KodeZwerg]

Zitat:

Zitat von softtouch (Beitrag 1505023)

Dies scheint soweit die bisher einzige Lösung zu sein, die auch wirklich funktioniert.

Was bitteschön funktionierte denn bei meinem Post nicht? Danke für Klärung. Hatte es Jahrelang in Betrieb.

[softtouch]

Zitat:

Zitat von KodeZwerg (Beitrag 1505024)

Zitat:

Zitat von softtouch (Beitrag 1505023)

Dies scheint soweit die bisher einzige Lösung zu sein, die auch wirklich funktioniert.

Was bitteschön funktionierte denn bei meinem Post nicht? Danke für Klärung. Hatte es Jahrelang in Betrieb.

Sorry, habe mich schlecht ausgedrückt. Funktioniert schon, ist mir aber doch ein wenig zu lang.

[Michael II]

Zitat:

Zitat von softtouch (Beitrag 1505026)

Zitat:

Zitat von KodeZwerg (Beitrag 1505024)

Zitat:

Zitat von softtouch (Beitrag 1505023)

Dies scheint soweit die bisher einzige Lösung zu sein, die auch wirklich funktioniert.

Was bitteschön funktionierte denn bei meinem Post nicht? Danke für Klärung. Hatte es Jahrelang in Betrieb.

Sorry, habe mich schlecht ausgedrückt. Funktioniert schon, ist mir aber doch ein wenig zu lang.

Generell gilt doch: Lieber lang und richtig als kurz und falsch ;-).

Du vergleichst hier KodeZwergs Implementierung mit dem Aufruf der Delphi Implementierung (welche - oh Schreck - ebenfalls mehrere Zeilen lang ist).

Ein Blick in die Delphi Implementierung von random würde sich lohnen.
Wie himitsu bereits erwähnt: Die Funktion random liefert 32Bit Zahlen im Bereich [0,1[. random gibt also insgesamt genau 2^32 voneinander verschiedene Werte aus.

D.h. aber auch
Result:= Round(Random*(ATo - AFrom)) + AFrom;
kann nicht mehr als 2^32 voneinander verschiedene Werte zurück liefern.

Oder anders: Bei ATo-AFrom > 2^32 - wie in deinem Fall - liefert die Funktion NICHT alle möglichen Zufallszahlen zurück. => KEIN Pseudozufallsgenerator für deine Aufgabe.

Zur Verwendung von "round". Round rundet bei .5 Werten immer zur nächsten GERADEN Zahl. round hat in purer Mathematik nix verloren.

Ein Beispiel: Wenn ATo-AFrom = $80000000, dann liefert round(random*$80000000) die Werte 0 0 1 2 2 2 3 4 4 4 5 6 6 6 7... zurück. D.h. die Null wird wegen der Verwendung von round doppelt so oft generiert wie eine ungerade Zahl. Gerade Zahlen (>0) werden sogar drei mal so oft generiert wie ungerade.

Wenn du im gleichen "Fahrwasser" wie Delphi es für 32 Bit Zahlen tut Pseudozufallszahlen im UInt64 Bereich erzeugen willst, dann empfehle ich dir:
https://de.wikipedia.org/wiki/Kongruenzgenerator
https://en.wikipedia.org/wiki/Linear_congruential_generator

Eine UIn64 Implementierung könnte so aussehen:

Delphi-Quellcode:

var randseed64 : UInt64;

function mulRange( a, b : UInt64 ) : UInt64;

var ah, al, bh, bl : UInt64;
    ah_x_bh,
    ah_x_bl,
    al_x_bh,
    al_x_bl : UInt64;
    carry : UInt64;

begin
    ah := a shr 32;
    al := UInt32( a );
    bh := b shr 32;
    bl := UInt32(b);

    ah_x_bh  := ah * bh;
    ah_x_bl  := ah * bl;
    al_x_bh  := al * bh;
    al_x_bl  := al * bl;

    carry :=  (uint64(uint32(ah_x_bl)) + uint64((uint32(al_x_bh))
            + (al_x_bl shr 32 ))) shr 32;

    Result :=  ah_x_bh
            + (ah_x_bl shr 32) + (al_x_bh shr 32)
            + carry;
end;


function Random64Proc : UInt64;
// https://de.wikipedia.org/wiki/Kongruenzgenerator
// https://en.wikipedia.org/wiki/Linear_congruential_generator
begin
{$Q-}
{$R-}
  Result := UInt64(RandSeed64) * 6364136223846793005 + 1442695040888963407;
  RandSeed64 := Result;
end;


function random64( ARange : UInt64 ) : UInt64;
begin
  Result := mulRange( Random64Proc, ARange );
end;

Nicht allzu lang getestet. Ich glaube, aber es ist OK so.

Beachte, dass sowohl Delphis random(ARange) wie auch hier random64(ARange) Zahlen im Bereich [0..ARange[ (also ARange NICHT dabei) erzeugen.
(Ähnlich für Delphis RandomRange im 32 Bit Bereich)

Es gibt wesentlich bessere Generatoren, welche auf heutigen Maschinen für die meisten Anwendungen schnell genug sind. TurboMagic kann dir zum Beispiel mit seinem DEC weiter helfen.

[TurboMagic]

Hallo Michael,

danke für deine DEC Werbung ;-)
Ich hab' da neulich auch kurz nachgesehen um dann festzustellen, dass der dort enthaltene
Zufallszahlengenerator wohl auch nur 32 Bit Zahlen liefert :-(

Es darf aber gerne jemand eine Erweiterung auf 64 Bit beisteuern. Wenn die vernünftig
funktioniert nehme ich die gerne mit auf und der Autor bekommt seinen verdienten Eintrag
in der NOTICE.TXT Datei.

Also her mit den Umsetzungen! ;-)

Grüße
TurboMagic

[Stevie]

Da das E in DEC für encryption steht, frag ich mich, ob der dort genutzte RNG nicht ein Kryptographisch sicherer Zufallszahlengenerator sein muss, was bei vielen Verwendungen von Random ja nicht zwingend gegeben sein muss.

[Michael II]

Ja genau. Und deshalb kann man bei den "krypto-sicheren" auch beliebig generierte 1/8/16/32 Bit Werte aneinanderhängen bis genug. Man ist nicht auf einen 64Bitter angewiesen.

Ein 64Bit Generator kann aber natürlich trotzdem sinnvoll sein, wenn dieser für die jeweilige Verwendung mehr Speed bringt.

Nebenbei: Eine Zusammenfassung von Methoden wie man von einem durch den Generator erzeugten n-Bit Wert in einen gewünschten Bereich [0,ARange[ abbildet gibt es zum Beispiel hier.

(U.a. wird im Paper auch die von Delphi verwendete Methode beschrieben. - Beim Pseudozufallsgenerator von Delphi wird der erzeugte 32 Bit Wert als Bruch in [0..1[ interpretiert und mit ARange multipliziert. Der ganzzahlige Wert des Resultats wird ausgegeben. Dadurch werden einige Zahlen m Mal erzeugt, andere (ausser wenn ARange¦2'32) m+1 Mal. Bei sehr grossem ARange wird m=1 => random(ARange) gibt dann gewisse Zahlen (m=1+1 Mal) doppelt so häufig aus wie andere. => Bereits für Werte von ARange viel kleiner als 2^32 macht - wenn man die Zahlen wirklich pseudozufällig im "Delphi Style" erzeugt haben will - die Verwendung von random64(ARange) [siehe oben] Sinn.)

[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:

Zitat von TurboMagic (Beitrag 1505376)

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:

Zitat von TurboMagic (Beitrag 1505376)

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:

Zitat von Michael II (Beitrag 1505381)

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:

Zitat von Uwe Raabe (Beitrag 1505385)

Zitat:

Zitat von Michael II (Beitrag 1505381)

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

Delphi-Quellcode:

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)

[rabatscher]

Für meine Lib


hab ich sowas verwendet:

Delphi-Quellcode:

function TRandomGenerator.RandInt64(const aRange: Int64): Int64;
var val1, val2 : LongWord;
begin
     val1 := fRandLW($8FFFFFFF);
     val2 := fRandLW($FFFFFFFF);

     Result := ( ( Int64(val1) shl 32) + Int64(val2) ) mod aRange;
end;

fRandLW ist vom typ:

Delphi-Quellcode:

function(const ARange : LongWord) : LongWord;

Also quasi ident mit der Delphi random funktion ;)


in https://github.com/mikerabat/mrmath findest du die Klasse TRandomGenerator
Die Lib unterstützt auch die Intel RDRAND Instruktion, Mersenne Twister, ChaCha (Salsa20) und eine von Windows bereit gestellte Crypto Random Engine
die von Advapi32.dll bzw. BCrypt.dll bereit gestellt wird.

[jaenicke]

Statt auf Int64 sollte der Case eher auf UInt64 gehen. Schließlich handelt es sich um positive Werte.