Zufallsfunktion nicht zufällig / random function not random

ZX-Team Forum
Antworten
Benutzeravatar
MatthiasS
User
Beiträge: 115
Registriert: 11.05.2004, 15:29
Wohnort: Wuppertal
Kontaktdaten:

Zufallsfunktion nicht zufällig / random function not random

Beitrag von MatthiasS » 16.06.2008, 03:15

Vorsicht! Die Zufalls-Funktin des ZX81 ist scheinbar nicht so richtig zufällig.
Ich habe mal das folgende Programm unter HRG-MS laufen lassen:
  • 10 LET H=32736
    20 PRINT USR H,ON
    30 PRINT USR H,CLR
    40 PRINT USR H,PIX,255*RND,191*RND
    50 GOTO 40
Und da meit man doch, es müsse ein Bild heraus kommen mit einer zufällig verteilten Punktewolke. Kommt aber nicht! Je länger man es laufen lässt, desto deutlicher wird die Struktur. Weiss jemand, warum?


CAUTION! The random function at the zx81 is not as random as expected.
I tried the following program with HRG-MS:
  • 10 LET H=32736
    20 PRINT USR H,ON
    30 PRINT USR H,CLR
    40 PRINT USR H,PIX,255*RND,191*RND
    50 GOTO 40
We all expect to get a picture with random pixels. Surprisingly the result is far away of beeing random! The longer it runs the more you see the structure. Does anybody know why?

Bild

Benutzeravatar
nils.eilers
User
Beiträge: 111
Registriert: 31.01.2005, 14:07
Wohnort: Leverkusen
Kontaktdaten:

Re: Zufallsfunktion nicht zufällig / random function not random

Beitrag von nils.eilers » 16.06.2008, 09:14

Glücklicherweise habe ich keine mathematische Ausbildung erleiden müssen, um die Qualität der Zufallsfunktion des ZX81 beurteilen zu können. Ich weiß aber, daß das menschliche Gehirn darauf ausgelegt ist, Muster zu erkennen - oftmals sogar da, wo gar keine sind.

Natürlich liefert die RND-Funktion keinen echten Zufall, sondern eine sich wiederholende Zahlenfolge. Beim ZX81 waren das 32768 oder 65536 Zahlen, danach wiederholt sich das wieder. Diese Eigenschaft des "sich wiederholenden Zufalls" haben vor einigen Jahren gewiefte Bastler ausgenutzt, mit einem kleinen tragbaren Computer mit wenigen Spielen zu ermitteln, ob ein Geldspielautomat kurz vor einer Auszahlung steht oder nicht. Nach Bekanntwerden wurde der Zufallsgenerator auf 32 Bit umgestellt.

Benutzeravatar
bodo
User
Beiträge: 319
Registriert: 14.02.2007, 17:21
Kontaktdaten:

Re: Zufallsfunktion nicht zufällig / random function not random

Beitrag von bodo » 21.06.2008, 13:02

Die Periode des ZX-Zufallszahlengenerators habe ich mit diesem kleinen Programm ermittelt:

Code: Alles auswählen

10 LET B=RND
20 LET N=0
30 LET N=N+1
40 IF B<>RND THEN GOTO 30
50 PRINT N
Sie beträgt 65536, das heißt dass nach dieser Anzahl Aufrufen sich die Folge der gelieferten Zahlen wiederholt.

Aus meinem BASIC-Disassembly sehe ich, dass der Algorithmus etwa so läuft (SEED enthält die letzte verwendete Zufallszahl):

SEED = (((SEED + 1) * 75) mod 65537) - 1
Von RND wird dann SEED / 65536 zurückgegeben.

Anmerkungen
  • "mod" ist die Modulo-Funktion, die den Rest nach Division mit ganzen Zahlen zurückgibt; in diesem Fall eine Zahl zwischen 0 und 65536.
  • Warum die Modulo-Funktion nicht reicht, und noch eine 1 abgezogen wird, erschließt sich mir nicht.
B0D0: Real programmers do it in hex.

