DEC Attack: Die kleine Problem-Ecke

Es gibt 88 Antworten in diesem Thema, welches 11.648 mal aufgerufen wurde. Der letzte Beitrag (5. Mai 2024 um 22:32) ist von goloMAK.

  • Ein verrückter Ansatz, der für das konkrete 1 Bit aber nicht lohnt, aber vielleicht was für mehr Bits taugt

    Code
    lda byte
    lsr
    eor byte
    and#$fe
    eor byte
    rol
    sta byte

    Bist Du Dir sicher, dass es funktioniert?
    Ich habe mal spaßeshalber %10110110 gewählt


    nach dem lda byte:
    a = %10110110
    nach dem lsr:

    a = %01011011, c = 0

    nach dem eor+and:
    a = %00000001

    jetzt kommt eor byte:
    a = %10110111

    jetzt kommt rol und ich denke, dass hier ein Fehler entsteht, weil vorher das ursprüngliche byte mit eor an die linke Seite hinzugefügt wurde und die Position nicht mehr stimmt:
    a = %01101110
    sta byte

    Ich kann mich natürlich auch Irren, ist ja schon mehrfach vorgekommen.

  • Noch eine Idee war, den BIT-Befehl zu benutzen, um einen Takt in einem Fall zu sparen:
    12 Bytes und 14 bzw. 15 Zyklen

    Code
    bit valueOne      ; 3

    Setzt aber voraus, dass es in der Zeropage fix einen Speicherstelle mit Wert 01 gibt.

    Wenn man sicherheitshalber etwa das ROM dafür hernimmt, etwa

    Code
    BIT $E01A

    dann braucht das 4 Takte.

  • Bist Du Dir sicher, dass es funktioniert?
    Ich habe mal spaßeshalber %10110110 gewählt

    Ich hatte eine kleine Basic-Schleife laufen lassen, weil mir das selber zu verwirrend war. Meine Konzentration ist aber ziemlich im Arsch, aber ich hab nochmal Deine Zahl getestet. Du hast das AND im Kopf invertiert.

    Code
    lda byte    10110110 
    lsr         01011011 +0 
    eor byte    11101101
    and#$fe     11101100
    eor byte    01011010
    rol         10110100
    sta byte
  • Noch eine Idee war, den BIT-Befehl zu benutzen, um einen Takt in einem Fall zu sparen:
    12 Bytes und 14 bzw. 15 Zyklen

    Code
    bit valueOne      ; 3

    Setzt aber voraus, dass es in der Zeropage fix einen Speicherstelle mit Wert 01 gibt.

    Wenn man sicherheitshalber etwa das ROM dafür hernimmt, etwa

    Code
    BIT $E01A

    dann braucht das 4 Takte.

    Korrekt, berni hat die ZP-Zusatzvariable in der Tabelle berücksichtigt.
    Bei den Zeiten für eine Variable außerhalb der Zeropage bin ich mir nicht so sicher.

    Bist Du Dir sicher, dass es funktioniert?
    Ich habe mal spaßeshalber %10110110 gewählt

    Ich hatte eine kleine Basic-Schleife laufen lassen, weil mir das selber zu verwirrend war. Meine Konzentration ist aber ziemlich im Arsch, aber ich hab nochmal Deine Zahl getestet. Du hast das AND im Kopf invertiert.

    Code
    lda byte    10110110 
    lsr         01011011 +0 
    eor byte    11101101
    and#$fe     11101100
    eor byte    01011010
    rol         10110100
    sta byte

    Hoogo
    stimmt, das war der (=mein) Fehler, also funktioniert doch alles wunderbar:
    12 Bytes und 18 Zyklen

  • Ich hab' mal eine Tabelle mit allen bisherigen Versuchen zusammengestellt: [...]

    Wow, starke Tabelle! :thumbup: Sehr interessant.

    BTW:

    sollte eigentlich test.a sein, aber dann akzeptiert es die Foren-Software nicht

    Hast du mal *.asm probiert? Das müsste eigentlich gehen.

    Bitte melde dich an, um diesen Link zu sehen. - Ratespiel • Bitte melde dich an, um diesen Link zu sehen. - BASIC-Erweiterung • Bitte melde dich an, um diesen Link zu sehen. - Sprite-Editor • Bitte melde dich an, um diesen Link zu sehen. - Zeichensatz-Editor Bitte melde dich an, um diesen Link zu sehen. - 2048 Blöcke

  • Noch zwei Version:
    13 Bytes und 17 Zyklen

    Code
    lda byte      ; 3 
    alr #3        ; 2    ALR entspricht AND und LSR
    adc #0        ; 2 
    and #1        ; 2
    asl           ; 2
    eor byte      ; 3
    sta byte      ; 3

    und mein neuer Favorit:
    9 Bytes und 12 Zyklen !!!

    Code
    lax byte      ; 3
    clc           ; 2
    adc #3        ; 2
    ora #11111101 ; 2
    sax byte      ; 3


    und falls man noch auf SBX ausweichen könnte, um das CLC zu sparen, wäre evtl. etwas in folgender Form möglich:

    Code
    lax byte
    sbx #$ff-3+1    ; o.s.ä. ???
    ???
    sax byte
  • Die Lösung von Mafiosino finde ich gut und smart. Sie lässt auch situative Optimierungen zu:

    Bei anfänglicher Nutzung des Akkus bleiben mit nur einem Byte mehr die Indexregister erhalten. Speed bleibt gleich.

    Code
    lda byte
    clc
    adc #$01
    and #$02
    eor byte
    sta byte
    
    B: 14 (11) / C: 18 (15)

    Mit Kenntnis des Carry-Status: Indexregister bleiben erhalten und Zyklen verringert.

    Code
    lda byte
    adc #$01    ; bzw. adc #$00 bei C=1
    and #$02
    eor byte
    sta byte
    
    B: 13 (10) / C: 16 (13)

    Beispiel aus dem wahren Leben:

    Bit Bitte melde dich an, um diesen Link zu sehen. in state erhält beim Erreichen des Zeilenendes also denselben Status wie Bit #0.

    Eine naheliegende Frage wäre, wie man es am besten mit Bit Bitte melde dich an, um diesen Link zu sehen./Bitte melde dich an, um diesen Link zu sehen. machen würde, von Bitte melde dich an, um diesen Link zu sehen. nach Bitte melde dich an, um diesen Link zu sehen. oder auch umgekehrt.

  • Da ist glaub ich was falsch drin.

    Eine naheliegende Frage wäre, wie man es am besten mit Bit Bitte melde dich an, um diesen Link zu sehen./Bitte melde dich an, um diesen Link zu sehen. machen würde, von Bitte melde dich an, um diesen Link zu sehen. nach Bitte melde dich an, um diesen Link zu sehen. oder auch umgekehrt.

    Code
    lda byte
    asl
    eor byte
    and#$7f
    eor byte
    ror
    sta byte

    Allgemeiner: Das EOR/AND/EOR kopiert beliebige Bits aus "byte" in den Akku, auch mehrere auf einmal. Das ASL und ROR verschleiern hier ein bisschen, wohin dieses Bit eigentlich kopiert wird.

  • Da ist glaub ich was falsch drin.

    Lustig jetzt sehe ich das auch. haha
    00 + 11 = 011

    01 + 11 = 100

    10 + 11 = 101

    11 + 11 = 110
    Bei der 1. und 3. Zeile wird in A das Bit-1 gesetzt, aber es hat im SAX dann keine Auswirkungen.
    ;) wäre auch zu schön gewesen.
    Danke für das Drüberschauen.

  • Mein heutiges Problem:

    Zufallszahlen einschränken

    Angenommen, ich habe eine zuverlässige Quelle von Zufallszahlen, die zwischen 0 und 255 liegen. Die Wahrscheinlichkeit ist dabei gleichverteilt, also alles tipp topp. Es soll jetzt also gar nicht um die Erzeugung von Zufallszahlen gehen.

    ABER: Ich möchte den Zahlenbereich jetzt auf 0-39 reduzieren, und zwar so, dass die Zahlen in diesem Bereich ebenfalls möglichst gleichverteilt sind.


    Der naive Ansatz:

    lda zufall

    and Bitte melde dich an, um diesen Link zu sehen.

    ... führt zu einer absolut schrecklichen Verteilung. :sad:

    Denkbar wäre der brutale Ansatz:

    lda zufall

    cmp Bitte melde dich an, um diesen Link zu sehen.

    bcc zahl_ist_0

    cmp Bitte melde dich an, um diesen Link zu sehen.

    bcc zahl_ist_1

    cmp Bitte melde dich an, um diesen Link zu sehen.

    ...

    evtl. mit einer entsprechenden Schleife.

    Mein "bestes" Verfahren sieht im Moment so aus:

    Wenn ich das mit allen Zahlen von 0 bis 255 durchgehe, komme ich zu folgendem Ergebnis:

    Im Zielbereich 0 - 39 kommen 32 Zahlen genau 8 x vor, die restlichen 8 Zahlen aber gar nicht!

    Gar nicht kommen vor: 4, 9, 14, 19, 20, 25, 30 und 35.

    (Auch interessant: Was haben diese Zahlen gemeinsam? :huh:)

    FRAGE: Wie würdet ihr das machen? Gibt es noch ein geschickteres Verfahren, mit logischen Verknüpfungen oder vielleicht auch ganz anders, was ich im Moment nur nicht sehe?

    Bitte melde dich an, um diesen Link zu sehen. - Ratespiel • Bitte melde dich an, um diesen Link zu sehen. - BASIC-Erweiterung • Bitte melde dich an, um diesen Link zu sehen. - Sprite-Editor • Bitte melde dich an, um diesen Link zu sehen. - Zeichensatz-Editor Bitte melde dich an, um diesen Link zu sehen. - 2048 Blöcke

  • Das and $Bitte melde dich an, um diesen Link zu sehen. ist ja ein and %00111001 wodurch Du ja schonmal BIT 1 und 2 ausmaskierst, d.h. da fehlen dann ja schon ein paar Zahlen. Dein lda RND gefolgt von lsr lsr lsr dividiert Deine verbleibende Zufallszahl ja durch 8, da ist es nicht erwunderlich, wenn ein paar Zahlen mehr nicht auftauchen.

    Was hast Du denn vor mit den Zufallszahlen? Generierst Du Dir vorab eine Tabelle mit Zufallszahlen oder benötigst Du mit jedem Durchlauf eine neue Zufallszahl?

    Was wäre denn mit

    lda RND

    and $#3F

    und wenn das Ergebnis > Bitte melde dich an, um diesen Link zu sehen. ist, dann eine neue Zufallszahl holen, and #$07 auf diese und das Ergebnis von der vorherigen Zufallszahl abziehen? Dann würdest Du je Zufallszahl max 2 Durchgänge haben.

    Wenn Du Dir nur eine Tabelle vorab generieren willst, also Geschwindigkeit keine Rolle spielt, dann würde ich lda RND and #$3F machen und falls das Ergebniss >39 einfach eine neue Zufallszahl solange holen, bis diese <= 39 ist.

  • Das and $Bitte melde dich an, um diesen Link zu sehen. ist ja ein and %00111001 wodurch Du ja schonmal BIT 1 und 2 ausmaskierst, d.h. da fehlen dann ja schon ein paar Zahlen.

    War dezimal gemeint, deshalb ohne Dollar: and Bitte melde dich an, um diesen Link zu sehen.. Taugt aber natürlich trotzdem nicht viel, das stimmt. :)

    Dein lda RND gefolgt von lsr lsr lsr dividiert Deine verbleibende Zufallszahl ja durch 8, da ist es nicht erwunderlich, wenn ein paar Zahlen mehr nicht auftauchen.

    Wieso? Wenn z.B. 0 rauskommt, dann ist eben die 0 damit vertreten. Da sehe ich nicht das Problem. Warum kann 15 herauskommen, aber nicht 14? Das muss ich mir nochmal anschauen...

    Generierst Du Dir vorab eine Tabelle mit Zufallszahlen oder benötigst Du mit jedem Durchlauf eine neue Zufallszahl?

    Letzteres. Zeit ist allerdings in meinem speziellen Fall trotzdem weniger das Problem. (Bin durch meinen Snake-Clon darauf gekommen, der dreht sowieso die meiste Zeit Däumchen.)

    Was wäre denn mit

    lda RND

    and $#3F

    und wenn das Ergebnis > Bitte melde dich an, um diesen Link zu sehen. ist, dann eine neue Zufallszahl holen, and #$07 auf diese und das Ergebnis von der vorherigen Zufallszahl abziehen? Dann würdest Du je Zufallszahl max 2 Durchgänge haben.

    Wenn Du Dir nur eine Tabelle vorab generieren willst, also Geschwindigkeit keine Rolle spielt, dann würde ich lda RND and #$3F machen und falls das Ergebniss >39 einfach eine neue Zufallszahl solange holen, bis diese <= 39 ist.

    Ah ja, das hört sich schon mal ganz gut an. :thumbup: In diese Richtung hatte ich tatsächlich gar nicht so gedacht.

    Bitte melde dich an, um diesen Link zu sehen. - Ratespiel • Bitte melde dich an, um diesen Link zu sehen. - BASIC-Erweiterung • Bitte melde dich an, um diesen Link zu sehen. - Sprite-Editor • Bitte melde dich an, um diesen Link zu sehen. - Zeichensatz-Editor Bitte melde dich an, um diesen Link zu sehen. - 2048 Blöcke

  • Hier mal mein erster Ansatz:

    Das entspricht einer Multiplikation mit 0.15625 (=1/32+1/8). Das Ergebnis ist nicht ganz gleichverteilt, das geht mit einer einzelnen Zufallszahl nicht. Du kannst aber den ersten Befehl durch ein lda zufall2 ersetzen (das sind dann die (binären) ersten 8 Nachkommastellen der Zufallszahl), dann müsste die Verteilung nochmal etwas näher an der Gleichverteilung sein.

  • goloMAK

    Zufallszahlen "von bis" habe ich in meiner Library, schon vor 30 Jahren erstellt.

    Aber da ist mir neulich aufgefallen, dass die 16bit-Zufallszahlen falsch berechnet waren. Muss ich noch korrigieren.

    8bit zwischen a und b funktioniert aber, und zwar so:

    1. Zufallszahl r zwischen 0 und 255 generieren

    2. Differenz von a und b multiplizieren mit r (byte * byte = word)

    3. Highbyte der Multiplikation addieren zu a, und fertig

    Da die Library sowieso die Multiplikation braucht, ist der zusätzliche Aufwand gering.

    Code suche ich später mal raus.

    <edit>

    Im mathematischen Klartext ist das:

    r * (b - a) / 256 + a

    z.B. 64 * (70 - 50) / 256 + 50 = 55

  • goloMAK

    Zufallszahlen "von bis" habe ich in meiner Library, schon vor 30 Jahren erstellt.

    Aber da ist mir neulich aufgefallen, dass die 16bit-Zufallszahlen falsch berechnet waren. Muss ich noch korrigieren.

    :)

    Das ist das Schöne an unserem Hobby... In welchem Bereich kann man sonst noch Fehler korrigieren, die man mal vor 30 Jahren gemacht hat?

    8bit zwischen a und b funktioniert aber, und zwar so:

    1. Zufallszahl r zwischen 0 und 255 generieren

    2. Differenz von a und b multiplizieren mit r (byte * byte = word)

    3. Highbyte der Multiplikation addieren zu a, und fertig

    Das hört sich ... interessant an! :thumbsup: Muss ich mir aber in einer ruhigen Minute genau angucken...

    Bitte melde dich an, um diesen Link zu sehen. - Ratespiel • Bitte melde dich an, um diesen Link zu sehen. - BASIC-Erweiterung • Bitte melde dich an, um diesen Link zu sehen. - Sprite-Editor • Bitte melde dich an, um diesen Link zu sehen. - Zeichensatz-Editor Bitte melde dich an, um diesen Link zu sehen. - 2048 Blöcke

  • Bitte melde dich an, um diesen Anhang zu sehen.

    Bitte melde dich an, um diesen Anhang zu sehen.

  • 1. Zufallszahl r zwischen 0 und 255 generieren

    2. Differenz von a und b multiplizieren mit r (byte * byte = word)

    3. Highbyte der Multiplikation addieren zu a, und fertig

    Ok, etwas salopp ausgedrückt heißt das doch Folgendes:

    Wenn man die Anzahl der gewünschten Zufallswerte mit 0-255 malnimmt, dann kann man die Zufallswerte einfach im Hi-Byte des Ergebnisses ablesen (ggf. vorher noch den Mindestwert hinzuaddieren). Was irgendwo logisch ist, wenn man bedenkt, dass 1 Hi-Byte = 256 Lo-Bytes ist. :facepalm:

    Wenn ich es richtig sehe, ist der höchste mögliche Zufallswert dabei tendenziell etwas unterrepräsentiert, aber für meine Zwecke ist das völlig irrelevant. Habe es auch mal getestet und kriege tatsächlich für alle Werte von 0-255 die erwarteten Häufigkeiten 6 oder 7.

    Danke für alle Hinweise! :thumbup:

    (EDIT) Falls Interesse besteht: Im Anhang ist noch die Testsuite, die ich benutzt habe.

    Dateien

    Bitte melde dich an, um diesen Link zu sehen. - Ratespiel • Bitte melde dich an, um diesen Link zu sehen. - BASIC-Erweiterung • Bitte melde dich an, um diesen Link zu sehen. - Sprite-Editor • Bitte melde dich an, um diesen Link zu sehen. - Zeichensatz-Editor Bitte melde dich an, um diesen Link zu sehen. - 2048 Blöcke