Texter mir x: effektiver künstlicher Zahlenüberlauf oder Modulo selber gemacht

Hallo,

da ich hier schon in einigen Antworten ein tiefgreifendes Verständnis für Zahlen und Gesetzmäßigkeiten beobachten konnte, setlle ich mal ein Problem zur Lösung.

Ich brauche eine Funktion, die mir einen Zahlenüberlauf realisiert bzw. aus einer Zahl die Zahl macht die entstanden wäre, wenn es einen Überlauf gegeben hätte. Der Wertebereich sollte z.B. von 0 bis 359 gehen (ganze Zahlen), obwohl es ein vorzeichenbehafteter 32bit-integer ist (ein 32bit-Überlauf muß nicht berücksichtigt sein, so groß werden die "Eingangszahlen" nicht).

Das ganze würde natürlich mit Modulo gehen aber der steht nicht zur Verfügung. Ich habe zwar schon mal einen Modulo selber programmiert aber der war relativ ineffizient (ich muß um jeden Prozessortakt ringen). Ich hoffe nun, es gibt eine effizientere Lösung, vielleicht eine auf Bit-Ebene, die ich nicht sehe.

An schnellen Befehlen, die in Frage kommen, stehen zur Verfügung:

  • die vier Grundrechenarten
  • bitweise and or xor not
  • shift links und rechts
  • Inkrementieren und Dekrementieren (hat aber keinen Rückgabewert, sondert ändert die Variable am Speicherort)
  • Betragsbildung
  • if ... else ... endif
    Der Syntax, den ich verwende, soll weitestgehend BASIC entsprechen (was ich kaum kenne), ist aber was Spezielles mit vielen hardwarespezifischen Befehlen.

