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
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.
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.
@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.
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
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?
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
Der ATMega kann per Hardware fraktional multiplizieren. Vielleicht hilft Dir das weiter.
@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?
Ü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.
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?
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.
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.
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
@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.
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!
>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.
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.
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
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.