RND-Zahlen von 0-10 in ASM

Es gibt 102 Antworten in diesem Thema, welches 18.026 mal aufgerufen wurde. Der letzte Beitrag (14. Dezember 2007 um 20:29) ist von Hanno Behrens.

  • Also ich bleib ja beim CRC16 Algo, da hat man auch ne Anständige Periode und vor allem: Man kann jederzeit per EOR andere Quellen mit einbeziehen, ohne irgendwas kaputtzumachen:

    LFSR gefällt mir nicht sonderlich. Da werden ja im Endeffekt nur "zufällige" Bits durchgeschoben. Beim CRC-Algo passiert ja genau das Inverse vom LFSR und man bekommt so in 50% noch ein EOR in den Ablauf und nicht nur blosses Bitdurchgeschiebe.

  • 16 Bit Zähler? Also die Schleife läuft in der Statistik 100*256 mal durch. Statistisch kommt also auf jedes der 256 Werte 100, was natürlich schön zu sehen ist, wenn man 100% annimmt. Sind es mehr oder weniger, ist es direkt in Prozenten abzulesen. Die Routine überprüft also 25600 Werte. Damit kann man zumindest schon mal anfangen zu arbeiten. Kommt bei unterschiedlichen Seeds immer das selbe heraus, ist das aussagekräftig. Wenn ich bei einem Erwartungswert von 100 Abweichungen von +-30% habe, kann man damit rechnen. Willst du mehr, mach das zehnfache an Durchläufen und zähle nicht ein Byte hoch, sondern ein Word mit zwei data-Tabellen. Aber es wird nichts am Ergebnis ändern. Mit +-30% sind wir bereits deutlich über der erlaubten Schwankung, denke ich. Werds nochmal genau durchrechnen.

    @Fröhn

    Dein CRC-Algorithmus an sich ist nicht schlecht. Nur brauchst du für das Ding zusätzliche Eingänge. Zudem hat er Laufzeitschwankungen, aber das ist nicht so wichtig, schätze ich. Aber als RND-Quelle verlässt du dich weiterhin auf die Register.

    Ich stimme dir zu, dass die Shiftregister eine unzureichende Zufallsquelle darstellen. Ich glaube nicht, dass die so viel besser sind als die Hardware. Ganz meine Rede. Man kann offensichtliche Unzulänglichkeiten von Zufallswerten mit einer CRC-Sum prima cachieren. Zum Beispiel, indem man einen MD5sum drüberlaufen läßt. Das funktioniert ganz gut. Deine Lösung ist schnell, aber ich fürchte nicht besonders hochwertig.

    Willst du das mal überprüfen, oder soll ich das machen? Ansonsten hau ich deinen CRC mal kurz in mein Tar mit rein und lass da meinen 256er-Test durchlaufen.

    Interessant ist es, ob man den CRC16 mit meinen beiden Shiftregistern kombinieren kann? Das sollte ein nettes Ergebnis geben, weil das Geschifte besser cachiert wird. Natürlich wird der Algorithmus dadurch nicht besser. Cachierung ist ja nur ein Patch für etwas, was zu schlecht funktioniert.

    2 Mal editiert, zuletzt von Hanno Behrens (7. Dezember 2007 um 16:00)

  • ehrm, ich glaub du hast da nen denkfehler. was deine funktion anzeigt ist quasi das lowbyte einer 16 bit zahl die bei 100 durchläufen gezählt wird. die aussagekraft ist eigentlich gering, das highbyte zu sehen wäre viel interessanter.

  • Nein. Was meine Funktion macht ist folgendes:

    Hole ein Byte aus einer RND-Funktion (kann man austauschen)
    Zähle das "Binbyte" eines Blocks hoch, das diesem Byte entspricht, also zähle, wieviele Bytes dieser Sorte vorhanden waren.

    rnd -> 0 -> inc block+0
    rnd ->22 -> inc block+22
    usw.

    Die rnd-Funktion wird 100*256 mal aufgerufen. Wenn die Funktion bei jedem Aufruf einfach "letzter Wert+1" zurück gibt, haben wir 256 mal eine 100 in unserem Ergebnis stehen.

    Die Zahlen sind also 100% gleichverteilt. Bei Zufallswerten haben wir jedoch Schwankungen drin. Wie hoch sie sein dürfen, sagt uns die Standard-Normalverteilung. Wird das gebrochen, ist unser Algorithmus "broken", also liefert nicht gleichverteilte Zahlen über unseren Wertebereich von 0..255

    Was ich festgestellt habe, ist, dass bestimmte Bytes grundsätzlich höher oder niedriger sind als vorhergehende. Das Verhältnis von Bytes im Abstand 4 ist mir sofort aufgefallen. Es gibt eine Spalte (oder zwei) bei Benutzung der RND-SID-Variante, wo immer ein größerer auf einen kleineren auf einen größeren Wert folgt. Das ist ein klares Muster und eindeutig unerwünscht.

    Weitere Muster-Tests sind Folgebytes: Also gibt es statistisch normale 0->0 Folgen? 1->1 Folgen usw. Dann 0->0->0 usw. Dann 0->1->2 usw. Das habe ich aber noch nicht gemacht. Unsere Randomfunktion ist ja schon im ersten Test gescheitert.

    Was das soll, ist klar: wenn wir beispielsweise ein Würfelspiel haben, sagen wir Mensch-Ärgere-Dich-Nicht und da werden immer 2 Würfel zusammen geworfen (Abhängigkeit!), dann müssen die Ergebnisse dieser Würfe statistisch korrekt sein. Oder wir haben ein seltsames Spiel als Ergebnis. Bestes Beispiel: Strippoker. Da ist der Randomalgorithmus ziemlich mies gewesen.

    2 Mal editiert, zuletzt von Hanno Behrens (7. Dezember 2007 um 15:56)

  • und da ist dein denkfehler. um aussagekräftige werte zu kriegen musst du viel mehr werte testen. bau das mal so um das die funktion jeweils 16bit hochzählt, und das so lange bis der erste dieser zähler überläuft. ich bin mir fast sicher das dann die werte relativ gleichverteilt sind. das man bei den paar werten die die routine zählt keine normalverteilung kriegt wundert mich nicht :)

  • Zitat

    Originally posted by Hanno Behrens
    Dein CRC-Algorithmus an sich ist nicht schlecht. Nur brauchst du für das Ding zusätzliche Eingänge. Zudem hat er Laufzeitschwankungen, aber das ist nicht so wichtig, schätze ich. Aber als RND-Quelle verlässt du dich weiterhin auf die Register.


    Wieso braucht man einen Eingang? Wenn man keinen Eingang benutzt, bekommt man eine Periode von 2^15-1 Werten, reicht doch auch für die meisten Anwendungen. Mit Eingang kann man allerdings wunderbar die Periode zerstören.

    Und die Laufzeitschwankungen lassen sich leicht beheben.

    Zitat

    Man kann offensichtliche Unzulänglichkeiten von Zufallswerten mit einer CRC-Sum prima cachieren. Zum Beispiel, indem man einen MD5sum drüberlaufen läßt.


    Oder am besten gleich den Mersenne Twister...

    Zitat


    Das funktioniert ganz gut. Deine Lösung ist schnell, aber ich fürchte nicht besonders hochwertig.


    Hochwertiger als LFSR allemal, selbst ohne Eingang.

  • Der Einwurf mit MD5 war von mir als Hinweis darauf gedacht, wie heutzutage mit schlechten Random-Quellen verfahren wird. Einfach ein MD5 drüber. Dass das auf dem C64 nicht sonderlich sinnvoll ist, ist klar. Vor allem weil der Mersenne-Twiser hochwertiger und im Verhältnis dazu besser ist, weil schneller.

    Nach obigen Vorschlag habe ich den Bin-Zähler nochmal auf 1000*256 Durchläufe erhöht. Natürlich kommt jetzt zum Tragen, dass die schlechten Werte unseres Generators mit der Zeit verwaschen werden. Die Abweichung nimmt natürlich ab, ist aber im Verhältnis immer noch viel zu groß.

    Ich hab jetzt außerdem das Basicprogramm noch mit ins Tar beigefügt.

    Meine Tests laufen darauf hinaus, dass sich die Fehler bei 1000 Durchläufen verwaschen. Die SID-Routine bringt etwa 7-8 Prozent Abweichung zwischen Maximum und Minimum, meine LFSR auch in der Größenordnung. Das ändert sich jedoch, wenn es 100 Durchläufe sind. Meine Vermutung ist fast, dass das Randomregister im SID zu langsam ist, also während eines Zustands mehrfach ausgelesen wird, während Algorithmen natürlich erst einen neuen Wert liefern, wenn dieser berechnet wurde.

    Kann das sein? Wie häufig ändert sich der Wert, wenn er von der Frequenz abhängt? C7 hat eine Frequenz von etwa 2093 Hz. Sollte der Zufallsgenerator von dieser Frequenz abhängen, dann haben wir alle 477 Taktzyklen einen neuen Wert.

  • Zitat

    Originally posted by Hanno Behrens
    Der Einwurf mit MD5 war von mir als Hinweis darauf gedacht, wie heutzutage mit schlechten Random-Quellen verfahren wird. Einfach ein MD5 drüber.


    Ein MD5 braucht man für eine 1:1 Abbildung nicht, da tut es auch eine Tabelle.

    Zitat


    Meine Vermutung ist fast, dass das Randomregister im SID zu langsam ist, also während eines Zustands mehrfach ausgelesen wird, während Algorithmen natürlich erst einen neuen Wert liefern, wenn dieser berechnet wurde.


    Eine passende Frequenz sollte man im SID schon einstellen.

  • @Fröhn

    Ich hab deine Routine crc16rand genannt und mal in meinen Test mit 100 Durchläufen gepackt. URRRGH!

    Sprich viel schlechter als alles andere. Nur so unter uns, no offence. Du kansnt das gern überprüfen. Sprich als Ergbnis habe ich, dass die Bytes abwechselnd immer groß/klein/groß/klein sind in der BIN-Statistik über 100 Durchläufe. Gerade Zahlen haben ein +50%, ungerade -50%. Das sagt wohl alles. Urgh.

    Ich denke, das sollte zum Nachdenken reichen, ob man seinen Routinen vertrauen kann oder nicht.

    Und ich bin mit meiner Frequenz vom SID bei C7. Das ist ziemlich am Ende der zugelassenen Werte. Nicht ausgemaxt, aber ziemlich. Mit ausgemaxtem $ffff gibt es tatsächlich bessere Werte bei 100 Durchgängen pro Wert +-12-15% und das ist okay.

    Ich häng dir deine Routine nochmal dran. Tag der uploads...

  • Zitat

    Original von Hanno Behrens

    Buuuaaahhhhh.... Ich bekomme das grosse Grausen! :schreck!:
    Da wird über tolle Algorithmen und Statistiken diskutiert, dabei sollte man doch ersteinmal die Grundzüge der Assemblerprogrammierung berücksichtigen.

    Die tolle Routine erzeugt nicht 100 * 256 Zufallszahlen, sondern nur 50 * 256. Im Gegenzug erhöht sie die Tabelle mit den Häufigkeiten nicht jedesmal um 1, sondern um 2.
    :lauh3: Hahaha...ja..so heben sich die Fehler zwar wieder ein bisschen auf.
    (Wenn man adc und sbc verwendet, sollte man schon darauf achten, was im Carry steht)

    Trotzdem grausiger Code.... (auch das mit dem Stack). Noch nie was von INC und DEC gehört? :nixwiss:

  • Zitat

    Original von Roland

    Buuuaaahhhhh.... Ich bekomme das grosse Grausen! :schreck!:
    Da wird über tolle Algorithmen und Statistiken diskutiert, dabei sollte man doch ersteinmal die Grundzüge der Assemblerprogrammierung berücksichtigen.

    Die tolle Routine erzeugt nicht 100 * 256 Zufallszahlen, sondern nur 50 * 256. Im Gegenzug erhöht sie die Tabelle mit den Häufigkeiten nicht jedesmal um 1, sondern um 2.
    :lauh3: Hahaha...ja..so heben sich die Fehler zwar wieder ein bisschen auf.
    (Wenn man adc und sbc verwendet, sollte man schon darauf achten, was im Carry steht)

    Trotzdem grausiger Code.... (auch das mit dem Stack). Noch nie was von INC und DEC gehört? :nixwiss:

    Tja, Roland. Bevor du lachst schau nochmal genau hin, was für Befehle ich verwende. Ich verwende add und sub und NICHT adc und sbc... add und sub sind geläufige Macros für clc;adc und sec;sbc Das mit dem Stack finde ich lustig. Lokale Variablen. Nur mit Accu. Also... Nochmal hinsetzen, lernen. :wink:

    Das mit dem DEC STACK+1,x, darüber könnte man reden. Bringt aber nicht viel. Und in dem Falle, wenns um das addieren oder subtrahieren von 16-Bitwerten geht, sehe ich überhaupt keinen Vorteil mehr. Nehneh, das passt schon so. Geh nochmal nachschlagen nach ADD und SUB...

    Das nenn ich nen Boomerang.

    3 Mal editiert, zuletzt von Hanno Behrens (7. Dezember 2007 um 18:12)

  • Gut! Da ich NIE Assembler (nur monitor) verwende, ist mir das nicht aufgefallen.
    Ich tipp immer so alles ein :)
    Punkt für dich...
    Ich bin wohl so von diesem grausigen Stack-Konstrukt und der Art und Weise wie die Tabellen hochgezählt werden geschockt. :roll2:
    Ich würde bei C64 doch nie den Stack für solche Zählerschleifen verwenden.

  • Ach, so grausig find ichs gar nicht. Ich finde es immer nervig irgendwo mitten im Programm oder am Ende Speicherzellen zu reservieren, die ohnehin nur lokal gebraucht werden. Und da das ganze nun wirklich nicht um Effizienz geht, siegt die Eleganz. Lokale Variablen sind cool. Mein Cryptobasic ist voll davon.

  • Naja....Zeropageadressen gibt es genug. Die schreien geradezu danach für Zählervariablen verwendet zu werden.
    und ein einfaches INC Tabelle,X hätte es auch getan....


    Ach, und was das Zufallszahlen vom Sid Rauschen abzugreifen betrifft, bin ich mir nicht sicher, ob es für eine gute gleichverteilung sinnvoll wäre, immer im gleich zeitinterval den wert abzugreifen. oder?

  • Zitat

    Ach, und was das Zufallszahlen vom Sid Rauschen abzugreifen betrifft, bin ich mir nicht sicher, ob es für eine gute gleichverteilung sinnvoll wäre, immer im gleich zeitinterval den wert abzugreifen. oder?

    das interval immer gleich lang ist dürfte relativ egal sein...wichtiger wäre das man die werte nicht zu "schnell" abfragt. warscheinlich wäre ideal wenn der oszillator gegenüber dem interval in dem abgefragt wird eine deutlich höhere frequenz hat, und zusätzlich das eine nicht durch das andere teilbar ist.

  • Yo...und DANN aber konstantes Zeitinterval....!?!

    allerdings wäre die Routine dann ja nur noch zum erzeugen von Zufallszahlen gut.... und wir wollen ja damit noch irgendwas machen :D

  • Zitat

    Originally posted by sauhund
    warscheinlich wäre ideal wenn der oszillator gegenüber dem interval in dem abgefragt wird eine deutlich höhere frequenz hat, und zusätzlich das eine nicht durch das andere teilbar ist.


    Einfach ne nette Primzahl aussuchen, damit liegt man meistens ganz gut.

  • Zitat

    Yo...und DANN aber konstantes Zeitinterval....!?! allerdings wäre die Routine dann ja nur noch zum erzeugen von Zufallszahlen gut.... und wir wollen ja damit noch irgendwas machen

    naja, wenn man ne schön hohe frequenz einstellt, und dann jeden frame ne zufallszahl holt, evtl noch am ende von allem was im raster-irq rennt, sollte das 3 mal passen :)

  • Ja, ich glaub auch, das passt. Wie gesagt, wenn man die Rauschfrequenz auf $ffff stellt gibt's keinerlei Probleme mit den Zufallszahlen. Die sehen sogar richtig gut aus. Aber die oben vorgeschlagene CRC16-Routine ist katastrophal. Ich werde auch nochmal die Routine checken vom Threaderöffner. Aber hab heute Abend keine Zeit mehr, muss los...

    Ich glaube nämlich, dass das Abgreifen der von ihm gewählten Register genauso wie beim crc16rand unschöne Ergebnisse zur Folge hat. Das beste und schnellste ist daher bislang eindeutig sidrand, so wie ich es sehe. Hat zwar wahrscheinlich nicht die Qualität von Fortuna/Yarrow/..., aber warum eigentlich nicht? Für einen schnellen Hack geeignet und bringt gegenüber einem LFSR keinerlei sichtbare Nachteile. Außer dem Wegfall einer SID-Stimme. Und natürlich, dass man nicht garantieren kann, dass alle Zahlen bei Durchlauf einer Periode auch wirklich kommen wie bei einem Software-LFSR.

    Trotzdem werde ich mich wohl mal dieses Wochenende an die Implementation eines AES machen. Damit hätte man dann eine prima Quelle für einen Fortuna und damit sollte man für den C64 allen Ansprüchen genügen. Nur schnell wird er nicht sein.

  • Zitat

    damit sollte man für den C64 allen Ansprüchen genügen. Nur schnell wird er nicht sein.

    das ist nur leider ein wiederspruch in sich =)