mikrocontroller.net

Forum: Mikrocontroller und Digitale Elektronik Schnellere Division


Autor: Baum2 (Gast)
Datum:

Bewertung
-2 lesenswert
nicht lesenswert
Hallo

Ich programmiere einen ATmega mit Hilfe des AVR Studios.
Mich würde interessieren, welcher Rechenschritt auf dem µC schneller ist 
und warum.

20 / 5;

oder

20 >> 4;

Kann der µC mit den Schiebebefehlen schneller arbeiten? Und wie genau 
würde er die Division ausführen?
Gruß.

Autor: Peter II (Gast)
Datum:

Bewertung
2 lesenswert
nicht lesenswert
Baum2 schrieb:
> Mich würde interessieren, welcher Rechenschritt auf dem µC schneller ist

warum simulierst du es dann nicht einfach?


20 / 5;
20 >> 4;

Da kommt eh nicht das gleiche Raus, was willst du das vergleichen?

> Kann der µC mit den Schiebebefehlen schneller arbeiten?
meist ja, genauere steht im Datenblatt

Autor: Baum2 (Gast)
Datum:

Bewertung
-1 lesenswert
nicht lesenswert
Peter II schrieb:
> Baum2 schrieb:
> Mich würde interessieren, welcher Rechenschritt auf dem µC schneller ist
>
> warum simulierst du es dann nicht einfach?
>
> 20 / 5;
> 20 >> 4;
>
> Da kommt eh nicht das gleiche Raus, was willst du das vergleichen?

Es geht mir um die Rechenschritte die er benötigt.

Autor: Alex (Gast)
Datum:

Bewertung
1 lesenswert
nicht lesenswert
Schau doch im Prozessor-Handbuch, wieviel Cycles ein div braucht
und wieviel Cycles ein shift braucht.

Shift ist vermutl. schneller.

Autor: Mark Brandis (markbrandis)
Datum:

Bewertung
1 lesenswert
nicht lesenswert
Baum2 schrieb:
> Hallo
>
> Ich programmiere einen ATmega mit Hilfe des AVR Studios.
> Mich würde interessieren, welcher Rechenschritt auf dem µC schneller ist
> und warum.
>
> 20 / 5;
>
> oder
>
> 20 >> 4;
>
> Kann der µC mit den Schiebebefehlen schneller arbeiten? Und wie genau
> würde er die Division ausführen?
> Gruß.

Entscheidend ist, was der Compiler aus Deinem Code macht. Sehr 
wahrscheinlich wird er es so umsetzen, dass es keinen Vorteil bringt im 
Code einen Shift-Befehl hinzuschreiben anstatt einer Division.

