Forum: Mikrocontroller und Digitale Elektronik langsame Division


von Kabal (Gast)


Lesenswert?

Hallo,

ich hab eine Frage zur Laufzeit einer Division einer 32Bit Ganzzahl. 
Wenn ich eine normale Division a3 = a1 / a2; habe, dann dauert die ca 
38mu s.
Ich programmiere mit dem AVR Studio 4 in C und hab einen Atmega128 mit 
16MHz Quarz.
Ist diese Berechnungszeit normal?
Gibt es eine Möglichkeit (ausser schnelleren Qaurz) die 
Berechnungsgeschwindigkeit zu erhöhen?


Ich bin dankbar für jeden Vorschlag.

Gruß
Kabal

von Karl H. (kbuchegg)


Lesenswert?

Kabal wrote:

> Gibt es eine Möglichkeit (ausser schnelleren Qaurz) die
> Berechnungsgeschwindigkeit zu erhöhen?

Berechnung umstellen.
Division vermeiden, wenn möglich. Eventuell ist es möglich den Divisor 
auf eine 2-er Potenz zu bringen.

Aber das hängt alles vom konkreten Fall ab. Eine generelle Aussage ist 
fast unmöglich.

von H.Joachim S. (crazyhorse)


Lesenswert?

Grundsätzlich passt die Grössenordnung der Laufzeit.

von Mark B. (markbrandis)


Lesenswert?

Ich hab's ehrlich gesagt noch nie selbst ausprobiert, aber man könnte 
versuchen, eine Ganzzahldivision durch fortgesetzte Subtraktion zu 
ersetzen. Ob es wirklich schneller ist, vor allem wenn Divisor << 
Dividend, weiß ich nicht.

von ... (Gast)


Lesenswert?

@Mark Brandis

Das ist Quatsch. Die Softwareimplementierung einer Division funktioniert 
mit shiften und subtrahieren, so wie man schriftlich dividiert, nur im 
Binärsystem. Da bist du nur mit subtrahieren auf keinen Fall schneller.

von Kabal (Gast)


Lesenswert?

Danke für die Antworten.

Ich habs mit subtrahieren versucht, das dauerte länger. Leider kann ich 
die Divisionen nicht vermeiden.
An Karl heinz Buchegger:
Kannst du mir bitte ein Beispiel geben wie ich die Division machen muss, 
wenn der Divisor in eine 2-er Potenz umgeformt wurde?

Und hat jemand eine Ahnung welche Frequenz der Atmega128 maximal 
verarbeiten kann? Wahrscheinlich werd ich dann wohl einen schnelleren 
Quarz nehmen müssen.

Gruß
Kabal

von Karl H. (kbuchegg)


Lesenswert?

Kabal wrote:
> Danke für die Antworten.
>
> Ich habs mit subtrahieren versucht, das dauerte länger. Leider kann ich
> die Divisionen nicht vermeiden.
> An Karl heinz Buchegger:
> Kannst du mir bitte ein Beispiel geben wie ich die Division machen muss,
> wenn der Divisor in eine 2-er Potenz umgeformt wurde?

Wie gesagt, dass hängt alles vom Anwendungsfall ab.
Zb. benutzt man bei Festkommaarithmetik ein Vielfaches eines 
Basiseinheit. Anstatt also zb. in Euro zu rechnen, rechnet man in Cent. 
Alle Eingabebeträge (in Euro) werden mit 100 multipliziert um Cent zu 
erhalten. Um daher von Cent wieder auf Euro zu kommen, müsste man durch 
100 dividieren.
Division durch 100 ist langsam. Aber niemand sagt, dass man die 
eingegebenen Euros mal 100 nehmen muss. Mal 128 ginge genauso, und dann 
ist die Divison durch 128 ein Klacks.

