Random ist kein reiner Zufall

[Der_Unwissende]

Zitat:

Zitat von dino

"Der Zieloperand ist sowohl beim mul wie beim imul Befehl immer das AL oder AX Register."

EAX = 32 Bit
AX = 16 Bit
AL = 8 Bit

Das sind nur 3 Bezeichner für das gleiche Register (mehr oder weniger). EAX wäre auf 32-Bit CPUs das volle 32 bittige Register, AX ist ein Teil dieses Registers (die unteren 16 Bit), AL wiederum ist ein Teil des AL-Registers (die unteren 8 Bit). AX würde sich aus AH und AL zusammensetzen.
Für aktuelle 32-Bitter sollte es also EAX sein

[Christian Seehase]

Moin Dino,

Zitat:

Zitat von dino

und um die Frage zu beantworten gucke ich mir nun an, wie Random programmiert ist

womit sich, IMHO, in diesem Thread kein Assembler Grundkurs rechtfertigt.

[dino]

random ist doch in assembler sprache geschrieben

den assembler grundkurs von hier habe ich mir bereits durchgelesen und ich wollte nurnoch hinausgehende sachen fragen, de aus dem kurs nciht hervorgingen

[dino]

könnte jemand noch den restlichen code posten?

ich weiss ja nciht, was das ist aber Random ist das nicht
und Randomize auch nicht

[Cöster]

Zitat:

Zitat von dino

könnte jemand noch den restlichen code posten?

ich weiss ja nciht, was das ist aber Random ist das nicht
und Randomize auch nicht

Selbstverständlich ist das Random. Wieso sollte es das nicht sein? Und wenn du es nicht glaubst, ich kann mich ein drittes Mal wiederholen, wechsel beim Debuggen einfach mal ins CPU-Fenster, dann siehst du den Code selbst.
Was in Randomize passiert, wurde hier jetzt auch schon n paar mal gesagt.

[dino]

oh tschuldige, so wollte ich das net gesagt haben

ich meinte

Delphi-Quellcode:

procedure       _RandInt; 
asm 
{     ->EAX     Range   } 
{     <-EAX     Result  } 
        PUSH    EBX 
{$IFDEF PIC} 
        PUSH    EAX 
        CALL    GetGOT 
        MOV     EBX,EAX 
        POP     EAX 
        MOV     ECX,[EBX].OFFSET RandSeed 
        IMUL    EDX,[ECX],08088405H 
        INC     EDX 
        MOV     [ECX],EDX 
{$ELSE} 
        XOR     EBX, EBX 
        IMUL    EDX,[EBX].RandSeed,08088405H 
        INC     EDX 
        MOV     [EBX].RandSeed,EDX 
{$ENDIF} 
        MUL     EDX 
        MOV     EAX,EDX 
        POP     EBX 
end;

ist nur random(3) z.b. oder?

finde ich im debugger auch den code für randomize?

[Cöster]

Zitat:

Zitat von dino

ist nur random(3) z.b. oder?

Hm? Also es ist die Funktion

Delphi-Quellcode:

function Random(const ARange: Integer): Integer;

, also auch z.B. Random(4). Die Funktion unterscheidet sich aber natürlich leicht von

Delphi-Quellcode:

function Random: Extended;

, falls du die meinst.

Zitat:

Zitat von dino

finde ich im debugger auch den code für randomize?

Ja, allerdings nur in ASM. Um seine Implementierung in Delphi-Language anzugucken, kannst du dir hier den Turbo Exlorer (kostenlos) runterladen, da ist das alles drin enthalten. Soweit ich weiß ist es aber illegal, Delphis Implementierungen zu veröffentlichen (was ich nicht verstehen kann, weil sie sich ja eh jeder angucken kann. Also korrigiert mich, wenn ich falsch liege), weswegen ich Randomize hier nicht schon längst gepostet habe.

[dino]

joa ASM komme ich ja nun ein bisschen mit klar

also Randseed wird durch die Funktion richtig geliefert, doch kriege ich hier kein ergebnis raus

und das mit dem code angucken hab ich noch nciht rausgekriegt(hab auf F9 gedrückt und dann auf Strg+Alt+C richtig?)

[Cöster]

Zitat:

Zitat von dino

