Schneller Divisions-Algirthmus 384bit / 27

[Mampf F. (mampf)]

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

[Vonwas (Gast)]

> Optimal wären 24 Taktzyklen ...

Du bist die erste Lachnummer der laufenden KW.

[Wegstaben V. (wegstabenverbuchsler)]

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.

[C. A. Rotwang (Gast)]

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

[Christoph db1uq K. (christoph_kessler)]

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.

[Jens W. (jensw)]

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

[Sebastian S. (amateur)]

@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.

[berndl (Gast)]

hm, kannst du die Division durch 27 evtl. durch geschicktes Aufsummieren 
nach shift-right hinbekommen? Also

z/32 + z/512 + z/.... + ...

also Zaehlerwert nach rechts schieben, z.B. 5; 9; ... und dann 
aufaddieren

[Yalu X. (yalu) (Moderator)]

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.

?

[Christoph db1uq K. (christoph_kessler)]

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?

[Mampf F. (mampf)]

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!

[Pandur S. (jetztnicht)]

384 Bit division fuer crypto ..

[PCB (Gast)]

Du könntest durch 32 teilen, also 6 rechtsshifts, das Ergebnis merken, 
die Ausgangszahl mit 5 multiplizieren und beide Ergebnisse aufaddieren.