binärer Modulo-Algorithmus

mdsnake

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

volkard

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?

mdsnake

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

volkard

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.

Mis2com

Welche Basis hat log denn?

mdsnake

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

Taurin

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.

volkard

mdsnake schrieb:

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

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

mdsnake

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

volkard

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

mdsnake

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

mfg mdsnake