joa ASM komme ich ja nun ein bisschen mit klar

Gut, aber Randomize ist in Delphi Language (eine If-Abfrage und die Zuweisung von RandSeed) deutlich leichter zu verstehen als in ASM.

Zitat:

Zitat von dino

und das mit dem code angucken hab ich noch nciht rausgekriegt

Ok, also:

• Neues Projekt
• Randomize ins FormCreate schreiben
• Haltepunkt bei Randomize setzen (auf den linken Rand des Quelltext-Editors klicken, sodass die Zeile rot markiert wird)
• F9
• Strg+Alt+C (jetzt ist das CPU-Fenster geöffnet. Die aktuelle Codezeile (call Randomize) ist markiert)
• F7 um eine Anweisung weiter zu springen (in das aufgerufene Randomize). Hier siehst du Randomize in Assembler-Form

Mit F7 kannst du dann die Zeilen einzeln durchgehen und dabei den Stack, die Register und die Flags beobachten (rechts). Das könnte bei der Analyse von Random sehr hilfreich sein.

[dino]

joa habs nun(obwohl Random bei mir wesentlich kleiner ausfällt, aber das Ergebnis bleibt das selbe)

ich bin nun auf der Suche nach result

[Cöster]

Zitat:

Zitat von dino

obwohl Random bei mir wesentlich kleiner ausfällt

Das liegt wohl daran, dass der Teil zwischen {$IFDEF PIC} und {ELSE} wegfällt.

Zitat:

Zitat von dino

ich bin nun auf der Suche nach result

:wiejetzt: Also das Result der Funktion ist das, was am Ende in EAX steht. Oder was meinst du?

[dino]

ja eigentlich meine ich das, aber da kommt bei mir immer 0 raus

[Cöster]

Also zunächst mal: Bei MUL EDX wird ja EAX mit EDX multipliziert. Das Ergebnis einer Multiplikation zweier 32Bit-Zahlen kann allerdings bis zu 64Bit beanspruchen. Deswegen wird das Ergebnis ins Registerpaar EDX:EAX geschrieben. Die 32 höherwertigen Bits stehen dabei in EDX.

Ursache dafür, dass das Result bei dir 0 ist, könnte sein:
Der Parameter ist 1 :lol:, es ist Zufall (:wink:) oder du rufst Randomize nicht auf. Denn wenn Randomize nirgendwo im Programm aufgerufen wird, ist RandSeed ja beim ersten Random-Aufruf 0. Nach folgenden 3 Zeilen ist RandSeed dann 1:

Code:

imul edx,[RandSeed],$0808804 // EDX := RandSeed(=0)*Konstante => EDX=0
inc edx                      // => EDX=1
mov [RandSeed],edx           // => RandSeed = 1

Dann wird EDX (=1) mit EAX (=Parameter, Größe: 32Bit) multipliziert. Das Ergebnis ist also EAX. Da die 32 niedrigwertigen Bits des Ergebnisses in EAX geschrieben werden, bleibt EAX unverändert (=Parameter) und EDX wird genullt.

Am Ende wird EDX (=0) dann in EAX kopiert und zurückgegeben. Deswegen ist die erste erzeugte Zufallszahl immer null, wenn Randomize nicht aufgerufen wurde.

[dino]

gehts auch mit Randomize?

schliesslich muss Random(3) ja seinen wert haben

[Cöster]

Zitat:

Zitat von dino

gehts auch mit Randomize?

schliesslich muss Random(3) ja seinen wert haben

Ich versteh nicht was du meinst. Was geht auch mit Randomize? Was ist "sein Wert"?

[QuickAndDirty]

Nachfolgend mal ein Beitrag aus google Groups
Das sollte dann wohl alle fragen beantworten.

Zitat:

Die einfachste und fuer sehr viele Zwecke ausreichende Methode ist die
sogenannte lineare Kongruenzmethode, die sich auf Rechnern leicht und schnell
implementieren laesst. Wir nehmen an, dass der Rechner z.b. mit Zahlen zwischen
0 und 2^32-1 rechnen kann.

Dann liefert die Formel

Seed_neu = (08088485h * Seed_alt + 1) mod 2^32

in Turbo-Pascal

var RandSeed:longint;

