Division und Vergleiche in Hardware

Hallo,
wie würdet Ihr möglichst effizient in Hardware den Rest der Division X/Y
berechnen, wobei X eine 2n-Bit Zahl und Y eine n-Bit Zahl ist.
Außerdem suche ich eine Begründung, warum Vergleiche in Hardware
ineffizient sind.
Ich würde mich über entsprechende Tipps und Literaturempfehlungen freuen.
Gruß,
Christof
Reply to
Christof Kluß
Loading thread data ...
Dieses Thema gehört eigentlich nicht nach dsie, betrifft aber viele Bereiche und somit ist es wahrscheinlich schwierig, DIE passende Gruppe dafür zu finden, jedoch passt de.sci.electronics eher als dsie.
F'up nach dse
Und mir fällt ein Papier einer IEEE-Konferenz (mittlerweile zwei Ewigkeiten her) dazu ein:
formatting link
Gruß, Mario
Reply to
Mario F. Duhanic
"Christof Kluß" schrieb im Newsbeitrag news: snipped-for-privacy@individual.net...
Hallo Christof,
In jedem Mikroprozessor ist ein Hardware-Vergleicher eingebaut, die ALU. Die macht nicht nur A+B oder A-B, sondern sie hat Ausgänge für . Wo sonst kämen die Flags her auf die man Abfragen machen kann wie wenn A>B dann springe nach xyz?
Abfrage auf Gleichheit ist einfach A-B und dann z.B. mit einem OR-Gatter alle Bits des Ergebnises auf 0 vergleichen.
Vielelicht solltest du den Begriff ineffizient genauer spezifizieren.
Parallele Division ist in der Tat schwierig. Deshalb wird das meistens Bit für Bit sequentiell gemacht. Dazwischen gibt es Mischformen die mit Tabellen zu guten Schätzwerten kommen die dann mit wenigen Iterationen zu genauen Ergebnissen führen.
Gruß Helmut
Reply to
Helmut Sennewald
Christof Klu=DF schrieb:
Hallo,
f=FCr ein gen=FCgend kleines n ist das einfach, man programmiert es in ei= n=20 Eprom, f=FCr ein n bis 6 geht das so noch. F=FCr n > 16 wird man an iterativen Methoden nicht vorbei kommen.
Um welches n geht es denn nun?
Bye
Reply to
Uwe Hercksen
Helmut Sennewald schrieb:
Hallo,
wobei ein schneller Addierer f=FCr gro=DFe Wortl=E4ngen so einfach auch w= ieder=20 nicht ist wenn Ripple Carry =FCber die ganze Breite nicht mehr geht.
Bye
Reply to
Uwe Hercksen
Hallo Uwe,
erstmal Danke für eure Antworten.
Uwe Hercksen wrote:
Also konkret geht es um einen Vergleich von Algorithmen für die Modularmultiplikation, die z.B. für RSA benötigt wird, wo dann n im Bereich von 512-2048 Bit liegt.
Nun möchte man also XY mod M berechnen, dazu gibt es z.B. folgende Möglichkeiten
1) klassische Methode, also P = X*Y berechnen und dann den Rest der Division P / M berechnen.
Nachteile: P ist 2n-Bit lang, aber wie sieht hier der Algorithmus konkret aus. Was gibt es noch für Nachteile?
2) Verschränkte Modularmultiplikation P := 0 for i = n-1 to 0 P = 2*P + x_i*Y if (P >= M) then P := P - M if (P >= M) then P := P - M
Nachteile: Vergleiche, die nicht parallel ausgeführt werden können. Für die Vergleiche sind nichtredundaten Addierer nötig? Also der größte Nachteil bei Vergleichen scheint die Laufzeit zu sein.
3) Montgomery Modularmultiplikation (berechnet X*Y*2^-n mod M) P := 0 for i = 0 to n-1 P := P + x_i*Y if (p_0 = 1) P := P + M P := P / 2 if (P >= M) then P := P - M
Hier wird nur am Ende ein Vergleich gebraucht. Außerdem kann man redundanten Addierer benutzen usw.
Nachteile: Vor- und Nachberechnung nötigt
Also im Grunde bräuchte ich mehr Argumente was an dem einen Algorithmus so viel schlechter als am anderen ist. Man könnte da jetzt sicher konkret die Area/Time Komplexität ausrechnen, aber es geht mir eher ums Grundverständnis.
Gruß, Christof
Reply to
Christof Kluß
Hallo Christof,
Probier mal Google mit folgendem Text.
division 1024 bit
Da gibt es seitenweise Treffer mit obigem Suchtext.
Gruß Helmut
"Christof Kluß" schrieb im Newsbeitrag news: snipped-for-privacy@individual.net...
Reply to
Helmut Sennewald
Christof Klu=DF schrieb:
Hallo,
bei so grossen n bedeutet das einen f=FCrchterlichen Aufwand f=FCr eine=20 reine Hardwarel=F6sung. Bitserielle Verfahren kommen ja wohl nicht in=20 Frage, aber auch damit w=E4re eine Division sehr aufwendig, aber auch=20 =E4usserst langsam.
Bye
Reply to
Uwe Hercksen

Site Timeline

PolyTech Forum website is not affiliated with any of the manufacturers or service providers discussed here. All logos and trade names are the property of their respective owners.