langsame Division

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.

Grundsätzlich passt die Grössenordnung der Laufzeit.

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.

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?

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

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

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