Die Suchmaschinen haben mir nicht viel geholfen, da "Modulo" häufig erwähnt wird, wenn es verwendet wird und google das gar mit dem Wort Mod assoziiert, was Unmengen Suchergebnisse zu Modifikationen liefert.

  1. Hello out there!

    Schleifen hast du auch zur Verfügung?

    WHILE x >= m DO x = x - m

    kommt ohne Division aus. (x ist deine Eingabe; m dein Modul, in deinem Bsp. 360)

    Der Syntax,

    _die_ Syntax [Wikipedia, Wiktionary]

    See ya up the road,
    Gunnar

    --
    „Und [dieses Forum] soll […] auch ein Fachforum bleiben und kein Psychologieforum werden.“ (Kirsten Evers)
    1. Schleifen hast du auch zur Verfügung?

      WHILE x >= m DO x = x - m

      Ja, do while und for. Deren Zeitverhalten habe ich aber noch nie untersucht und die Hardware ist gerade in Gebrauch so das ich das jetzt nicht testen kann.

      Deine Lösung funktioniert aber nicht für negative x. Mit einer Fallunterscheidung dürfte es schon zu langsam sein, muß ich aber testen.

      PS: x ist vermutlich immer kleiner als das Vierfache von m aber eine Lösung die davon unabhängig ist, wäre natürlich besser.

      1. Hello out there!

        WHILE x >= m DO x = x - m
        Deine Lösung funktioniert aber nicht für negative x.

        Dann musst du natürlich addieren:

        WHILE x < 0 DO x = x + m

        PS: x ist vermutlich immer kleiner als das Vierfache von m

        Dann soll das schnell genug sein.

        aber eine Lösung die davon unabhängig ist, wäre natürlich besser.

        Dann kommst du wohl nicht um eine Division herum. Ob diese samt Auswertung des Ergebnisses schneller ist als ein paar wenige Additionen/Subtraktionen, hängt wohl von der Hardware ab.

        See ya up the road,
        Gunnar

        --
        „Und [dieses Forum] soll […] auch ein Fachforum bleiben und kein Psychologieforum werden.“ (Kirsten Evers)
  2. Yerf!

    Das ganze würde natürlich mit Modulo gehen aber der steht nicht zur Verfügung.

    Wir suchen also ein z = x mod y

    An schnellen Befehlen, die in Frage kommen, stehen zur Verfügung:

    • die vier Grundrechenarten

    Integer?

    z = x - ((x / y) * y)

    bei Float wirds komplizierter...

    • Betragsbildung

    Damit könnte man evtl. Probleme mit negativem x umgehen.

    x mod y = abs(x) mod y // oder lieg ich da grad falsch?

    Gruß,

    Harlequin

    1. Hello,

      Das ganze würde natürlich mit Modulo gehen aber der steht nicht zur Verfügung.

      Wir suchen also ein z = x mod y

      An schnellen Befehlen, die in Frage kommen, stehen zur Verfügung:

      • die vier Grundrechenarten

      Integer?

      z = x - ((x / y) * y)

      Man weiß ja nicht, wei es umgesetzt wir und auf welchem Prozessor.
      Aber ich gehe mal davon aus, dass es kein Mathematischer Coprozessor ist, sondern irgendeine eine Single-Chip-Gurke.

      Da wären DIV und MUL auf jeden Fall sehr teure Statements.

      Als Beispiel beim Beim 8086

      DIV    3+9+16+4+4+4+17 = 57  (zuzügl. 2*EA)   genau nachvollziehbar
       MUL    77+133+83+139   = 432 (zuzügl. 2*EA)   Maximalwert
       SUB    90+162+168      = 420 (zuzügl. 2*EA)

      Das muss man sich also sehr genau überlegen, ob man nicht lieber eine Abbildung von "repnz" oder so ähnlich benutzt. Das ist bei den hardwarenahen Hochsprachen i.d.R. in For-Schleifen umgesetzt.
      Wenn es sich um sogenannte "dedizierte For-Schleifen" handelt, in denen man den Schleifenzähler wärend der Abarbeitung nicht mehr verändrn darf, sind die extrem schnell.

      Das kann man aber eben nicht beantworten, ohne den Assempler-Code Deiner Hochsprache zu haben und ohne den Prozessortyp genauer zu kennen.

      Wenn es um das Ausknautschen von Taktzyklen geht, wird ja wohl Portierbarkeit eher keine Rolle spielen

      Harzliche Grüße vom Berg
      http://bergpost.annerschbarrich.de

      Tom

      --
      Fortschritt entsteht nur durch die Auseinandersetzung der Kreativen
      Nur selber lernen macht schlau
      Ein Jammer ist auch, dass die Dummen so selbstsicher und die Klugen voller Zweifel sind. Das sollte uns häufiger zweifeln lassen :-)

      1. Hello,

        *ups*, wie konnte denn das passieren?

        SUB    3+9+16+4+4+4+17 = 57  (zuzügl. 2*EA)   genau nachvollziehbar

        MUL    77+133+83+139   = 432 (zuzügl. 2*EA)   Maximalwert

        DIV    90+162+168      = 420 (zuzügl. 2*EA)

        so herum latürnich (sic!)

        Harzliche Grüße vom Berg
        http://bergpost.annerschbarrich.de

        Tom

        --
        Fortschritt entsteht nur durch die Auseinandersetzung der Kreativen
        Nur selber lernen macht schlau
        Ein Jammer ist auch, dass die Dummen so selbstsicher und die Klugen voller Zweifel sind. Das sollte uns häufiger zweifeln lassen :-)

      2. Yerf!

        Man weiß ja nicht, wei es umgesetzt wir und auf welchem Prozessor.

        Deshalb wollte ich eine weitere Lösung zud er von Gunnar posten. Vergleichen, was nun schneller ist, kann nur der OP.

        Gruß,

        Harlequin

      3. Sorry, das wollte ich eigentlich gleich dazuschreiben.

        = (Zuweisung) 2 Takte
        +, -, * je 2 Takte
        / 5 Takte
        inc, dec je 3 Takte (inklusive Zuweisung)
        absi (Betragsbildung) 3 Takte
        and, or, xor je 2 Zakte
        not 1 Takt
        shift weiß ich gerade nicht
        if ... else ... endif mit einer Bedingung 6+3 Takte wenn wahr, 4 Takte wenn falsch

        Der Prozessor ist ein DPS mit 40 Mhz.

        1. Yerf!

          = (Zuweisung) 2 Takte
          +, -, * je 2 Takte
          / 5 Takte

          Wobei es schon komisch ist, dass der Prozessor * und / so gut kann aber dann kein Modulo...

          Gruß,

          Harlequin

          1. Hello,

            = (Zuweisung) 2 Takte
            +, -, * je 2 Takte
            / 5 Takte

            Wobei es schon komisch ist, dass der Prozessor * und / so gut kann aber dann kein Modulo...

            only RISC brings fun

            oder wie hieß der Spruch mit dem Germanismus drin?

            Harzliche Grüße vom Berg
            http://bergpost.annerschbarrich.de

            Tom

            --
            Fortschritt entsteht nur durch die Auseinandersetzung der Kreativen
            Nur selber lernen macht schlau
            Ein Jammer ist auch, dass die Dummen so selbstsicher und die Klugen voller Zweifel sind. Das sollte uns häufiger zweifeln lassen :-)

            1. Yerf!

              only RISC brings fun

              oder wie hieß der Spruch mit dem Germanismus drin?

              No RISC no fun

              Aber Modulo gehört bei Integer doch eigentlich zu den Grundrechenarten (gerade  auch weil das Nachbilden über die anderen Operationen so aufwendig ist).

              Gruß,

              Harlequin

              1. Aber Modulo gehört bei Integer doch eigentlich zu den Grundrechenarten (gerade  auch weil das Nachbilden über die anderen Operationen so aufwendig ist).

                Ich werde mal bei den Entwicklern anfragen. Bei einer anderen Gelegenheit haben die mir auch eine undokumentierte Funktion verraten, die unsagbar nützlich war für meine Zwecke.

    2. Integer?

      z = x - ((x / y) * y)

      Ja, ganze Zahlen.

      Beispiel:
      -10, -370, -730 ist gleichbedeutend und soll 350 ergeben
      370, 730, 1090 ist gleichbedeutend und soll 10 ergeben

      z = x - ((x / y) * y) ergibt
      -10 (mit absi ist da nichts zu machen)
      10

      Ich komme jetzt auf folgendes, ich glaube meine alte Lösung war noch etwas schlechter:
      z = (x + 1440) - (((x + 1440) / y) * y) ergibt
      350
      10
      Das sind 15 Takte ohne Klammern. Bei Klammern verhält sich der Compiler relativ undurchschaubar, das muß ich testen. Vermutlich sind es in Summe 18 Takte.

      Da ich die Funktion je Prozeßaufruf relativ häufig ausführen muß, sind 18 Takte für einen Überlauf der sonst nebenbei Auftritt recht viel. Leider funktioniert das nur bei 2^x.

      Daher hatte ich auf eine schnelle Lösung auf Bit-Ebene gehofft.

      1. Yerf!

        Beispiel:
        -10, -370, -730 ist gleichbedeutend und soll 350 ergeben
        370, 730, 1090 ist gleichbedeutend und soll 10 ergeben

        Das ist aber kein normales Modulo...

        Ich komme jetzt auf folgendes, ich glaube meine alte Lösung war noch etwas schlechter:
        z = (x + 1440) - (((x + 1440) / y) * y) ergibt

        ...etwas anderes

        Das sind 15 Takte ohne Klammern. Bei Klammern verhält sich der Compiler relativ undurchschaubar, das muß ich testen. Vermutlich sind es in Summe 18 Takte.

        Bei der Geschwindigkeit für Multiplikation/Division dürfte das aber der schneller Weg sein, eine Schleife ist da sicherlich langsamer.

        Daher hatte ich auf eine schnelle Lösung auf Bit-Ebene gehofft.

        Auf Bit-Ebene kann man leider nur mit 2er-Potenzen hantieren...

        Gruß,

        Harlequin

        1. Hello,

          Auf Bit-Ebene kann man leider nur mit 2er-Potenzen hantieren...

          Da gibt's auch Tricks für MUL 3 oder DIV 3 usw. Für 5 gab es auch was...

          Aber das ist lange her. Da müsste ich jetzt selber in die alten Bücher schauen. Aus dem Kopf weiß ich das nicht mehr.

          Harzliche Grüße vom Berg
          http://bergpost.annerschbarrich.de

          Tom

          --
          Fortschritt entsteht nur durch die Auseinandersetzung der Kreativen
          Nur selber lernen macht schlau
          Ein Jammer ist auch, dass die Dummen so selbstsicher und die Klugen voller Zweifel sind. Das sollte uns häufiger zweifeln lassen :-)

        2. Das ist aber kein normales Modulo...

          Das ist ein Überlauf, das Modulo habe ich doch nur gesucht, um einen Überlauf zu machen.

          Also ich habe getestet:
          die do ... until Schleife wird mind. einmal durchlaufen, was bei Werten im Wertebereich "ungünstig" ist. Im worst-case Fall ist sie zu langsam (8 bis 28 Takte im Beispiel) und würde mit einer Fallunterscheidung noch um bis 9 Takte langsamer werden.

          Meine neue Lösung braucht nur 15 Takte. Der Compiler scheint verbessert worden zu sein, seit ich mich beschwert habe, daß selbst doppelte Klammern um einen Ausdruck nicht optimiert werden. Auf Assembler-Niveau könnte man noch 2 Takte rausholen, weil eine Subtraktion doppelt ist. Das zu erkennen ist aber vom Compiler zu viel erwartet.

          15 Takte gilt es zu schlagen. Ich danke aber schon mal, daß ich aufgrund der Vorschläge erneut nachdenken mußte und dabei auf eine bessere Lösung gekommen bin. Im Moment bekomme ich die x mal 15 Takte auch noch unter aber Alles ist noch nicht umgesetzt.

          1. Hallo,

            Ist das noch aktuell?

            15 Takte gilt es zu schlagen.

            Nur 15 Takte für dein Modulo? Das ist schwer zu toppen, wenn man nicht hardwarenah programmieren kann, wie z.B. so:

            MOV AX, Wert
            XOR DX, DX
            MOV BX, Modul
            DIV BX

            Das Ergebnis der Divison befindet sich jetzt in AX, wobei der gesuchte Rest der Division in DX steht.

            Im Moment bekomme ich die x mal 15 Takte auch noch unter

            Wieso x mal 15 Takte? Verstehe nicht ganz, aber egal...

            Eine Lösung auf Bit-Ebene ist auch möglich, aber halt kaum unter 15 Takten. Man müsste zuerst wissen, wieviel Takte ein SHR 8 braucht.

            Also ist es noch aktuell? Dann würde ich noch ein bischen drüber meditieren, solche Kopfnüsse interessieren mich :-)

            Gruß, Don P

            1. Hello,

              15 Takte gilt es zu schlagen.

              Nur 15 Takte für dein Modulo? Das ist schwer zu toppen, wenn man nicht hardwarenah programmieren kann, wie z.B. so:

              MOV AX, Wert
              XOR DX, DX
              MOV BX, Modul
              DIV BX

              Das Ergebnis der Divison befindet sich jetzt in AX, wobei der gesuchte Rest der Division in DX steht.

              Und wieviele Takte benötigt welche Operation?
              Insbesondre DIV dürfte doch auch heute noch mehr als 150 Takte benötigen?

              Harzliche Grüße vom Berg
              http://bergpost.annerschbarrich.de

              Tom

              --
              Fortschritt entsteht nur durch die Auseinandersetzung der Kreativen
              Nur selber lernen macht schlau
              Ein Jammer ist auch, dass die Dummen so selbstsicher und die Klugen voller Zweifel sind. Das sollte uns häufiger zweifeln lassen :-)

              1. Und wieviele Takte benötigt welche Operation?
                Insbesondre DIV dürfte doch auch heute noch mehr als 150 Takte benötigen?

                Die Division benötig auf diesem Prozessor, so wie sie vom Compiler umgesetzt wird, 5 Takte.

                1. Hello,

                  Und wieviele Takte benötigt welche Operation?
                  Insbesondre DIV dürfte doch auch heute noch mehr als 150 Takte benötigen?

                  Die Division benötig auf diesem Prozessor, so wie sie vom Compiler umgesetzt wird, 5 Takte.

                  Wie geht das?
                  Wie zählt das?

                  Man muss doch mindestens zwei Register mit Werten laden und dann den Befehl auch noch übermitteln, das Ergebnis abholen usw...

                  Harzliche Grüße vom Berg
                  http://bergpost.annerschbarrich.de

                  Tom

                  --
                  Fortschritt entsteht nur durch die Auseinandersetzung der Kreativen
                  Nur selber lernen macht schlau
                  Ein Jammer ist auch, dass die Dummen so selbstsicher und die Klugen voller Zweifel sind. Das sollte uns häufiger zweifeln lassen :-)

                  1. Die Division benötig auf diesem Prozessor, so wie sie vom Compiler umgesetzt wird, 5 Takte.

                    Wie geht das?

                    Öhm, vielleicht findest Du die Antwort hier:
                    http://www.analog.com/UploadedFiles/Data_Sheets/ADSP-21060_21060L.pdf
                    So einer ist es, komisch nur, daß dort von 6 Takten die Rede ist.

                    Wie zählt das?

                    Man muss doch mindestens zwei Register mit Werten laden und dann den Befehl auch noch übermitteln, das Ergebnis abholen usw...

                    Wie das zählt? Nur die Division kostet 5 Takte, egal ob mit Konstanten oder Variablen (allerdings nur mit Variablen aus dem internen RAM), Für die Zuweisung des Ergebnisses auf eine Variable werden noch mal zwei Takte fällig.

                    1. Hello,

                      http://www.analog.com/UploadedFiles/Data_Sheets/ADSP-21060_21060L.pdf
                      So einer ist es, komisch nur, daß dort von 6 Takten die Rede ist.

                      Geniales Teil.

                      Harzliche Grüße vom Berg
                      http://bergpost.annerschbarrich.de

                      Tom

                      --
                      Fortschritt entsteht nur durch die Auseinandersetzung der Kreativen
                      Nur selber lernen macht schlau
                      Ein Jammer ist auch, dass die Dummen so selbstsicher und die Klugen voller Zweifel sind. Das sollte uns häufiger zweifeln lassen :-)

            2. Hallo,

              Ist das noch aktuell?

              Ja. Der Support hat zwar schon versprochen, nach eine Lösung zu suchen, hat aber noch nicht wieder geantwortet.

              Wieso x mal 15 Takte?

              Weil ich die Funktion mehrfach in einem Prozeßaufruf verwenden muß.

              Eine Lösung auf Bit-Ebene ist auch möglich, aber halt kaum unter 15 Takten. Man müsste zuerst wissen, wieviel Takte ein SHR 8 braucht.

              Jedes shift egal um wieviel Stellen braucht zwei Takte. Damit habe ich auch schon versucht was hinzubekommen, bin aber mit dem Wertebereich zu keinem Ergebnis gekommen.

              Dann würde ich noch ein bischen drüber meditieren, solche Kopfnüsse interessieren mich :-)

              Gruß, Don P

              Auf solche Leute hatte ich gehofft. :-)

              1. Hallo,

                Dann würde ich noch ein bischen drüber meditieren, solche Kopfnüsse interessieren mich :-)

                Auf solche Leute hatte ich gehofft. :-)

                Muss leider passen. Es geht zwar auf Bit-Ebene, ist aber sehr umständlich und dauert viel zu lange mit den vielen and, xor, shift usw., die dazu nötig sind.

                Aber: Dein DSP kann doch Modulo, anscheinend gibt es eine C-Funktion namens fmod, die das erledigt. Vielleicht benutzt du einfach die falsche Programmiersprache?

                Gruß, Don P

                1. Muss leider passen. Es geht zwar auf Bit-Ebene, ist aber sehr umständlich und dauert viel zu lange mit den vielen and, xor, shift usw., die dazu nötig sind.

                  Schade, bei einem Wertebereich von 2^n wäre es natürlich einfach gewesen. Danke für deine Mühe.

                  Aber: Dein DSP kann doch Modulo, anscheinend gibt es eine C-Funktion namens fmod, die das erledigt. Vielleicht benutzt du einfach die falsche Programmiersprache?

                  Ich bin leider an die eine Programmiersprache gebunden. Ich wüßte nicht, wie ich sonst die ganze IO-Hardware ansprechen soll, die mit dem DSP verbaut ist.

                  Es sei denn, man kann das dekompilieren, die entsprechenden Teile ersetzen und wieder kompilieren. Es gibt ein Modul um binär-files direkt zu laden, nicht nur den kompilierten Code aus dem Editor.

                  Wenn noch was rauskommt, werde ich berichten.