RandSeed := $08088405*RandSeed + 1;

eine Zahlenfolge, in denen saemtliche Werte zwischen 0 und 2^32-1 genau einmal
vorkommen und die sich dann wiederholt. Die Operation liefert also eine
Reihenfolge/Aufzaehlung/Permutation aller Zahlen 0..2^32-1. Diese Permutation
ist nachweislich recht "zufaellig". Um nachzuweisen, dass die Formel

Seed_neu = (c*Seed_alt + 1) mod 3^32

tatsaechlich alle Zahlen von 0..2^32-1 aufzaehlt und keine "vergisst", ist
nicht ganz einfach. Vor allem ist die Wahl von c nicht trivial. Man kann
zeigen, dass die Zahl c kongruent 5 modulo 8 sein muss, damit die obige Formel
fuer eine beliebige (!) 2-er-Potenz als Modul eine vollstaendige Permutation
0..Modul-1 liefert. c darf nicht zu gross und nicht zu klein sein, damit die
Folge dann "zufaellig" aussieht. Der obige Wert von c ist gut und wird z.b. von
der Funktion Random in Turbo-Pascal verwendet.

Die obige Folge liefert aber noch lange nicht das, was man unter einer
Zufallsfolge versteht, also z.B. unter einer zufaelligen Gleichverteilung der
Zahlen {0,1} oder allgemein {0,1,...,n-1}, denn sie ist zunaechst nur eine
Permutation, in der sich Werte nur nach 4 Milliarden Zuegen wiederholen. Dazu
muss man sie noch einer geeigneten Transformation unterwerfen, damit man nur
Werte aus {0..n-1} erhaelt, die sich dann natuerlich auch in kuerzeren
Abstaenden wiederholen sollen/muessen.

Dazu muessen hier die _hohen_ Bits von Seed "abgegriffen" werden.

Die Operation "Seed mod n" waere denkbar ungeeignet, denn sie liefert z.b. fuer
n=2 offensichtlich fuer aufeinanderfolgende Seed-Werte abwechselnd 0 und 1.

Die korrekte Transformation lautet hier

Seed := (c*Seed+1) mod 2^32
Random := (n*Seed) div 2^32 { Wert aus {0,...,n-1}

Sie sollte nur fuer maximal n=2^16 angewandt werden. D.h. fuer einen
"richtigen" Zufallszahlengenerator fuer 16-Bit-Werte braucht man einen
Zufallspermutationsgenerator von mindestens 32 Bit Laenge.

Dieser Algorithmus hat den Vorzug, dass er wahrscheinlich der
schnellstmoegliche sinnvolle Pseudeo-Zufalls-Algorithmus ist und er ist in den
meisten Compiler implementiert, die eine Zufallsfunktion bereitstellen (Basic,
Pascal,Fortran,C).

Um den Gererator bei Programmstart zu _initialisieren_ gibt es meist eine
Funktion namens Randomize, die ueblicherweise die Systemzeit ausliest und Seed
damit auf einen halbwegs nicht reproduzierberen und unerwarteten Wert setzt.
Wenn man die Zufallsfolge reproduzierbar sein soll, kann man Seed von Hand auf
einen beliebigen Wert setzen, den man sich merkt. Dann wird immer dieselbe
"Zufallsfolge" erzeugt. die Initialisierung sollte aber nur einmal geschehen,
da wiederholtes Randomize die Folge eher verschelchtert als verbessert.

Fuer sehr hohe Ansprueche gibt es erheblich kompliziertere und auch bessere
Pseudo-Zufallsgeneratoren.

cu
Horst

Da wo er einmal von "mod 3 " spricht ist wohl mod 2 gemeint.
hier die Quelle
http://groups.google.de/group/fido.g...81eb097e3b72d4

Noch etwas in Delphi kann auf mod 2^32 verzichtet werden da Variablen einfach überlaufen.

[dino]

der spricht da nirgendswo von mod 3 (oder meinst du mod3^32?)

[dino]

naja jedenfalls habe ich mit sachen wie Random := (n*Seed) div 2^32 { Wert aus {0,...,n-1} herrumgespielt doch habs immernoch nicht raus(wie gesagt: den neuen randseed kriege ich schon nur result nicht)