Random(2) in schnell

[Nikolas]

Was machst du denn überhaupt mit den Zahlen? Vielleicht gibt es eine Möglichkeit, das Ganze anders anzusetzen.

[Amateurprofi]

Vielleicht liege ich jetzt völlig falsch, aber ich versuche es mal.

Du bist der Auffassung, die Nutzung der Random Funktion nähme zuviel Zeit in Anspruch.
Wenn das so sein sollte : Was macht Dein Programm, außer ausschließlich die Random-Funktion aufzurufen ?
Ein Aufruf Random(2) benötigt 24 CPU-Ticks (GetTickCount=16 CPU-Ticks)

QueryPerformanceFrequency ist als Alternative natürlich nicht tauglich, denn die liefert dir die Frequenz von QueryPerfomanceCounter, sollte also ein konstanter Wert sein.

Das Ergebnis von QueryPerformanceCounter wäre eine Alternative, allerdings braucht das ca. 2900 Ticks also mehr als 100 mal so viel wir Random(2).

Statt des lahmen QPC könntest Du den Time Stamp Counter direkt abfragen, aber auch das braucht 88 CPU-Ticks, also fast 4 mal so viel wie Random(2).

Delphi-Quellcode:

FUNCTION TimeStamp:Int64;
asm
   rdtsc
end;

Wenn du, was das Beitrag vermuten läßt, eine Zufallszahl im Bereich 0..1 haben möchtest könntest du das so realisieren

Delphi-Quellcode:

FUNCTION Random2:integer;
asm
   rdtsc
   and eax,1
end;

Wenn ich das alles völllig falsch verstanden habe, dann ignoriere das Obige bitte.

[3_of_8]

Zitat:

Zitat von Der_Unwissende

Zitat:

Zitat von glkgereon

Leider scheint Random kein Int64 zu unterstützen :?

Hi,
dafür unterstützt es als Ausgabe 80Bit-Extended Werte :wink:

Man sollte aber wahrscheinlich nur die Mantisse verwenden. Das Zero-Bit wird meißtens 1 sein und das Sign-Bit immer 0. Der Exponent wird denke ich auch nicht stark genug schwanken.

[brechi]

der Zufallsgenerator von Delphi mal in Assembler und für 1/0 optimiert:

Delphi-Quellcode:

  asm
    @@nochma:
    imul ecx, ecx, $8088405 // vielleicht hier mal experimentieren
    inc ecx
    //mov edx, ecx

    js @@ist1
// wenn 0 mache:
    nop

    jmp @@nochma
    @@ist1:
// wenn 1 mache:
    nop

    jmp @@nochma
  end;

[negaH]

Mersenne Twister kanste vergessen, zu langsam.

Aber zum Angang machst du mal was anders ;)

Erzeuge eine 323Bit Zufallszahl. Diese global speichern. Bei der Berechnung in deinen Funktionen dann diese Funktion

Delphi-Quellcode:

var
  Zufall: Caridnal = 0;

function RandomBit: Boolean;
begin
  Zufall := Zufall shr 1 or Zufall shl 31;
  Result := Odd(Zufall);
end;

initialization
  Randomize;
  Zufall := Random(MaxInt);
end.

Dies produziert zwar immer die gleiche Sequenz aus 32 Bits, aber dies spielt zur Einschätzung, um wieviel du durch die Optimierung deines RNGs an Zeit einsparen könntest, keine Rolle.

Im alten DEC war ein TRandom_LFSR mit Perioden von 2^32-1 bis 2^2032-1 bei dem der LFSR 128 mit Periode 2^128-1 ungefähr 43Mb/Sec auf einem P4 1.5GHz lief. Du könntest dir aus dem Source dieses LFSR extrahieren.

Gruß Hagen

[glkgereon]

Ok, ich denke es ist an der Zeit mal genauer den "Sinn" des Projektes zu erläutern.

Im Prinzip geht es um ein OnlineGame.
Bei diesem Spiel ist es möglich Waffen mithilfe von Edelsteinen zu veredeln. (Um Schaden zu erhöhen...)
Hierbei gibt es Waffenstufen von 0 bis 15.
Für jeden Up-Versuch wird ein Stein benötigt.
Es besteht eine 50%-Chance dass der Versuch erfolgreich ist (Stufe wird um eins erhöht)
Schlägt der Versuch fehl, wird die Stufe verringert (Allerdings nur falls die neue Stufe nicht unter 3 liegt...d.h. bei einem Fehlschlag bei Stufe 0,1,2 oder 3 bleibt alles wie es ist).

