Forum: FPGA, VHDL & Co. Schneller Divisions-Algirthmus 384bit / 27


Announcement: there is an English version of this forum on EmbDev.net. Posts you create there will be displayed on Mikrocontroller.net and EmbDev.net.
von Mampf F. (mampf) Benutzerseite


Bewertung
0 lesenswert
nicht lesenswert
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

von Vonwas (Gast)


Bewertung
0 lesenswert
nicht lesenswert
> Optimal wären 24 Taktzyklen ...

Du bist die erste Lachnummer der laufenden KW.

von Wegstaben V. (wegstabenverbuchsler)


Bewertung
0 lesenswert
nicht lesenswert
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.

: Bearbeitet durch User
von C. A. Rotwang (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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

von Christoph db1uq K. (christoph_kessler)


Bewertung
0 lesenswert
nicht lesenswert
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.

von Jens W. (jensw)


Bewertung
0 lesenswert
nicht lesenswert
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

von Sebastian S. (amateur)


Bewertung
-2 lesenswert
nicht lesenswert
@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.

von berndl (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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

von Yalu X. (yalu) (Moderator)


Bewertung
0 lesenswert
nicht lesenswert
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.

?

von Christoph db1uq K. (christoph_kessler)


Bewertung
-1 lesenswert
nicht lesenswert
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?

von Mampf F. (mampf) Benutzerseite


Bewertung
0 lesenswert
nicht lesenswert
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!

: Bearbeitet durch User
von Joggel E. (jetztnicht)


Bewertung
0 lesenswert
nicht lesenswert
384 Bit division fuer crypto ..

von PCB (Gast)


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

Beitrag #6205362 wurde vom Autor gelöscht.

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [vhdl]VHDL-Code[/vhdl]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.