Dividieren - here we go again!

Es gibt 15 Antworten in diesem Thema, welches 2.500 mal aufgerufen wurde. Der letzte Beitrag (29. Juli 2022 um 21:19) ist von Mike.

  • Dividieren in Assembler, immer wieder ein schönes Thema!

    Vor allem, wenn eine Kommazahl herauskommt.

    Konkret soll in meinem Beispiel 23/7 gerechnet werden. Laut Taschenrechner ~= 3,285714.

    Als binäre Näherung habe ich ermittelt: 0000 0011 0100 1001 0010 0100

    Das heißt 2^1+2^0+2^(-2)+...+2^(-14) ~= 3.285706

    Das Ziel ist also, dass genau diese drei Bytes (Hex $03 $49 $24) hintereinander im Speicher liegen.

    Mein Code unten erfüllt diesen Zweck zwar, aber er ist doch recht redundant. Irgendwie finde ich nicht den richtigen Übergang, nachdem das ganzzahlige Ergebnis vorliegt. Ich habe immer das Gefühl, es müsste sich alles mit einer einheitlichen Schleife erledigen lassen.

    Was habe ich übersehen? Verbesserungsvorschläge willkommen!

    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

  • Nur generell mal einige Optimierungen, die mir so ins Auge springen ...

    Code
                lda #$01
                sta res
    loop        asl dvd
                rol
                cmp dvs
                bcc skip
                sbc dvs
    skip        rol res
                bcc loop

    Wieso wird das Ergebnis auf 3 Bytes aufgeteilt? Bei 8 Durchläufen, kann es nur max 8 Bit umfassen. Wenn man mehr "Dezimalstellen" im Ergebnis haben möchte, muss man den "Rest" weiter zerteilen und das die Schleife etwa auf 16 oder 24 Bit ausweiten. Dann ergäbe das einen Sinn.

    Nach 8 Durchläufen ist der Dividend natürlich komplett rausgeschoben und man müsste diesen dann nicht mehr ständig mitrotieren ... in so einem Fall könnte man sich da auch was überlegen, etwa eine 2. Schleife für Bit 9 bis 15 (oder 23).

    Aber zu den Optimierungen an sich:

    * X als Bitzähler kann man sich sparen, wenn man im Result-Byte res einfach Bit 0 zu Beginn setzt und dann dieses Bit dann nach dem 8 ROL beim Carry angelangt ist, dann ist das Carry-Flag gestetzt und wir haben 8 Durchläufte.

    * tmp kann man sich auch sparen, wenn man gleich den Akku dafür verwendet.

  • Wieso wird das Ergebnis auf 3 Bytes aufgeteilt? Bei 8 Durchläufen, kann es nur max 8 Bit umfassen.

    8 Bit für die Ganzzahl, dann noch einmal 16 Bit für die Nachkommastellen (im 2. Loop).

    Aber da war natürlich noch Luft drin, die Nachkomma-Bytes hatten im 1. Loop nichts verloren. Meine momentan kürzeste Fassung sieht so aus:

    Wenn man mehr "Dezimalstellen" im Ergebnis haben möchte, muss man den "Rest" weiter zerteilen und das die Schleife etwa auf 16 oder 24 Bit ausweiten. Dann ergäbe das einen Sinn.

    Beide Schleifen zusammen ergeben ja 24 Bit. Mein zentrales Anliegen war es, die beiden Schleifen zu einer zusammenzufassen, die gleich alle 24 Bits abfrühstückt. Ich bin aber unsicher, ob das überhaupt naheliegend/sinnvoll wäre.

    Aber zu den Optimierungen an sich:

    * X als Bitzähler kann man sich sparen, wenn man im Result-Byte res einfach Bit 0 zu Beginn setzt und dann dieses Bit dann nach dem 8 ROL beim Carry angelangt ist, dann ist das Carry-Flag gestetzt und wir haben 8 Durchläufte.

    * tmp kann man sich auch sparen, wenn man gleich den Akku dafür verwendet.

    Cool, das hört sich beides interessant an. :thumbup: Muss ich demnächst ausprobieren/einbauen.

    (Anbei noch die obige Fassung als PRG.)

    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

    Einmal editiert, zuletzt von goloMAK (24. Juli 2022 um 22:17)

  • Dividieren in Assembler, immer wieder ein schönes Thema! Vor allem, wenn eine Kommazahl herauskommt.

    Das ist jetzt nicht wirklich wild. Eine gängige 'Maßnahme' ist dann die Fixpunkt-Darstellung: die Zahlen werden mit einer 2er-Potenz multipliziert, alles links vom Radix-Punkt ist der ganzzahlige Anteil, alle Bits darunter der gebrochene Anteil.

    Das kann auch bei der Division mit Dividend und Divisor machen und muß dann nur ausknobeln, wo im Ergebnis der Radix-Punkt herauskommt. Umgekehrt, wenn das Format des Ergebnisses schon feststeht, muß man ermitteln, wie das Format des Dividenden und Divisors auszusehen hat.

    Da Du im Ergebnis ein Byte vor dem Radix-Punkt und zwei Bytes nach dem Radix-Punkt haben willst und hier im Beispiel der Divisor ganzzahlig ist, läßt sich das Ergebnis mit einer 24-Bit-durch-8-Bit-Integer-Division ausrechnen. Der Dividend ist dann 23x65536 - also, in 8:16-Darstellung. Bei Fixpunkt gibt die Zahl vor dem Doppelpunkt die Bits des ganzzahligen Anteils an (hier acht) und die Zahl nach dem Doppelpunkt die Bits des gebrochenen Anteils (hier 16).

    Ich nehme einfach mal meine Bitte melde dich an, um diesen Link zu sehen. her und erweitere die auf 24 Bit im Dividenden:

    Anstelle von #$07 bei dem CMP- und SBC-Befehl ist auch ein anderer Divisor möglich.

    Wenn Du jetzt in zp und zp+1 eine 0 schreibst, und in zp+2 die 23, dann sollte nach der Ausführung an gleicher Stelle das von dir erwartete Ergebnis $03 $49 $24 - allerdings in umgekehrter Reihenfolge, also little-endian! - herauskommen.

    P.S. JeeK hat bei der Originalfassung der Routine mal kräftig mitgeholfen. :D

    P.P.S. wolltest Du pi annähern? Dann wäre allerdings 22/7 der Bruch, den Du ausrechnen wolltest. ;)

  • Danke, Mike! Da habe ich was zum Tüfteln.

    Eine Frage:

    Der Dividend ist dann 22x65536 - also, in 8:16-Darstellung.

    Der Dividend ist in meinem Beispiel ja 23. Warum entspricht das jetzt 22x65536 und nicht 23x0? (Ich weiß auch nicht wirklich, wofür das "x" steht?)

    Und:

    P.P.S. wolltest Du pi annähern? Dann wäre allerdings 22/7 der Bruch, den Du ausrechnen wolltest. ;)

    Oh, nein, diese zufällige Nähe ist mir gar nicht aufgefallen. Ich wollte allerdings einen Divisor haben, bei dem ein schön krummes Ergebnis mit langer Periodenlänge herauskommt, und so kam ich auf 7. Der Dividend sollte nicht zu groß sein, damit es nicht so viele Durchläufe gibt und ich die Bitverschiebungen leichter nachvollziehen kann.

    Und so habe ich dann - beinahe - Pi neu entdeckt. :)

    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

  • Warum entspricht das jetzt 22x65536 und nicht 23x0? (Ich weiß auch nicht wirklich, wofür das "x" steht?)

    23x65536, ich hab' das im Original-Beitrag gerade noch korrigieren können. Das "x" steht hier für Multiplikation.

    Das ist jetzt weniger wild als es aussieht, denn die Multiplikation mit einer 2er-Potenz in Binärschreibweise ist ja nur einfaches Bitschieben. Damit ist dann die 23 in 8:16-Fixpunktdarstellung und in Little Endian eben $00 $00 $17 - so wie Du das oben im Bild siehst, eingespeichert in $FB, $FC und $FD.

    Und so habe ich dann - beinahe - Pi neu entdeckt. :)

    22/7 ist eine gängige Näherung für pi - die war schon Archimedes bekannt. Die Chinesen haben mit 355/113 eine noch bessere Näherung gefunden, da sind dann schon 6 Nachkommastellen korrekt!

  • 23x65536, ich hab' das im Original-Beitrag gerade noch korrigieren können. Das "x" steht hier für Multiplikation.

    Ah... jetzt rappelt's! :) Der Dividend fängt in der Gesamtbetrachtung bei Bit 16 an, so gesehen muss sein Wert deshalb auch mit 2^16 malgenommen werden.

    Damit ist dann die 23 in 8:16-Fixpunktdarstellung und in Little Endian eben $00 $00 $17 - so wie Du das oben im Bild siehst, eingespeichert in $FB, $FC und $FD.

    Den Screenshot finde ich sehr gut. Faszinierend, dass die ganze Routine mit kleiner Demo auf einen einzigen VC20-Schirm passt!

    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

  • Jetzt ist mir noch aufgefallen, dass meine 24-Bit-Näherung für 23/7 doch nicht optimal war.

    $24 $49 $03 hat eine größere Abweichung als $25 $49 $03.

    Ich hatte einfach abgebrochen, als der Rest kleiner war als 2-16, aber tatsächlich hätte man aufrunden und 2-16 noch setzen müssen.

    Jetzt ist die Frage, wie setzt man das programmtechnisch um? :)

    Ich habe die etwas pummelige Lösung gewählt und ein viertes Ergebnisbyte eingeführt. Das höchste Bit dieses Zusatzbytes entscheidet dann, ob aufgerundet wird. So hier:

    Das klappt zwar so, aber ich werde mal wieder das Gefühl nicht los, dass das auch eleganter gehen müsste. Muss ich wirklich das ganze Rundungsbyte zusammennudeln, obwohl mich nur das höchste Bit interessiert?

    Was wären vielleicht noch ganz andere Ansätze?

    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

  • Muss ich wirklich das ganze Rundungsbyte zusammennudeln, obwohl mich nur das höchste Bit interessiert?

    Nein, das ist nicht nötig. Im Akku steht nach Ausführung der Routine der Rest und Du mußt nur nachprüfen, ob der Rest >= Divisor/2 ist. Die dazu nötige Nachbehandlung sieht wie folgt aus:

    Statt #$07 geht auch wieder ein variabler Wert, der muß dann natürlich der gleiche sein wie in der vorgelagerten Integer-Division. Statt Richtung Null bzw. nach unten abzuschneiden, rundet die erweiterte Routine jetzt zum nächstgelegenen Wert. Der SBC-Befehl kann entfallen, wenn der Rest im Programm weiter nicht verwendet wird.

    Ob das Runden jetzt notwendig oder sinnvoll ist, hängt vom Anwendungsfall ab. Bei vielen Geometrie-Algorithmen wird z.B. konstant nach unten gerundet und ggfs. vorher die Eingangsdaten so vorbehandelt, daß das Ergebnis stimmig aussieht. Richtig konkret fällt einem das auf, wenn man z.B. perspektivisch korrektes Texture-Mapping macht: da willst Du die berechneten Textur-Koordinaten immer nur nach unten runden, da Du sonst an zwei Rändern des projizierten Vierecks aus der Textur grob 'herausfällst'.

    Du solltest dir auch noch überlegen, was Du mit vorzeichenbehafteten Zahlen machst. ;) Gerade da wird die gerundete Version tendenziell eher lästig. Mit der Version, die Richtung 0 rundet, kannst Du im 2-Komplement die Berechung und die Vorzeichen immer so festlegen:

    |Quotient| = |Dividend| / |Divisor|

    sgn(Quotient) = sgn(Dividend) x sgn(Divisor)

    sgn(Rest) = sgn(Dividend)

    und es gilt immer(!): Dividend = Quotient x Divisor + Rest

    mit |...| := Betrag und sgn(...) := Vorzeichen.


    P.S. Du hast in Bitte melde dich an, um diesen Link zu sehen. am Anfang der Routine LDA #0 vergessen. Den Befehl kannst Du nicht einfach weglassen, sonst rechnet die Routine falsch!

  • Muss ich wirklich das ganze Rundungsbyte zusammennudeln, obwohl mich nur das höchste Bit interessiert?

    Nein, das ist nicht nötig. Im Akku steht nach Ausführung der Routine der Rest und Du mußt nur nachprüfen, ob der Rest >= Divisor/2 ist.

    Hm... guter Tipp, aber im Akku steht zum Schluss eine 4 (auch in deinem Screenshot), der Rest von 23/7 ist aber 2. :gruebel

    Ich glaube, der Rest steht nach dem 8. Durchgang der Schleife im Akku, oder? Denn dann steht ja auch das ganzzahlige Ergebnis fest.

    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

  • Du rechnest ja tatsächlich den Rest von 23x65536 / 7 aus, dieser Rest ist 4 und das ist auch der Rest der zur Rundung der 16. "Nachkommastelle" (in binär) relevant ist!

    Noch dazu:

    Der Dividend fängt in der Gesamtbetrachtung bei Bit 16 an, so gesehen muss sein Wert deshalb auch mit 2^16 malgenommen werden.

    Tatsächlich skalieren wir hier den Dividenden mit 2^16 und damit auch den Quotient. Der Dividend muß dann auch nicht mehr zwangweise ganzzahlig sein, Du kannst z.B. auch 23.5/7 ausrechnen, indem Du (skaliert) 1540096 / 7 rechnest (gibt 220013 mit Abrunden -> 220013/65536 = 3.35713... und 23.5/7 = 3.35714...)

  • Argh, ja, das Wort "Rest" hat mich verwirrt. :saint:

    Werde am Wochenende weiter tüfteln.

    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 zur Ergänzung/Korrektur meines Post Bitte melde dich an, um diesen Link zu sehen.:

    Der Dividend muß dann auch nicht mehr zwangweise ganzzahlig sein, [...]

    genauer: Der originale Dvidend [...]

    Ob man jetzt den Zugang über eine Fixpunkt-Darstellung oder allgemeiner, über Skalierung sucht, wesentlich ist, daß der Computer auf keinen Fall mit echt gebrochenen Werten rechnen kann *) - allenfalls mit sehr großen ganzen Zahlen! Was man da als "Fließkommazahlen" verkauft bekommt, sind tatsächlich Maschinenzahlen und die sind selbst nur eine endliche(!) Teilmenge der rationalen Zahlen. Der Exponent sorgt dann dafür, daß man nicht mit einer fixen Skalierung rechnen muß, und dadurch kann dann größenordnungsmäßig ein größerer Zahlbereich zwischen 0 und unendlich abgedeckt werden.


    *) sonst wärst Du nämlich gerade mit einem Analog-Rechner unterwegs und der ist dann in der Genauigkeit durch Rauschen limitiert. :)

  • wesentlich ist, daß der Computer auf keinen Fall mit echt gebrochenen Werten rechnen kann *) - allenfalls mit sehr großen ganzen Zahlen!

    Da lag der Knackpunkt: Ich wollte gefühlsmäßig die Zahl immer noch in Vorkomma- und Nachkommateil aufspalten, obwohl das durch die Skalierung eigentlich gar keinen Sinn mehr ergab.

    Auf jeden Fall echt gut, diese Skalierung. :)

    Noch kurz:

    P.S. Du hast in Bitte melde dich an, um diesen Link zu sehen. am Anfang der Routine LDA #0 vergessen. Den Befehl kannst Du nicht einfach weglassen, sonst rechnet die Routine falsch!

    Da hatte ich einfach den ganzen INIT-Block zur Vereinfachung weggelassen. dvd und dvd+1 ($fb und $fc in deinem Code) müssen ja auch vorher 0 gesetzt werden, oder?

    Auf jeden Fall sieht das komplette Programm bei mir jetzt so aus und funktioniert auch:

    Nochmal danke für die guten Tipps!

    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

  • Da hatte ich einfach den ganzen INIT-Block zur Vereinfachung weggelassen. dvd und dvd+1 ($fb und $fc in deinem Code) müssen ja auch vorher 0 gesetzt werden, oder?

    Nochmal: ohne den expliziten "LDA #0"-Befehl ganz am Anfang ist die Routine kaputt! Wenn der Befehl fehlt und beim Eintritt in die verbockte Routine ein nicht-Null Wert im Akku steht, dann rechnet sie nicht richtig.

    Die Eingangsdaten in zp, zp+1, zp+2 sind da anders gelagert. Auch wenn in zp und zp+1 nicht 0 drin steht, wird die ganze 24-Bit-Zahl korrekt durch 7 geteilt. Darauf wollte ich auch mit dem Beispiel von "23.5/7" hinweisen - dann steht nämlich im "gebrochenen" Teil des Dividenden (also, in $FB und $FC) was anderes als Null.