Benutzeravatar
siggi
User
Beiträge: 2352
Registriert: 06.12.2005, 08:34
Wohnort: D, Hessen, tiefste Werreraa
Kontaktdaten:

Re: Zufallsfunktion nicht zufällig / random function not random

Beitrag von siggi » 21.06.2008, 19:23

Damit SEED wieder 16-bittig wird?
Mehr als 65535 kriegt man da (ohne Datenkompression ;-) ) halt nicht rein.

Siggi

Benutzeravatar
MatthiasS
User
Beiträge: 115
Registriert: 11.05.2004, 15:29
Wohnort: Wuppertal
Kontaktdaten:

Re: Zufallsfunktion nicht zufällig / random function not random

Beitrag von MatthiasS » 21.06.2008, 19:48

Das erklärt aber noch nicht, warum die grafische Darstellung solche Linien ergibt, wenn man zwei aufeinanderfolgende Zufallszahlen als x- und y- Koordinaten einsetzt!

Benutzeravatar
siggi
User
Beiträge: 2352
Registriert: 06.12.2005, 08:34
Wohnort: D, Hessen, tiefste Werreraa
Kontaktdaten:

Re: Zufallsfunktion nicht zufällig / random function not random

Beitrag von siggi » 21.06.2008, 20:05

Hallo Matthias,
die RND-Funktion liefert Werte KLEINER 1. Also wird der Wert 1 nie angenommen (ich nehme mal an, es wird bei der Wandlung der "real"-Zahl in "integer" abgeschnitten und nicht aufgerundet) und Du plottest nie in Zeile 191 oder Spalte 255. Änderst Du Dein Programm, sodaß diese Zeile/Spalte auch genutzt wird, sieht Bildchen bestimmt ganz anders aus ..

Siggi

Benutzeravatar
MatthiasS
User
Beiträge: 115
Registriert: 11.05.2004, 15:29
Wohnort: Wuppertal
Kontaktdaten:

Re: Zufallsfunktion nicht zufällig / random function not random

Beitrag von MatthiasS » 22.06.2008, 00:32

Hallo Siggi,

ich habe es ausprobiert. Egal welche Faktoren ich nehme, es kommen immer seltsame Muster heraus, die immer linienartig sind.

Das geht übrigens mit jeder anderen HRG-Software genauso. Auch mit der ur-eigenen ZX81 PLOT Funktion. Man muss dann eben nur den Wertebereich begrenzen. Dann sieht man nur einen kleinen Teil von dem, was man in HRG sehen könnte.
Ich mach mal ein Beispielprogram dazu...
  • 10 LET X=200*RND
    20 LET Y=100*RND
    30 IF X>63THEN RUN
    40 IF Y>43THEN RUN
    50 PLOT X,Y
    60 RUN
Lass es mal laufen und wundere Dich!

Benutzeravatar
MatthiasS
User
Beiträge: 115
Registriert: 11.05.2004, 15:29
Wohnort: Wuppertal
Kontaktdaten:

Re: Zufallsfunktion nicht zufällig / random function not random

Beitrag von MatthiasS » 22.06.2008, 01:03

Hallo Bodo,
ich habe das auch so gesehen.
Allerdings habe ich das so verstanden:

SEED = ((SEED * 75) mod 65537) - 1

Dann habe ich mal versucht, das in Basic nachzuprogrammieren. Dann müsste man ja auch immer von SEED die nächste Zufallszahl vorhersagen können! Das hat aber nicht funktioniert. Entweder ist die Formel nicht ganz richtig, oder ich war zu blöd, das umzusetzen...
Hast Du das mal überprüft?
Matthias
Zuletzt geändert von MatthiasS am 22.06.2008, 14:28, insgesamt 1-mal geändert.

Benutzeravatar
siggi
User
Beiträge: 2352
Registriert: 06.12.2005, 08:34
Wohnort: D, Hessen, tiefste Werreraa
Kontaktdaten:

Re: Zufallsfunktion nicht zufällig / random function not random

Beitrag von siggi » 22.06.2008, 09:01