Autor: Peter II (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Baum2 schrieb:
>> Da kommt eh nicht das gleiche Raus, was willst du das vergleichen?
> Es geht mir um die Rechenschritte die er benötigt.

die Rechenschritte sind ja abhängig von den Werten in der Formel.

Eine Division durch 1 geht z.b. sehr schnell.

Autor: Jörg Wunsch (dl8dtl) (Moderator) Benutzerseite
Datum:

Bewertung
2 lesenswert
nicht lesenswert
Peter II schrieb:
> Eine Division durch 1 geht z.b. sehr schnell.

… gefolgt von einer Division durch ganze Zweierpotenzen.

Konstante Divisionen taugen natürlich sowieso nicht für den Vergleich,
denn die werden vom Compiler rausoptimiert.  Divisionen durch konstante
Zweierpotenzen werden typisch ebenfalls ohne Bibliotheksaufruf durch
passende Schiebeoperationen bereits vom Compiler ersetzt.

Autor: Assem-Blär (Gast)
Datum:

Bewertung
3 lesenswert
nicht lesenswert
Baum2 schrieb:
> Es geht mir um die Rechenschritte die er benötigt.

Schreibe dir ein Mini-Programm das auf dem einen und
dem anderen Weg die gleiche Rechnung durchführt.
Compiliere es und schaue dir das vom Compiler erzeugte
*.lss file an. Dort kannst du auf Asssembler-Ebene
nachvollziehen was der Prozessor tun soll.

Allerdings solltest du die Optimierung ausschalten da
der Compiler eventuell für beide Rechenwege die
gleiche Methode wählt.

Autor: Jörg Wunsch (dl8dtl) (Moderator) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Assem-Blär schrieb:
> Allerdings solltest du die Optimierung ausschalten

Schlechter Ratschlag.

Dann kommt ja völlig praxisfremdes Zeugs raus.

„Wie schnell kann dieses Auto dort fahren?“

„Keine Ahnung, probier's aus, aber lass lieber die Handbremse
angezogen dabei.“

: Bearbeitet durch Moderator
Autor: Dirk_Geber (Gast)
Datum:

Bewertung
-1 lesenswert
nicht lesenswert
Ich würde halt gerne wissen, ob es im Bezug auf die Optimierung 
sinnvoller ist, nur durch Zweierpotenzen zu dividieren.

Autor: Peter II (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Dirk_Geber schrieb:
> Ich würde halt gerne wissen, ob es im Bezug auf die Optimierung
> sinnvoller ist, nur durch Zweierpotenzen zu dividieren

schaden tut es auf jeden Fall nicht. Damit es schneller ist, muss der 
Divisor aber zu Compilezeit konstant sein.

Autor: Mark Brandis (markbrandis)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Dirk_Geber schrieb:
> Ich würde halt gerne wissen, ob es im Bezug auf die Optimierung
> sinnvoller ist, nur durch Zweierpotenzen zu dividieren.

Zuerst einmal will man in aller Regel korrekte Ergebnisse haben. Also 
führt man eben die Berechnungen aus, die notwendig sind um das 
gewünschte Ergebnis zu bekommen.

Ich habe noch von keiner realen Anwendung gehört, in der man sich das 
korrekte Dividieren aus Performance-Gründen komplett verkneifen musste.

Autor: Arduino Fanboy (ufuf)
Datum:

Bewertung
4 lesenswert
nicht lesenswert
> wahsaga schrieb zu vergleichbarem mal:
"
Forenposting mit Performancefrage Bewertungsfaustregel:
Wer Fragen nach der Performance solcher Kinkerlitzchen stellt, der 
programmiert vermutlich noch nicht mal ansatzweise performant. 
Andernfalls, wenn er wirklich und zu Recht an einer Applikation arbeiten 
würde, bei der dieses Quentchen entscheidend ist, sollte er diese Frage 
gar nicht mehr stellen müssen.
"

Autor: Jörg Wunsch (dl8dtl) (Moderator) Benutzerseite
Datum:

Bewertung
1 lesenswert
nicht lesenswert
Peter II schrieb:
> Damit es schneller ist, muss der Divisor aber zu Compilezeit konstant
> sein.

Nein.  Auch zur Laufzeit ist eine Division durch 2^N immer noch
schneller als andere Divisionen.  Der Algorithmus ist dann schneller
fertig.  (Zur Compilezeit kann es nur der Compiler gleich optimieren.)

Da geht's den Computern wie den Menschen.  Ins Dezimalsystem
übertragen: wenn du 37568 durch 100 dividieren sollst, bist du mit
dem Ergebnis auch viel schneller fertig, als wenn du es durch 101
teilen sollst.

Autor: c-hater (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Mark B. schrieb:

> Zuerst einmal will man in aller Regel korrekte Ergebnisse haben.

Ja, absolut korrekte Ergebnisse und die dann noch instantan berechnet, 
das ist natürlich das Ideal.

Das Blöde ist halt nur: das geht nicht zu machen. Es wird immer eine 
gewisse Laufzeit erforderlich sein und oft werden auch gewisse 
Abweichungen vom absolut korrekten Ergebnis auftreten müssen.

Der Trick in der Numerik ist, einen geeigneten Kompromiss zwischen 
Korrektheit und Laufzeit zu finden. Blöderweise ist aber wiederum von 
der Anwendung abhängig, welcher Kompromiss geeignet ist.

Wer das nicht begriffen hat, hat vom Programmieren noch nicht viel 
verstanden.

Autor: Volker Bosch (Firma: L-E-A) (vobs)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Alex schrieb:
> Schau doch im Prozessor-Handbuch, wieviel Cycles ein div braucht
> und wieviel Cycles ein shift braucht.

Welche AVRs besitzen denn überhaupt einen Divisionsbefehl?

Grüßle,
Volker.

Autor: Arduino Fanboy (ufuf)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Volker B. schrieb:
> Welche AVRs besitzen denn überhaupt einen Divisionsbefehl?

Selbst ein BarrelShifter wird schmerzlich vermisst.

Autor: klick klack (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
c-hater schrieb:
> Ja, absolut korrekte Ergebnisse und die dann noch instantan berechnet,
> das ist natürlich das Ideal.

Ohne Laufzeit geht nur die wegoptimierte Division durch 1, aber warum 
sollte man da überhaupt dividieren, wenn es vorher bekannt ist. Alles 
andere hat was von Radio Eriwan...

Autor: chris (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Das Schieben ist schneller ABER eben nur zur entsprechenden Basis des 
Zahlensystemes. Bezogen auf binär heißt es du kannst nur durch 2 teilen 
auf die 10erBasis ist es eben nur /10. Somit ist die Aufgabe von dir die 
Dvision so abzubilden das du nicht nur durch die Basis des 
entsprechenden Zahlensystemes dividieren kannst sondern auch andere 
Teiler möglich sind. Dazu brauchst all den anderen Kram....

Autor: Draco (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Also wenn rechnen müsste:

uint8_t Wert = 20 / 5;


Dann mach ich doch gleich so:

uint8_t Wert = 4;



;-)

Ansonsten sehe ich das wie

Arduino F. schrieb:
>> wahsaga schrieb zu vergleichbarem mal:
> "
> Forenposting mit Performancefrage Bewertungsfaustregel:
> Wer Fragen nach der Performance solcher Kinkerlitzchen stellt, der
> programmiert vermutlich noch nicht mal ansatzweise performant.
> Andernfalls, wenn er wirklich und zu Recht an einer Applikation arbeiten
> würde, bei der dieses Quentchen entscheidend ist, sollte er diese Frage
> gar nicht mehr stellen müssen.
> "

Autor: Joachim B. (jar)
Datum:

Bewertung
-1 lesenswert
nicht lesenswert
Draco schrieb:
> Also wenn rechnen müsste:
>
> uint8_t Wert = 20 / 5;

das dürfte schon der Präprozessor machen und 4 einsetzen vermute ich 
mal.

Autor: Bernd K. (prof7bit)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Mark B. schrieb:
> Entscheidend ist, was der Compiler aus Deinem Code macht. Sehr
> wahrscheinlich wird er es so umsetzen, dass es keinen Vorteil bringt im
> Code einen Shift-Befehl hinzuschreiben anstatt einer Division.

Sag das mal dem Keil C51 Compiler.

Autor: Mark Brandis (markbrandis)
Datum:

Bewertung
1 lesenswert
nicht lesenswert
Bernd K. schrieb:
> Mark B. schrieb:
>> Entscheidend ist, was der Compiler aus Deinem Code macht. Sehr
>> wahrscheinlich wird er es so umsetzen, dass es keinen Vorteil bringt im
>> Code einen Shift-Befehl hinzuschreiben anstatt einer Division.
>
> Sag das mal dem Keil C51 Compiler.

Okay, also: Ein vernünftiger Compiler wird es so umsetzen, dass es 
keinen Vorteil bringt einen Shift-Befehl hinzuschreiben anstatt einer 
Division. ;-)

Autor: Jörg Wunsch (dl8dtl) (Moderator) Benutzerseite
Datum:

Bewertung
1 lesenswert
nicht lesenswert
Joachim B. schrieb:
> das dürfte schon der Präprozessor machen und 4 einsetzen vermute ich
> mal.

Präprozessor, Subst.:

Mystischer Teil eines C-Compilers, dessen Möglichkeiten weithin
gefühlsmäßig dramatisch überschätzt werden.  Der P. erledigt einfache
Textersetzungen, bevor der Quelltext einer Übersetzungseinheit zum
eigentlichen Compiler weitergereicht wird.

Autor: Spannungsteiler (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert

Autor: Jörg Wunsch (dl8dtl) (Moderator) Benutzerseite
Datum:

Bewertung
2 lesenswert
nicht lesenswert
Spannungsteiler schrieb:
> --->
> http://www.matuschek.net/avr-codeoptimierung2/

Mikrooptimierung.

Solche Hacks wird man sich nur antun, wenn's auf die paar Takte
wirklich ankommt.  Portiert man den ganzen Salat mal irgendwann
auf einen anderen Prozessor, dann kann einem solcherart
Optimierung ganz schnell auf die Füße fallen, weil sie sich dort
dann plötzlich als Pessimierung entpuppt, ganz davon abgesehen,
dass sie eine bestimmte Byteorder benötigt.

Bei ARM und GCC hat man übrigens Glück: der erkennt, dass all die
vielen Umständlichkeiten von "version2" letztlich zum gleichen
Code führen wie "version1", und schreibt in beiden Fällen den
passenden LSRS-Befehl (mit 22 Bit Schiebeweite) hin. ;-)

Autor: Joachim B. (jar)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Jörg W. schrieb:
> Mystischer Teil eines C-Compilers, dessen Möglichkeiten weithin
> gefühlsmäßig dramatisch überschätzt werden.  Der P. erledigt einfache
> Textersetzungen,

OK dann macht die Ersetzung 20/5 der Compiler, ich hoffe ich liege nicht 
ganz falsch das er gleich 4 in die Konstante einsetzt.

Autor: Jörg Wunsch (dl8dtl) (Moderator) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Joachim B. schrieb:
> OK dann macht die Ersetzung 20/5 der Compiler

So ist es.

Autor: Cyblord ---- (cyblord)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Jörg W. schrieb:
> Joachim B. schrieb:
>> das dürfte schon der Präprozessor machen und 4 einsetzen vermute ich
>> mal.
>
> Präprozessor, Subst.:
>
> Mystischer Teil eines C-Compilers, dessen Möglichkeiten weithin
> gefühlsmäßig dramatisch überschätzt werden.  Der P. erledigt einfache
> Textersetzungen, bevor der Quelltext einer Übersetzungseinheit zum
> eigentlichen Compiler weitergereicht wird.

Er kann aber rechnen, muss es sgoar, und zwar wenn es berechenbare Terme 
in #if Statements gibt.

Autor: Jörg Wunsch (dl8dtl) (Moderator) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Cyblord -. schrieb:
> Er kann aber rechnen

Hab' ich ja auch nicht bestritten.  Wird aber (abgesehen von einfachen
Booleschen Ausdrücken) nur selten benutzt, und insbesondere eben nur
dafür, um die Bedingung eines #if zu evaluieren.

Autor: Cyblord ---- (cyblord)
Datum:

Bewertung
1 lesenswert
nicht lesenswert
Jörg W. schrieb:
> Cyblord -. schrieb:
>> Er kann aber rechnen
>
> Hab' ich ja auch nicht bestritten.

Doch irgendwie schon. Dein Beitrag suggeriert er mache ausschließlich 
einfache Textersetzungen. Was rechnen dann doch ausschließt.

Autor: A. K. (prx)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Mark B. schrieb:
> Okay, also: Ein vernünftiger Compiler wird es so umsetzen, dass es
> keinen Vorteil bringt einen Shift-Befehl hinzuschreiben anstatt einer
> Division. ;-)

Wobei zu beachten wäre, dass
  int i = a;
  i %= 8;
und
  i >>= 3;
nicht äquivalent sind, weil auch bei Verwendung eines Schiebebefehls mit 
Vorzeichen bei negativen Werten unterschiedlich gerundet wird. Eine 
Divisionoperation, die durch Shift ersetzt wird, kann also komplizierter 
ausfallen als ein Shift allein. Und bei Optimierung auf Grösse kann die 
Division dann u.U. sparsamer ausfallen als dieser Ersatz.

: Bearbeitet durch User
Autor: Urban (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Es gab auf dem µCNet vor ein paar Jahren einen Thread mit einer 
schnellen Division, die in USA patentiert war. Der Thread stand 
vermutlich im Zusammenhang mit der Emulation des DIV-Befehls eines 8051 
auf einem AVR-Controller. Vielleicht weiß noch jemand welcher Thread das 
war.

Autor: Christopher B. (chrimbo) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
A. K. schrieb:
> Wobei zu beachten wäre, dass
>   int i = a;
>   i %= 8;
> und
>   i >>= 3;
> nicht äquivalent sind

sind sie doch niemals, oder? Außer für den Sonderfall dass a zwischen 8 
und 16 ist.

aber du meintest wohl /= statt %= ?

Autor: A. K. (prx)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Christopher B. schrieb:
> aber du meintest wohl /= statt %= ?

Ja. Oder "%=" und & statt Shift.

Autor: Joachim B. (jar)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Jörg W. schrieb:
> Der P. erledigt einfache
> Textersetzungen,
Cyblord -. schrieb:
> Er kann aber rechnen, muss es sgoar, und zwar wenn es berechenbare Terme
> in #if Statements gibt.
Cyblord -. schrieb:
> Dein Beitrag suggeriert er mache ausschließlich
> einfache Textersetzungen. Was rechnen dann doch ausschließt.

danke, wusste ich doch das der Prä rechnen kann, aber irgendeiner muss 
ja immer widersprechen!

: Bearbeitet durch User
Autor: Jörg Wunsch (dl8dtl) (Moderator) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Joachim B. schrieb:
> wusste ich doch das der Prä rechnen kann

Macht er schon, nur nicht da, wo viele Leute vermuten, dass er es
täte …
#define FOO 42
#define BAR 21

int gimmevalue(void)
{
#if FOO - BAR  // hier rechnet er
   return FOO - BAR;  // hier nicht, hier ersetzt er nur Text
#else
   return 42;
#endif
}

Autor: Detlef _A (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Zur Integer Division mit Konstanten gibts paar tricks:
http://www.hackersdelight.org/divcMore.pdf

Zur selbstprogrammierten Division von integern hatte ich hier mal was 
geschrieben.

Beitrag "Integer division, Reciprocal of an integer value, Kehrwert eines integers"

HTH
Cheers
Detlef

Autor: Urban (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hier ist das Patent, das ich gesucht habe (siehe oben):

https://www.google.com/patents/US7007058

Der Algorithmus steht etwas tiefer und beginnt mit:

#define uchar unsigned char

Der C-Quelltext selbst ist etwas putzig.

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]
  • [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.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

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