Oder: Um den ADC zu 'entrauschen' nimmt man gerne einen Mittelwert her. 
Als dezimal denkender Mensch ist es naheliegend 10, 20, 40 oder 
meinetwegen 50 Messungen zu machen um den Mittelwert zu bilden. Für den 
Rechner sind das alles besch. Zahlen, 64 wäre viel besser, weil eine 
Div. durch 64 trivial ist.

etc., etc.

Welche Aufgabenstellung hast du? Wie und wo kommt da eine Division ins 
Spiel?

von Kabal (Gast)


Lesenswert?

Danke Karl-Heinz,

die Division mit der 2-er Potenz ist um ein vielfaches schneller. Ich 
hab noch festgestellt, dass die Division mit int32_t länger dauert als 
mit uint32_t. Kann das daran liegen, dass bei int32_t das Vorzeichen für 
die längere Berechnung sorgt?

Die Division kommt im Hauptprogramm vor. Ich muss alle 60mu s einen Wert 
abtasten und in der Zeit mehrere Berechnungen machen. Die Berechnungen 
konnte ich in eine 2-er Potenz umwandeln (danke nochmal für den Tipp).

Gruß
Kabal

von unsigned (Gast)


Lesenswert?

ja, natürlich benötigen Rechenoperationen mit Vorzeichen mehr 
Rechenzeit...

von Knut B. (Firma: TravelRec.) (travelrec) Benutzerseite


Lesenswert?

Der ATMega kann per Hardware fraktional multiplizieren. Vielleicht hilft 
Dir das weiter.

von Peter (Gast)


Lesenswert?

@Kabal (Gast)
kannst du etwas zu den Zahlenbreichen sagen für welche du die Division 
brauchst.

Können a1 und a2 nur in einem Bereich liegen?

von Simon K. (simon) Benutzerseite


Lesenswert?

Übrigens ist eine Division um 256 am einfachsten, im Idealfalle dauert 
die 0 Takte :-)

Divisionen kann man eigentlich sehr leicht vermeiden.

Beispiel:

Resultat: Multiplikation mit 85 (*ACHTUNG*: Hierbei entsteht ein 
Rundungsfehler, da nur mit INT gerechnet wird. Falls der Fehler zu groß 
wird, sollte man nicht mit 256 erweitern, sondern zum Beispiel mit 1024.
Division durch 256 kann durch einfaches weglassen des niedrigsten Bytes 
realisiert werden.

Fazit:
Mehrkosten: Multiplikation (Dank On Board Multipliziereinheit 
ertragbar), größeren Datentyp benötigt (sollte auch verkraftbar sein), 
kleine Rechenungenauigkeit (muss je nach Anwendungsfall angepasst 
werden).
Ersparnis: Division.

von Mark B. (markbrandis)


Lesenswert?

Simon K. wrote:
> Übrigens ist eine Division um 256 am einfachsten, im Idealfalle dauert
> die 0 Takte :-)

Aha, von einem 16-Bit Register nur die obere Hälfte nehmen?

von Simon K. (simon) Benutzerseite


Lesenswert?

Mark Brandis wrote:
> Simon K. wrote:
>> Übrigens ist eine Division um 256 am einfachsten, im Idealfalle dauert
>> die 0 Takte :-)
>
> Aha, von einem 16-Bit Register nur die obere Hälfte nehmen?

Genau, siehe oben, Beitrag ist editiert.

von Benedikt K. (benedikt)


Lesenswert?

Das setzt aber vorraus, dass die Zahl durch die geteilt wird konstant 
und zur Compilezeit bekannt ist.

Vor allem Fließkommazahlen kann man damit aber sehr leicht vermeiden wie
in diesem Beispiel: Zahl*1,23456 kann man näherungsweise durch 
Zahl*316/256 ersetzen. Vor allem in Inline Assembler ist das ganze sehr 
schnell, da man hier nur die Multiplikationen einbauen kann, die man für 
das Ergebnis auch wirklich benötigt und nicht auf 16 oder 32bit 
beschränkt ist, sondern jedes Vielfache von 8 verwenden kann.
Sowas ist ideal um z.B. den Wert einer krummen ADC Messung in Volt oder 
ähnliches umzurechnen.