Ziel ist es einen Simulator dazu zu schreiben, welcher die Steine zählt die man braucht um eine Waffe von 0 auf 15 zu bringen.
Quelltext ist folgender:

Delphi-Quellcode:

while Akt<>Config.Ziel do //Akt = Aktuelle Stufe
begin
  if Rnd>31 then begin R:=Random(MaxInt); Rnd:=0; end; //Letztes Bit meines 32Bit Random-Werts => Neue Zahl
  if (R and (1 shl Rnd))<>0 then //Aktuelles Bit true?
    Inc(Akt) //Eins Hoch
  else if Akt>3 then Dec(Akt); //Sonst wenn Stufe>3 dann runter
  Inc(C); //Versuch zählen
  Inc(Rnd); //Nächstes Bit
end;

Ich hoffe es ist klar dass ein "nicht zufälliger zufallsgenerator" mir nicht weiterhilft :-)

Ein weiteres Problem, welches mir soeben aufgefallen ist ist der Array den ich für meine Ergebnisse nutze...
insgesamt sieht das so aus:

Delphi-Quellcode:

TUpper = class
// ...
  FRes64: array of Int64;
end;

procedure TUpper.Generate(Cnt: Int64);
var Akt, Rnd: Byte;
    C, Len: Int64;
    R: Integer;
begin
  Len:=Length(FRes64);
  Rnd:=255;
  R:=0;
  while Cnt>0 do
  begin
    Akt:=Config.Start;
    C:=0;
    while Akt<>Config.Ziel do
    begin
      if Rnd>31 then begin R:=Random(MaxInt); Rnd:=0; end;
      if (R and (1 shl Rnd))<>0 then
        Inc(Akt)
      else if Akt>3 then Dec(Akt);
      Inc(C);
      Inc(Rnd);
    end;
    if C>=Len then
    begin
      Len:=C+1;
      SetLength(FRes64,Len);
    end;
    Inc(FRes64[C]);
    Dec(Cnt);
  end;
end;

in anbetracht der Tatsache dass Random nur 22 Cycles benötigt, liegt es vielleicht doch eher am SetLength?
(Wie) kann man das optimieren?

Daher stellt sich mir nun die Frage ob man hier überhaupt noch groß optimieren kann...(Aber da vertrau ich ganz auf euch :wink: )
Im Moment braucht diese Funktion so wie sie da steht für 100.000.000 Durchläufe 386 Sekunden auf einem AMD 3000+ (seperater Thread, tpLower, Opera,Miranda usw im Hintergrund laufend)

[Nikolas]

Bei so einem Problem solltest du dich eher an einem Stochastiker wenden. Gut Möglich, dass du im Matheboard.de jemanden mit einer Lösung finden kannst. Du hast hier einen Random-Walk in einem beschränkten Intervall, vielleicht hat schon jemand eine analytische Lösung gefunden.

[Der_Unwissende]

Zitat:

Zitat von 3_of_8

Man sollte aber wahrscheinlich nur die Mantisse verwenden. Das Zero-Bit wird meißtens 1 sein und das Sign-Bit immer 0. Der Exponent wird denke ich auch nicht stark genug schwanken.

Warum sollte denn der Exponent nicht stark genug schwanken? Ich meine die Random-Funktion erzeugt recht gleichverteilt Zahlen zwischen 0 und 1 (idealerweise). Das wiederum heißt, dass alle negativen Exponenten recht gleichmässig verwendet werden können (oder übersehe ich etwas?), was wohl wieder ein Bit weniger bedeutet. Bleiben von den 80 Bit eines Extended immer noch 77 übrig. Das sind immer noch mehr Bits als bei einem Int64 nötig währen, die schwanken (Sinn und Nutzen mal außen vor)


Gruß Der Unwissende

[3_of_8]

Stimmt, wenn man das Sign-Bit des Exponenten rauslässt, könnte es gehen. Und man spart sich auch die Multiplikation, die man hat, wenn man das ganze in einen Integer umrechnet.

[grenzgaenger]

sag mal, was machst du eigentlich da?

Delphi-Quellcode:

if C>=Len then
    begin
      Len:=C+1;
      SetLength(FRes64,Len);
    end;
    Inc(FRes64[C]);

ich kann mir nicht vorstllen, dass du 2^32 ergebnisse auf dem bildschirm sehen möchtest. schränk das doch mal ein und bau dir eine vernünftige datenstruktur auf, anstatt immer den speicher umzumodeln...