Hallo Matthias,
in Deinem obingen Testprogramm gehst Du auch nicht "fair" mit X und Y um. Denn in X-Richtung werden die Zufallszahlen auf Wertebereich 200 abgebildet und in Y-Richtung auf 100. Damit wird die X-Richtung natürlich "löchriger".
Teste mal mit gleichen Streckfaktoren, z. B.

10 LET X=43 * RND
20 LET y=43 * RND
30 PLOT X,Y
40 RUN

Das sieht dann schon symmetrischer aus, gelle?

Siggi

Benutzeravatar
MatthiasS
User
Beiträge: 115
Registriert: 11.05.2004, 15:29
Wohnort: Wuppertal
Kontaktdaten:

Re: Zufallsfunktion nicht zufällig / random function not random

Beitrag von MatthiasS » 22.06.2008, 11:50

Nein, es sind ja keine Löcher!
Es sind eben Linien! Würde die Multiplikation eine Granularität erzeugen, dann ergäben sich Punkte-Inseln zwischen horizontalen und vertikalen weißen Streifen

Man sieht den Effekt sogar noch besser bei gleichen Streckungsfaktoren von z.B. 150 für x und y! Je größer der Faktor, desto deutlicher aber auch langsamer. Dann sind die Linien nämlich genau vertikal. Es kommt dann für x jeder zweite Wert gar nicht mehr vor!
  • 10 LET X=150*RND
    20 LET Y=150*RND
    30 IF X>63THEN RUN
    40 IF Y>43THEN RUN
    50 PLOT X,Y
    60 RUN
Bildnach ein paar Minuten
Bildnach vielen Minuten

Aber es kommen ja alle Werte vor! Irgendwo ist y mal 1 oder 2 oder 3 oder 4 usw.
Nur eben nicht zufällig. Man sieht an diesem neuen Beispiel, dass, wenn y kleiner als 43 (oder 32 oder so etwas) ist, für x niemals ungerade Werte kleiner als 63 kommen. Das ist der Punkt. Für y kommen alle Werte durchaus vor. Also kann es nicht an einer Multiplikation liegen.

Allerdings hast Du natürlich recht. Wenn man mit kleinen Werten multipliziert, fällt das gar nicht auf. Das bedeutet aber nur, dass der Zufallsgenerator für diese geringe Auflösung (<64) gut ist. Aber bei höheren Auflösungen (z.B. 255) sieht man eben die sequenziellen Fehler der Zufallsfunktion.

Benutzeravatar
MatthiasS
User
Beiträge: 115
Registriert: 11.05.2004, 15:29
Wohnort: Wuppertal
Kontaktdaten:

Re: Zufallsfunktion nicht zufällig / random function not random

Beitrag von MatthiasS » 22.06.2008, 14:57

Wenn man zwischen den beiden RDN Funktionen noch einen RDN Funktionsaufruf einfügt, ist übrigens die Welt auch wieder in Ordnung. Dann ergibt sich egal mit welchen Faktoren immer ein zufällig gestreutes Bild!

Das deuetet auch auf eine sequenzielle Unzulänglichkeit der Funktion hin.

Matthias

Benutzeravatar
siggi
User
Beiträge: 2352
Registriert: 06.12.2005, 08:34
Wohnort: D, Hessen, tiefste Werreraa
Kontaktdaten:

Re: Zufallsfunktion nicht zufällig / random function not random

Beitrag von siggi » 22.06.2008, 22:02

Wenn man die beiden Zuweisungen von X und Y vertauscht (also erst Y, dann X errechnen), dann ergeben sich horizontale Linien. Das bestätigt Deine Vermutung, daß es an der RND Funktion und nicht an der Streckung liegt.
Also: Bug-Report schreiben und an Clive zur Behebung schicken (oder ist etwa die Gewährleistung schon abgelaufen? ) :D

BTW: Hat eigentlich schon mal jemand intensiver mit dem "besseren" ZX81 Rom (SG81?) gearbeitet? Da sind ja die Floating-Point-Routinen überarbeitet und laufen etwas flotter. Vielleicht verhält sich da auch RND anders????

Siggi

Antworten