binärer Modulo-Algorithmus



  • Hallo Leute,

    ich bin auf der Suche nach einem Algorithmus für die Modulo-Operation bezogen auf Binärzahlen. Natürlich könnte man den Euklidischen Algorithmus binär umsetzen.
    Im schlimmsten Falle benötigt dieser aber 2^Wortlänge-1 Subtraktionen, was bei mir zu viel ist.
    Gibt es einen binären Algorithmus, welcher mod in ~n Schritten berechnen kann??

    mfg mdsnake



  • mdsnake schrieb:

    Natürlich könnte man den Euklidischen Algorithmus binär umsetzen.
    Im schlimmsten Falle benötigt dieser aber 2^Wortlänge-1 Subtraktionen, was bei mir zu viel ist.
    Gibt es einen binären Algorithmus, welcher mod in ~n Schritten berechnen kann??

    euklid binär gips namens "binary gcd". der braucht nicht log(wortlänge) divisionen, sondern nur log(wortlänge) subtraktionen.
    was hilft der zum modulo-rechnen?



  • Ich hatte die Variante: (x mod y) -> x-y solange bis x-y<y -> ausgabe
    irgendwie als euklidischen Alg. im Gedächtnis, könnte mich da natürlich aber auch geirrt haben. Wenn es so sein sollte,dann weg mit dem eukli...

    mfG mdsnake



  • mdsnake schrieb:

    Ich hatte die Variante: (x mod y) -> x-y solange bis x-y<y -> ausgabe irgendwie als euklidischen Alg. im Gedächtnis, könnte mich da natürlich aber auch geirrt haben. Wenn es so sein sollte,dann weg mit dem eukli...

    macht ja nix.
    sei TAUSEND ne beliebige aber zu große zahl.
    (x mod y) -> x-y solange bis x-y<y
    kostet schlimmstenfalls (bei x=TAUSEND, y=1) TAUSEND subraktionen.
    schneller wäre

    (x mod y) -> 
       y solange verdoppeln, wie y<=x
    
       solange y<=x
         y von x anziehen
         y halbieren
    

    kostsich nur log(TAUSEND) verdoppelungen, vergleiche und subtraktionen.
    verdoppelungen, vergleiche und subtraktionen kosten je auch nur log(TAUSEND) schritte.

    also statt deiner 2^Wortlänge bin ich bei Wortlänge^2, was hoffentlich nicht das gleiche ist.



  • Welche Basis hat log denn?



  • Jo, prinzipiell reicht deine Variante, drum danke. Das einzige, was noch ein wenig ungünstig ist, sind die ganzen Vergleiche, da diese in meiner Struktur sehr aufwendig(ungünstig sind). Optimal wäre eine Variante, bei der man sich die ständigen Vergleiche sparen könnte!
    Gibts da nen Algorithmus, der auschließlich mit shifts,Additionen und Subtraktionen auskommt und auch noch die Laufzeitbedingungen erfüllt??

    mfg mdsnake



  • Mis2com schrieb:

    Welche Basis hat log denn?

    Bei der Berechnung der Komplexitäten eines Algorithmus ist einem das meistens
    egal. Es kommt dabei im wesentlichen auf das Verhalten für große Zahlen (also
    beinahe unendliche) Zahlen an. Und da ist es einem die Basis egal, da man ausdrücke
    wie n*log(n) mit n^2 vergleicht. Und da schneidet n*log(n) stets besser ab.
    Man spricht deswegen auch von asymptotischer Komplexität.



  • mdsnake schrieb:

    die ganzen Vergleiche, da diese in meiner Struktur sehr aufwendig(ungünstig sind).

    vergleiche teurer als additionen???
    erklärste mal deine struktur?



  • Also, ich schreibe ein Programm, dass systemc nutzt um damit Hardware zu simmulieren. Im wesentlichen handelt es sich um einen Controller und eine Add/Sub - Zelle. Diese Add/Sub -Zellen werden als mehrere Piplinestufen nacheinander angeordnet. Der Controller sagt jeder Stufe, was sie zu tun hat. Mit hilfe dieser Pipline werden die Grundoperationen für ganze Zahlen(add,sub,mult,div,mod) bereitgestellt. Die Zellen arbeiten intern mit einem redundanten Zahlensystem und führen die Addition u. Subtraktion zweier Zahlen in jeweils einem Takt aus.

    Das Problem ist nun,dass die Hardware für eine add/sub Operation sowieso in jeder Stufe zur verfügung steht. Die Hardware für die Vergleiche zweier Zahlen müßte noch extra für jede Stufe mit synthetisiert werden.
    Genau diese Synthese, extra nur für mod, würde ich gern vermeiden wollen und lieber mit korrekturoperationen oder ähnlichem arbeiten.

    mfg mdsnake



  • ok, problem verstanden.
    aber ich sehe leider keine lösung, die vergleiche zu sparen.



  • Hmm schade, aber trotzdem danke für deine Hilfe und den verbesserten Algorithmus...

    mfg mdsnake


Anmelden zum Antworten