Hello, Guest the thread was called6.6k times and contains 95 replays

last post from JeeK at the

Zufallszahlen

  • Ich denke, die für den BASIC Programierer wichtige Frage ist nicht

    wie zufällig meine Zufallszahl ist, sondern wie schnell wird sie ermittelt und

    im Basic Programm verarbeitet.

    Ein RND(-Ti) und ein folgendes RND(.) ist für MICH z.B. völlig ausreichend zufällig. ^^

    Man kann ja auch mit Hilfe des Rauschens vom SID Zufallszahlen ermitteln,

    das erhöht aber wieder den Programmieraufwand im Basic und drosselt wahrscheinlich die Geschwindigkeit! (selbst noch nicht getestet!!!).

  • In #77 Beispiel 1 müsste es in Zeile 40 heißen RND(1)*(I+1), weil sonst beim ersten Ziehen die 49 nicht mit einbezogen wird.

    Das ist auch in Beispiel 4 der Fall. Das könnte dann so aussehen:

  • Man kann ja auch mit Hilfe des Rauschens vom SID Zufallszahlen ermitteln

    Ja, aber dem muss man trotz höchster Rauschfrequenz auch ein bisschen Zeit geben, seine Werte zu ändern. Wenn man ohne Pause wie wild ausliest, erhält man viele gleiche Zahlen. Wie groß die Pause mindestens sein muss, kann man sich anhand der Frequenz ausrechnen. Unten ein Beispiel, wie man es nicht machen sollte. Unmittelbar nach dem Einschalten des Generators erhält man noch besonders viele gleiche Zahlen, die oben anfangen und dann langsam absteigen: 252 252 252 252 252 248 248 248 248 248 248 248 248 248 240 240 240 240 240 224 224 .... Nach einer kleinen Wartezeit pendelt sich das auf Sequenzen von etwa 2 bis 3 gleichen Zahlen ein: 214 131 131 197 197 47 47 47 143 143 19 19 30 30 78 78 78 60 60 .... Wenn man dem Oszillator also mindestens dreimal so lang Zeit lässt wie in meinem Beispiel, dann geht es, sofern der Rauschgenerator schon vorher eingeschaltet war. Wie lange man ihm mindestens Zeit lassen muss zum "Einschwingen", weiß ich noch nicht. So was weiß bestimmt der andi6510.

  • Der SID-Rauschgenerator ist freilich für Assembler-Programmierer deutlich interessanter. Deutlich schneller und unkompliziert, vergleicht man eine Float-Funktion ...
    Aus BASIC-Ebene würde ich ohnehin möglichst wenig Hardware-Abhängigkeiten, sofern sie nicht ohnehin schon gegeben ist, einbauen.

    Ein RND(-TI) bringt nur etwas in der Kombination mit einem RND() das ein positives (Nicht-Null) Argument hat.

    Das Problem von RND(0) (bzw. RND(.)) beim C64 ist generell, dass die RTC (CIA1) standardmäßig nicht gestartet ist und die 32-Bit-Mantisse nur von 16 Bits des CIA1-Timer-A befüllt wird. Das schränkt das Spektrum der erzeugten Zahlen deutlich ein. Außerdem leidet der Zufallsaspekt ziemlich (hinterlässt systematische Muster), wenn die Abfragen im gleichen Intervall stattfinden (sie im RND-Artikel des C64-Wikis zu sehen und erklärt wird). Wenn einem das reicht und die Geschwindigkeit wirklich so wichtig ist, kann man natürlich damit leben.

    Ein RND(-TI) bringt dann aber nichts.

    Mit dem Aktivieren der RTC von CIA1 kann man ja die Zufallsbandbreite noch steigern (siehe auch Beispiel im Artikel).


    Hinsichtlich Geschwindigkeit ist natürlich RND(0) 5x so flott wie ein RND(1). Hier das Argument mit dem "."-Trick oder über eine Variable zu optimieren spielt dann bei diesem Unterschied faktisch kaum eine Rolle mehr. ;)

  • so, letzte Version, mit ohne dem doofen TI$ und nur einem Array ..

  • Ich dachte auch an das Auslesen von irgendwelchen Analogwerten innerhalb des Rechners um dann per Zufallsdivisoren eine riesige Auswahl an Zufallszahlen zu haben.

    Wenn bestimmte Ausführungen zu lange dauern, kann man das ja an den Anfang eines Programms setzen und die Zufallszahlen zwischenspeichern und bei Bedarf später einfach abfragen.


    Dann gibt es keine Verzögerungen, und der Kram könnte sogar schneller als die üblichen Routinen während des Programmablaufs bereitgestellt werden.


    ...nur so ´ne Idee...

  • Ich dachte auch an das Auslesen von irgendwelchen Analogwerten innerhalb des Rechners

    Soweit ich weiß gibt es an "auslesbaren Analogwerten" nur die POTX/POTY Eingänge des SID für die Paddles. Die sind dafür wohl kaum zu gebrauchen ;)


    Die Grundidee ist aber an sich naheliegend. Gerne hergenommen wird $d012 (aktuelle Rasterzeile) oder auch $dc04 (lowbyte timer A von CIA #1). Außerdem bietet der SID die Möglichkeit, den Wert von Oszillator 3 auszulesen ... wenn man den stumm schaltet und Rauschen aktiviert, erhält man hier pseudozufällige Werte (das Rauschen wird vom SID per LFSR erzeugt). Alles nicht analog, aber erfüllt wohl den Zweck, an den du dachtest. Wobei ich mit solchen Eingaben immer eher einen PRNG seeden würde, als sie wiederholt für Zufall zu nutzen (zu dem Zweck taugt dann wohl auch ausschließlich die Variante mit dem SID OSC3).

  • Ich dachte auch an das Auslesen von irgendwelchen Analogwerten innerhalb des Rechners

    Soweit ich weiß gibt es an "auslesbaren Analogwerten" nur die POTX/POTY Eingänge des SID für die Paddles. Die sind dafür wohl kaum zu gebrauchen ;)


    Die Grundidee ist aber an sich naheliegend. Gerne hergenommen wird $d012 (aktuelle Rasterzeile) oder auch $dc04 (lowbyte timer A von CIA #1). Außerdem bietet der SID die Möglichkeit, den Wert von Oszillator 3 auszulesen ... wenn man den stumm schaltet und Rauschen aktiviert, erhält man hier pseudozufällige Werte (das Rauschen wird vom SID per LFSR erzeugt). Alles nicht analog, aber erfüllt wohl den Zweck, an den du dachtest. Wobei ich mit solchen Eingaben immer eher einen PRNG seeden würde, als sie wiederholt für Zufall zu nutzen (zu dem Zweck taugt dann wohl auch ausschließlich die Variante mit dem SID OSC3).

  • so, letzte Version, mit ohne dem doofen TI$ und nur einem Array ..

    Gefällt mir gut, ist fast die In-Place-Variante, die ich gepostet habe, aber kompakter. Wenn man mit Index 0 beginnt, schaut es doch etwas eleganter aus, auch wenn man die +1 Korrektur mal irgendwo machen muss. Der Unterschied ist, dass hier allerdings wieder eine zusätzlich Extraschleife in einem 2. Durchlauf für das Insertion-Sort verwendet wird. Dabei gibt es ja schon diese Schleife (FORI=.TO5 in 40) bereits und könnte diese auch gleich verwenden.

    Wenn man diese beiden Schleifen verschmilzt (man muss dann nur den Sonderfall I=0 berücksichtigen, weil ja FOR-NEXT immer mind. 1 mal durchlaufen wird), kommt man dann auf

    Code
    1. 10 DIM I,J,T,Z(48)
    2. 20 A=TI
    3. 30 FOR I=.TO48:Z(I)=I:NEXT
    4. 40 FOR I=.TO5:J=RND(I)*(49-I)+I:T=Z(J):Z(J)=Z(I):J=I-1:IFI=0GOTO60
    5. 50 FOR J=I-1TO.STEP-1:IF T<Z(J) THEN Z(J+1)=Z(J):NEXT
    6. 60 Z(J+1)=T+1:NEXT I
    7. 70 B=TI
    8. 79 REM AUSGABE 6 AUS 49
    9. 80 FOR I=.TO5:PRINTZ(I);:NEXT
    10. 90 PRINTTAB(25)INT(50*(B-A)/3)"MS":GOTO20

    Es ist damit noch ein bisschen schneller, sondern auch etwas kürzer. ;)

  • Uiiii, "Dim I,J,T" kannte ich noch nicht!

    Wieder was gelernt! :thumbup:

    Das wird so schnell wie möglich getestet!

    Ja, das verwendet man, um die Reihenfolge der Variablen festzulegen, damit die häufig gebrauchten Variablen schnell bei der (linearen) Suche in der Variablentabelle gefunden werden. Das ist eleganter und kompakter als mit Pseudozuweisungen zu arbeiten. ;)

  • Wenn man diese beiden Schleifen verschmilzt

    Gute Arbeit! Da spielt InsertSort seine Vorteile aus, weil es ja jedes Element einzeln weg sortiert und völlig egal ist, ob der Satz noch nicht komplett ist.

    Das ist bestimmt noch nicht das Ende der Fahnenstange. Hab mal den Zeitcode erweitert, damit nach 100 Durchläufen der Durchschnitt angezeigt wird. Aktueller Stand: 614ms.


    btw Punkt statt Null schreibe ich nur aus Gewohnheit, also auch da, wo es eh nix bringt.


    Die Zählung der Ziffern und Sequenzen wie in #80, die für die ausschließliche Nutzung von RND(0) ja nicht so toll ausgefallen war, werde ich mal für RND(0) mit beiden CIAs wiederholen.


    Und das Thema "Zyklische Pseudozufallszahlen durch Schieberegister" will ich bei Gelegenheit noch mal aufgreifen. Das trifft dann auch wieder besser den Eingangs-Beitrag dieses Threads, auch wenn ich im kompletten Berechnungszyklus statt 100 immer nur Mengen von Zweierpotenzen erzeugen kann. Aber für die Spiele-Programmierung ist das eine hervorragende Sache, weil man die Werte jederzeit einzeln erzeugen kann, das auch noch ultraschnell, sich innerhalb der Menge bzw. des Zyklus' nie eine Zahl wiederholt, der Code dafür winzig klein ist und man durch Änderung des letzten Ergebnisses direkt beliebige Sequenzen aus der Menge abrufen kann.

  • Wenn man die Zahlen wieder auf Position 1 bis 49 legt, kann das GOTO entfallen.


    Wir haben dann in Z.50 beim ersten Mal für J mit I-1 die Stelle 0, wo sich immer die 0 befindet. Da T nicht kleiner als 0 sein kann, wird die Schleife beim ersten Mal sofort beendet und in Z.60 dann T der Stelle 1 zugewiesen. Damit Index 0 beim Einsortieren der nächsten Zahlen nicht weiter berücksichtigt wird, muss der Endwert der Sortierschleife 1 sein.


    Frage: Wie kann es sein, dass bei mir (trotz gleicher Konfiguration, z.B. Random-Delay:Off, etc.) VICE 3.1 dafür ganze 42ms länger braucht als VICE 2.4?


    Beim wiederholten Start von 3.1 habe ich bis zur letzten Zahl immer dasselbe Ergebnis und immer dieselbe Messzeit (591ms).

    Beim wiederholten Start von 2.4 habe ich ebenfalls bis zur letzten Zahl immer dasselbe Ergebnis und immer dieselbe Messzeit (549ms). Aber eben andere als bei 3.1.


    Dass die gezogenen Zahlen unterschiedlich sind, könnte ich ja noch aufgrund von kleinen Timing-Unterschieden der Versionen beim "Einschalten" verstehen.

    Aber durch andere Zahlen entstehen im Durchschnitt von 1000 Ziehungen nur Unterschiede von bis zu 3ms und nicht 42ms. Man kann ja außerdem nach einem Durchlauf von 1000 Ziehungen auch RUN eingeben und erhält ebenfalls andere Zahlen, und dann bestätigt sich, dass VICE 2.4 immer etwa 42ms weniger braucht. WHY? :gruebel

  • Beim wiederholten Start von 3.1 habe ich bis zur letzten Zahl immer dasselbe Ergebnis und immer dieselbe Messzeit (591ms).

    Beim wiederholten Start von 2.4 habe ich ebenfalls bis zur letzten Zahl immer dasselbe Ergebnis und immer dieselbe Messzeit (549ms). Aber eben andere als bei 3.1.

    Meine 3.1er-Version WinVICE-3.1-x86-r33738 liefert bei mir gemittelt 548 ms.

    Gibt es da im Laufe der 3.1er-Serie diesbezüglich einen Bug? Die 2.4er-Zeit würde dann ja passen.


    Ich hatte z.B. schon mal bei der 2.4er-Release (stable) und einer späteren 2.4.20 (unstable) eine Anomalie bei der RTC, wo in der alten (stable) Version die RTC um 2 % zu langsam lief.
    Gut, hier haben wir 8 % Abweichung. Das ist dann sicher wieder etwas anderes ...

  • Danke. Ich weiß schon, was es war .. so was doofes aber auch :wand .. Es lag am Action Replay, das ich aus Gewohnheit schon irgendwie nicht mehr registriere, aber das nicht nur die Startsequenz massiv beeinflusst, sondern auch die Periode für das Service-Intervall verringert und damit in der BASIC-Umgebung mehr Zeit abzwackt. Das werde ich bald mal direkt im Modul ändern. Und wenn man es ganz genau wissen will, sollte man das ja ohnehin komplett deaktivieren bzw. herausnehmen.


    Eines hab ich noch ausprobiert .. Das Belegen des Arrays mit den 49 Zahlen benötigte schon immer die Hälfte der Gesamtzeit, also dachte ich, lass ich das einfach mal sein. Nur die ersten 6 werden gebraucht. Alle mit 0 belegten Elemente entsprechen ihrem Index. Für ein einmaliges Generieren einer Lottoreihe erfordert es keine weiteren Maßnahmen. Erst bei der nächsten kompletten Ziehung müsste das Array wieder bereinigt werden. Leider gibt es hier kein REDIM. So bleibt dann nur das langsame Löschen in einer Schleife, der RUN-Befehl oder, wie in dem Beispiel, das Neu-Dimensionieren durch zwei POKEs zu ermöglichen. Allerdings werden dabei alle etwaigen Arrays gelöscht. Außerdem hab ich mal bei der Gelegenheit getestet, was das Verwenden von Variablen für alle sonstigen Zahlen bringt; beläuft sich auf 20ms.


    jeek(03s).prg

  • Genau genommen kann man sich das Initialisieren ab dem 2. Durchlauf überhaupt weglassen, ausgehend von der Variante aus Posting #94.

    Das letzte Ergebnis ist ja schließlich nur wieder eine Permutation, aus der zufällig 6 entnommen werden. Es wird nicht zufälliger, wenn das Array vorher "geordnet" ist. Vielmehr sollte es völlig egal sein, aus welcher Permutation die 6 Zahlen entnommen werden. Es darf jedenfalls in dem Array immer nur jede Zahl genau ein mal vorkommen.

    Damit kommt man auf gemittelt 324 ms.

    Folgende Zeilen wurden geändert:

    Code
    1. 15 a=ti
    2. 20 fori=1to49:z(i)=i:next:goto40
    3. 30 a=ti
    4. ...
    5. 90 m%(n)=int(50*(b-a)/3):printtab(25)m%(n)"ms":n=n+1:ifn<=999goto30
    6. ...