Guten Morgen,
ich hätte da ein kleines Problem, das ich auch selbst mit intensiven
Recherchen nicht selbst lösen konnte.
Und zwar suche ich einen Divisions-Algorithmus, der möglichst flink
384Bit Binärzahlen in die Basis 3 oder 27 umrechnet.
Ich hatte ein paar Implementierungen, die alle mehr oder weniger recht
langsam waren. Eine iterative Divider-Variante die es auf stolze 50k
Taktzyklen (@100MHz) gebracht hat. Eine iterative Variante, die mit dem
Kehrwert von 27 multipliziert kam sowas auf 5k.
Für meine bisherige Anwendung war das in Ordnung ("gutes pferd springt
nur so hoch wie es muss" und so ...), leider habe ich nun andere
Anforderungen und dafür ist die Division viel zu langsam, mir gehen aber
leider die Ideen aus.
Optimal wären 24 Taktzyklen - aber auch 240 wären deutlich besser.
Hätte jemand eine Idee, was man machen könnte?
Ich hatte beim Googeln was von Array-Dividern gelesen? Wäre das ein
möglicher Anwendungsfall dafür?
Viele Grüße,
Mampf
Gast
#6180763
> Optimal wären 24 Taktzyklen ...
Du bist die erste Lachnummer der laufenden KW.
Mampf F. schrieb: > Ich hatte ein paar Implementierungen, dann wäre es doch hilfreich, genau DIESE Algorithmen (incl. der verwendeten Sprache bzw. Compiler, Libraries etc) hier zu benennen bzw. vorzustellen, damit sie hier diskutiert (und gegebenenfalls final verworfen) werden können.
Gast
#6180768
Mampf F. schrieb: > Hätte jemand eine Idee, was man machen könnte? CORDIC gilt als Allheilmittel fürs numbercrunchen auf digitaltechnik: http://www.andraka.com/files/crdcsrvy.pdf
Multiplizierer gibt es eher als Hardware, für einen festen Divisor kann man mit dem Kehrwert multiplizieren. Die sind aber auch keine 384 Bit breit, also muss man mehrfach multiplizieren, und aufaddieren. Die 24 Taktzyklen sind so auch nicht erreichbar.
Hallo, Du kannst mal nach Radix-2 suchen. Da hatte Lothar was auf seiner Homepage. Er brauchte einen Takt pro bit (bei dir wären das 384 Takte). Oder du beschäftigst dich mit Kettenbrüchen. Da könntest du geschickt mit einer Multiplikation erweitern um dann die Division durch ein Shift zu erledigen. Gruß, Jens
@Mampf F. Na denn mal guten Appetit! In Brat und Grill sind Deine gewünschten Schritt zahlen wohl kaum erreichbar. Höchstens in Ene-Mene-Muh könnte es gehen. Willst Du aber etwas Genaueres haben, so wären ein Hinweis auf die verwendete Architektur und die verwendete Sprache nicht schlecht. Bitte verabschiede Dich doch gleich mal vor deinen 24/240 Schritten.
Gast
#6181262
hm, kannst du die Division durch 27 evtl. durch geschicktes Aufsummieren nach shift-right hinbekommen? Also
1 | |
also Zaehlerwert nach rechts schieben, z.B. 5; 9; ... und dann aufaddieren
Suchst du nun einen Mampf F. schrieb: > Divisions-Algorithmus oder einen > Algorithmus, der möglichst flink 384Bit Binärzahlen in die Basis 3 > oder 27 umrechnet. ?
2 hoch 384 = 3,94020062×10¹¹⁵, wo in der Natur braucht man solche Präzision? Das mit der Basis 3 oder 27 habe ich auch nicht kapiert, was hat das mit einer Division zu tun?
Hmm, Division hab ich jetzt per Pipelining hinbekommen - in 27 clock cycles pro Div @ 75MHz. Nicht optimal, aber auch nicht so schlecht wie zuvor. Ich muss leider iterativ die 384Bit in 16bit-Teile verarbeiten, weil sonst das Timing völlig kaputt ist. Eventuell könnte ich noch mit multicycle-paths experimentieren, damit ich wenigstens meine 100Mhz wieder bekomme, auch wenn der eigentliche Datendurchsatz nicht höher ist. 32Bit Divisionen haben timing-technich überhaupt nicht funktioniert. Ist natürlich fraglich, wie es bei höherem Füllstand dann mit dem Timing aussieht. Laut Simulation kommt das richtige aus - und da ich nur taktsynchron zu einem Clock bin, funktioniert es in echt sicher auch. Die Division ist nur ein Teil einer Basis-Convertierung - aber da dividiert man ja nur mehrfach hintereinander. Ich glaub, das Thema hat sich dann erledigt :) Vielen Dank für eure Hilfe!
384 Bit division fuer crypto ..
Gast
#6200513
Du könntest durch 32 teilen, also 6 rechtsshifts, das Ergebnis merken, die Ausgangszahl mit 5 multiplizieren und beide Ergebnisse aufaddieren.
Beitrag #6205362 wurde von einem Moderator gelöscht.
Antwort schreiben
Bitte melde dich an, um einen Beitrag zu schreiben.