Qualität software-generierter Zufallszahlen in Icon

Heute ist Stammtischzeit:
Jeden Donnerstag 20:30 Uhr hier im Chat.
Wer Lust hat, kann sich gerne beteiligen. ;)
  • Hallo zusammen,

    dieser Thread geht auf diesen zurück.

    Code:

    Code-Deutung:

    ZeileDeutung
    1Einbinden der Graphics-Library (für alles, was auf Fenstern passiert)
    2-3zwei globale Variablen (geben die Dimension des auszuwertenden Bereiches ein. Die Auswertung erfolgt sowohl numerisch als auch graphisch)
    6Haupteintrittspunkt
    7Öffnet ein Fenster an der Position mit der Größe
    9-10Hm ... erzeuigt ein zweiduimensionales Array - ich hätte hierfür auch eine andere Library einbinden können. Aber letztlich stecken diese beiden Zeilen dahinter. In Zeile 9 wird ein Spaltenvektor aufgespannt. In Zeile 10 wird jedes Spaltenelement mit einem Zeilenvektor belegt. Ergebnis ist dann eine X*Y-Matrix. Die 0 in Zeile 10 ist der Initialisierungswert. Hätte ich auch weglassen können.
    12-16gibt den Inhalt der Matrix aus - Ergebnis ist eine 0-Matrix der Dimension X*Y
    18-21Initialisieren einige Zählvariablen
    23Starten einer Endlosschleife, die nur durch Erfüllen der Bedingung in Zeile 51 abgebrochen werden kann
    25-26? ist der Zufallszahlen -Operator. In diesen beiden Zeilen werden also zwei Zufallszahlen im Bereich 1 bis X und 1 bis Y ermittelt und den Variablen x und y zugewiesen
    28Zählt die Anzahl der Schleifendurchläufe
    30-34Prüft, ob die Kombination x,y erstmals vorliegt.
    Falls ja, wird das entsprechende Matrix-element gesetzt und der Zähler filled hochgezählt.
    35-39Falls der Punkt (x | y) innerhalb eines Kreises mit Mittelpunkt (X/2 | Y/2) und Radius X/2 = Y/2 liegt, dann wird die Vordergrundfabe auf grün gesetzt und ein Zähler hochgezählt.
    40-44Anderenfalls wird ein anderer Zähler hochgezählt und die Vordergrundfarbe auf schwarz gesetzt
    45Der Punkt an der Position (x | y) wird jetzt tatsächlich in der gesetzten Vordergrundfarbe gemalt.
    47Ausgabe einiger interessanter Informationen
    49Abbruchbedingung: Wenn alle Elemente der Matrix gesetzt sind = alle Punkte in der Graphik auf grün oder schwarz gesetzt sind
    51-54Ausgabe zusammenfassender Informationen.
    Wie ich in dem anderen Thread schon angedeutet habe, ist das Verhältnis von Zufallspunkte im Kreis zur Anzahl aller Punkte wie pi : 4. Die Zahl in der rechten Spalte von Zeile 49 ist somit pi/4.
    Da ich hier die Qualität der Zufallszahlen ermitteln will, verwende ich die Versuche, die innerhalb des Kreises gelandet sind (auch wenn mehrmals der gleiche Punkt getroffen wird) zur Anzahl der Schleifendurchläufe. Die Übereinstimmung mit pi/4 bzw. das Vierfache davon abzgl. pi ist dann ein Maß für die Gleichverteilung der hiermit ermittelten Zufallszahlen.
    Dieses Maß hängt aber vom Seed ab, der mit &random := gesetzt werden kann.
    Die Übereinstimmung mit pi = 3,1415... ist schon mal nicht schlecht.

    Programm-Ausgabe (die letzten 4 Zeilen):

    766452 168 150 62500 0.7850524234

    Amount of loops: 766452

    4 *(In circle / loops): 3.140209693

    difference to pi: 0.001382960093


    Graphische Ausgabe (250 x 250-Matrix)

    Man erkennt, dass alle Pixel gesetzt sind und dass die grünen Punkte innerhalb eines Kreises liegen.


    Beste Grüße

    Andreas

    Ich bin wirklich nicht darauf aus, Microsoft zu zerstören. Das wird nur ein völlig unbeabsichtigter Nebeneffekt sein.
    Linus Torvalds - "Vater" von Linux

    Linux is like a wigwam, no windows, no gates, but with an apache inside dancing samba, very hungry eating a yacc, a gnu and a bison.

    Einmal editiert, zuletzt von Andreas (3. Oktober 2020 um 17:43)

  • Qualität software-generierter Zufallszahlen in Icon? Schau mal ob du hier fündig wirst!

  • Eine wichtige Information fehlt: Was macht der ?-Operator. Also nicht, dass der Zufallszahlen erzeugt, sondern *wie* er das macht. Denn softwaregenerierte Zufallszahl ist ja nicht gleich softwaregenerierter Zufallszahl. Ich vermute mal Icon als Sprache legt das nicht wirklich fest, und man muss schauen was die konkrete Implementierung macht.

    Die Endlosschleife ist IMHO problematisch weil das tatsächlich eine Endlossschleife ist, falls der RNG tatsächlich so schlecht ist, das bestimmte Werte nie getroffen werden und damit nie alle Punkte getroffen werden. Das in dem verlinkten Thema auch erwähnte CBM BASIC V2 hat beispielsweise ein Zufallsfunktion die zwei Modi bietet und der Modus der eine Pseudozufallszahl aus dem Inhalt von bestimmten Hardwareregistern bildet, liefert nur 256 unterschiedliche Werte zwischen 0 (inklusive) und 1 (exklusive). Das ist natürlich eine ziemlich heftige Macke, die aber von Deinem Programm vielleicht gar nicht erkannt würde!

    “Dawn, n.: The time when men of reason go to bed.” — Ambrose Bierce, “The Devil's Dictionary”

  • Hallo _blackjack_,

    Eine wichtige Information fehlt: Was macht der ?-Operator. Also nicht, dass der Zufallszahlen erzeugt, sondern *wie* er das macht. Denn softwaregenerierte Zufallszahl ist ja nicht gleich softwaregenerierter Zufallszahl. Ich vermute mal Icon als Sprache legt das nicht wirklich fest, und man muss schauen was die konkrete Implementierung macht.

    für die Zufallszahlen ist die Datei ~/icon9_51/ipl/random.icn zuständig.

    Der Zufallszahlen-Operator ? in Icon führt folgenden Code aus:

    Code
    procedure rand_int(i)            #: model ?i
       static scale
    
       initial scale := 1.0 / (2 ^ 31 - 1)
    
       (i := (0 < integer(i))) | runerr(205, i)
    
       return integer(i * rand_num() * scale) + 1
    
    end

    rand_num() ist definiert durch:

    Da ich im Quellcode in #1 den Seed mit &random := nicht verwendet habe, startet das Programm jedes Mal implizit mit &random := 0 und setzt &random gemäß dieses Algorithmus neu. Dass das so ist, kann man erkennen, wenn man sich zusätzlich noch &random ausgeben lässt - nach jeder Zufallszahlenermittlung ist &random geändert.

    Interessant ist noch folgende Funktion, die &random mittels Hardware-Zufallszahlengenerator in /dev/urandom setzt.

    Wenn es diese Datei nicht gibt, wird stattdessen &random anhand Datum und Uhrzeit berechnet. Ich hätte nur noch eine Linux-Zeit mit aufgenommen (die Nanosekunden seit dem letzten Sekundenwechsel - da steckt beliebig viel Zufälligkeit drin).

    Dann gibt es noch eine Funktion, die ich vorstellen möchte:

    Wenn für a, c, m und x keine Werte übergeben werden, dann wird die Standardfolge der Zufallszahlen ermittelt (wie in meinem Code). Setzt man a, c, m und x auf andere Werte, dann wird einfach nur eine andere Zahlenfolge berechnet.

    Die anderen Funktionen in random.icn unterstützen den Programmierer, wenn man z.B. nicht Zufallszahlen von 1 bis N sondern von M bis N ermittelt haben möchte.

    Demnach ist das bei jeder Icon-Implementierung identisch.


    Die Endlosschleife ist IMHO problematisch weil das tatsächlich eine Endlossschleife ist, falls der RNG tatsächlich so schlecht ist, das bestimmte Werte nie getroffen werden und damit nie alle Punkte getroffen werden. Das in dem verlinkten Thema auch erwähnte CBM BASIC V2 hat beispielsweise ein Zufallsfunktion die zwei Modi bietet und der Modus der eine Pseudozufallszahl aus dem Inhalt von bestimmten Hardwareregistern bildet, liefert nur 256 unterschiedliche Werte zwischen 0 (inklusive) und 1 (exklusive). Das ist natürlich eine ziemlich heftige Macke, die aber von Deinem Programm vielleicht gar nicht erkannt würde!

    Nö, sehe ich nicht so. In meinem konkreten Beispiel will ich ermitteln, nach wie vielen Durchläufen bei einer N*N-Matrix zufällig jede Zeile und Spalte mindestens einmal angesprochen wurde. Bei hinreichend kleinem N muss das gegeben sein. Jede natürliche Zahl muss mal erzeugt werden - in Kombination mit einer zweiten Dimension dauert das dann nur länger.

    Wenn der Seed &random so schlecht gesetzt ist, dass vor Abbruchbedingung eine zyklische Folge erzeugt wird, aus der nichts mehr herausführt, dann kann man das eben nur dann erkennen, wenn man dem Programm die Möglichkeit, in eben diesen Zyklus zu fallen.

    Das sehe ich dann auch an der erzeugten Graphik mit dem Kreis. Wenn sich auf der Graphik nichts mehr tut, und in der Matric keine neue Kombination Zeile, Spalte erreicht wird, dann liefert das Programm nur noch Zufallszahlenpaare, die bereits ermittelt wurden.

    Da Icon keine Begrenzung der Darstellung ganzer Zahlen kennt, gibt es keine Quantelung in N*(1/256)-Schritten. In dem gezeigten Code-Auszügen wird z.B. mit 32Bit-Zahlen gearbeitet.

    Ist Deine Frage beantwortet?


    Beste Grüße

    Andreas

    Ich bin wirklich nicht darauf aus, Microsoft zu zerstören. Das wird nur ein völlig unbeabsichtigter Nebeneffekt sein.
    Linus Torvalds - "Vater" von Linux

    Linux is like a wigwam, no windows, no gates, but with an apache inside dancing samba, very hungry eating a yacc, a gnu and a bison.

  • Welche Frage? *Jetzt* habe ich eine: Was meinst Du mit dem „Nö, sehe ich nicht so“? Der RNG-Modus vom C64 der nur 256 Werte aus dem Wertebereich liefert, wird recht wahrscheinlich den kompletten 250×250 Bereich abdecken, denn die Werte sind gleichmässig über den Wertebereich verteilt. Falls die also noch vom Zufall her gleich Wahrscheinlich sind, wie genau würde man mit Deinem Programm erkennen, dass das eine ziemlich schlechter RNG ist? Der Kreis ist komplett und das Ergebnis wäre nahe an ? dran.

    “Dawn, n.: The time when men of reason go to bed.” — Ambrose Bierce, “The Devil's Dictionary”

  • also mir gefällt am Besten eine Idee mit RND und Verknüpfung von ADC Werten offener ADC Eingänge, leider hat der PI keinen ADC.

    lasst die PIs & ESPs am Leben !
    Energiesparen:
    Das Gehirn kann in Standby gehen. Abschalten spart aber noch mehr Energie, was immer mehr nutzen. Dieter Nuhr
    (ich kann leider nicht schneller fahren, vor mir fährt ein GTi)

  • Hallo _blackjack_,


    Welche Frage? *Jetzt* habe ich eine: Was meinst Du mit dem „Nö, sehe ich nicht so“? Der RNG-Modus vom C64 der nur 256 Werte aus dem Wertebereich liefert, wird recht wahrscheinlich den kompletten 250×250 Bereich abdecken, denn die Werte sind gleichmässig über den Wertebereich verteilt. Falls die also noch vom Zufall her gleich Wahrscheinlich sind, wie genau würde man mit Deinem Programm erkennen, dass das eine ziemlich schlechter RNG ist? Der Kreis ist komplett und das Ergebnis wäre nahe an ? dran.

    Na, Du fragtest, was der ?-Operator macht - und wolltest wissen, wie er das macht...

    Das Programm habe ich ja auch mit einer Matrix von 500 x 500 laufen lassen. Da gibt es ganz sicherlich keine 256er-Teilung ;). Der gezeigte Algorithmus für rng() lässt das ja auch nicht zu. Dann müsste da was stehen mit bla % (2^8) oder Vergleichbares. Aus dem Code folgt vielmehr, dass in Icon Zufallszahlen auf 32 Bit aufgelöst werden. Kann man natürlich anpassen auf beliebig größere Zahlen (Stich: LIA Large Integer Arithmetic) anpassen.

    Mit dem Nö, meinte ich, dass die Endlosschleife keine so schlechte Idee ist. Es gibt keine Abbruchbedingung außer der einen gemachten. Wenn der Algorithmus aufgrund schwacher Zufallszahlenermittlung mehr oder zu viele Versuche braucht, um den zweidimensionalen Bereich abzudecken, dann ist das eben so.

    Das Programm habe ich mal mit X = 500 und Y = 500 laufen lassen. 500 * 500 = 250000.

    3278091 50 143 250000 0.7855785578

    Amount of loops: 3278091

    4 *(In circle / loops): 3.142314231

    difference to pi: 0.0007215774672


    Nach rund 3.280.000 Durchläufen war die Abbruchbedingung erfüllt. Für die letzte Zelle brauchte das Programm aber immerhin rund 25 Millionen Versuche.

    Eine Entscheidung "Abbruch wegen zu vieler Versuche für eine weitere zu setzende Zelle" wäre unberechtigt gewesen.

    Einen ziemlich schlechten RNG würde man daran erkennen, dass z.B. in der Graphik Bereiche gar nicht erreicht werden.

    Basierend auf solchen Zufallszahlen habe ich mal ein Galton-Brett programmiert (mit graphischer Animation der Kugeln, der Flugbahn und Sammlung in finalen Containern). Da geht es nur darum, N mal hintereinander "rechts" oder "links" zufällig zu setzen. Bei einer großen Anzahl an Durchläufen erfüllen die N+1 aufsummierten Zahlen die Voraussetzungen einer Normalverteilung. Für die Übereinstimmung mit der Normalverteilung gibt es Algorithmen.

    Bei meinem hier gebrachten Programm müsste die Anzahl der Durchläufe erheblich gesteigert werden. Die Anzahl der Treffer müsste ebenso wie beim Galton-Brett aufsummiert werden. Dann müssen stochastische Betrachtungen angestellt werden, um zu zeigen, ob mit akzeptablem Vertrauensbereich ein Zahlenpaar signifikant häufiger bzw. seltener ermittelt wurde. Ist die Signifikanz nicht gegeben, muss man den RNG als brauchbar einstufen.


    Beste Grüße

    Andreas

    Ich bin wirklich nicht darauf aus, Microsoft zu zerstören. Das wird nur ein völlig unbeabsichtigter Nebeneffekt sein.
    Linus Torvalds - "Vater" von Linux

    Linux is like a wigwam, no windows, no gates, but with an apache inside dancing samba, very hungry eating a yacc, a gnu and a bison.

  • Mit dem erhöhen von X und Y verschiebt man das Problem aber nur und Endlosschleife ist immer noch keine gute Idee. Was man da eigentlich möchte ist die Periode von dem RNG zu bestimmen, also nach wie vielen Zahlen sich das dann wiederholt. Und dabei kann man auch gleich schauen ob auch der gesamte Wertebereich abgedeckt wird. Und das möchte man dann auch für alle möglichen Seed-Werte machen.

    “Dawn, n.: The time when men of reason go to bed.” — Ambrose Bierce, “The Devil's Dictionary”

Jetzt mitmachen!

Du hast noch kein Benutzerkonto auf unserer Seite? Registriere dich kostenlos und nimm an unserer Community teil!