von Kabal (Gast)


Lesenswert?

Danke für die Antworten.

An Travel Rec.: fraktional multiplizieren sagt mir nichts. Kannst du mir 
da ein wenig auf die Sprünge helfen?

An Peter: Der Zahlenbereich liegt bei 32 Bit Ganzzahlen.

An Simon K.: Die Umrechnung ist ein sehr guter Tipp, danke dafür, ich 
werde versuchen das in meinen Quellcode einzubauen.

Gruß
Kabal

von Peter (Gast)


Lesenswert?

@Kabal (Gast)
>Der Zahlenbereich liegt bei 32 Bit Ganzzahlen.

das ist schon klar, aber kann man z.b. sagen der der Divisor nur 
100-1000 sein kann, oder das das ergebniss immer zwischen 100 und 200 
liegt. Damit könnte man eventuell selber eine Division schrieben die 
genau den Bereich abdeckt dafür aber schneller ist.

von Gast (Gast)


Lesenswert?

Versuche einmal, die Berechnungen in float zu machen. Da dürfte es 
einfacher sein, die Division durch Multiplikation mit dem Kehrwert zu 
machen. Da nur 24Bit Mantisse gerechnet werden, kann gegenüber 32Bit-int 
durchaus schneller gerechnet werden (MUL-Befehle des Prozessors).

Probieren kostet nichts!

von Knut B. (Firma: TravelRec.) (travelrec) Benutzerseite


Lesenswert?

>fraktional multiplizieren sagt mir nichts. Kannst du mir
>da ein wenig auf die Sprünge helfen?

Befehle FMUL, FMULSU, FMULS

Eine fraktionale Multiplikation ist nichts weiter als eine Division mit 
festem Raster (pro Bit jeweils die Hälfte des nächsthöherwertigen Bits), 
nur daß diese per Hardware unterstützt und somit nur 2 Takte pro 
Operation braucht.

von oszi40 (Gast)


Lesenswert?

Interessant ist auch WO die Operanden liegen. Externe Daten brauchen 
länger.

von Benedikt K. (benedikt)


Lesenswert?

Kabal wrote:
> fraktional multiplizieren sagt mir nichts.

Das ist ein Festkommazahlenformat bei dem z.B. 32767 fast 1 entspricht 
und -32768 -1. Die restlichen Werte liegen dazwischen (oder allgemein: 
Wert/32768 beim 1.15 Format).
Im Prinzip kann man daher auch mit ganz normalen Zahlen (also int) 
rechnen, nur bei der Multiplikation 2er Werte ergibt sich dann ein 
Unterschied: 16384*16384 (also 0,5*0,5 in obiger Zahlendarstellung) 
ergibt 0,25. 16384*16384/65536 ergibt jedoch 4096, also 0,125. Das 
kompensiert der fmul Befehl.
Für C Anwendungen ist dieser Befehl jedoch uninteressant, da C dieses 
Zahlenformat nicht unterstützt, und ist höchstens für irgendwelche DSP 
Operationen die man in Assembler schreibt, brauchbar.

von Kabal (Gast)


Lesenswert?

Der Zahlenbereich liegt zwischen 320 und 320000 im Ergebnis. Der Worst 
Case für einen Teil der Berechnung liegt bei 4*10^7 / 125. Die 125 kann 
ich durch leichte Anpassung in eine 128 umwandeln. Dann wäre das ja auch 
schneller.
Die Überlegung mit den Floats werde ich mal ausprobieren.
Die Umrechnungsformel und der Tipp mit den 2er Potenzen als Divisor 
haben schon sehr viel gebracht. Damit kann ich mein Programm schon gut 
umsetzen.

Nochmals vielen Dank für die zahlreichen Antworten und Anregungen.

Gruß
Kabal

Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.