www.mikrocontroller.net

Forum: Mikrocontroller und Digitale Elektronik AVR Division Spezialfall: 0xXX00 / 0xXX (16/8 Bit)


Autor: Chris O. (lupin_iii)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ich habe einen Fall, bei dem ich eine 16-Bit Zahl durch eine 8-Bit Zahl 
dividieren will, wobei das low Byte der 16-Bit Zahl 0 ist. Ich habe mir 
die Routinen in der AVR200 Bibliothek angesehen, aber die einzig in 
Frage kommende wäre "div16u" (16/16 unsigned division). Nun kommt mir 
die aber etwas überdimensioniert vor, da ich ja ein spezielle 
Vorraussetzungen für die Zahlen habe. Lässt sich das irgendwie 
optimieren, sodass ich keine 200 Cycles für eine Division brauche?

Autor: Hegy (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Rechenoperationen wie malnehmen oder teilen brauchen immer viele 
Taktzyklen, es sei denn, du teilst durch 2^n, dann ist nach rechts 
schieben günstiger.

Autor: yalu (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Daraus, dass der Dividend mit 8 Nullen endet, kannst du wahrschienlich
keinen Nutzden ziehen. Somit suchst du nach einer gewöhnlichen
16/8-Division. Google liefert bspw. dieses:

  http://www.avr-asm-tutorial.net/avr_en/calc/DIV8E.html

habe aber keine Ahnung, ob das taugt.

Autor: Oh Mann (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
1. high Byte vom 16 Bit Wert nehmen (optimal: via Re-Define)
2. 8/8 Division machen
3. bei 0X0000 das high Byte durch das Ergebnis ersetzen (optimal: s.o.)

Grundlagen der Digitaltechnik I !

Autor: Morin (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> Grundlagen der Digitaltechnik I !

Schade dass du da nicht aufgepasst hast, denn deine "Lösung" rundet 
nicht auf ganze Zahlen sondern auf Vielfache von 256.

Beispiel: 256 / 16 = 16
Richtig: 0x0100 / 0x10 = 0x0010
Deine "Lösung" würde Berechnen: 0x0100 / 0x10 = 0x0000

Autor: Oh Mann (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Morin, häng Dich nicht soweit aus'm Fenster!
Vielleicht habe ich da grössere Kenntnisse und Erfahrung!
Überleg nochmal!
Tip: Du teilst in Deinem Beispiel durch dez. 16,
die Frage ging um einen 8-Bit Integer als Divisor!

Autor: Marcus (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo,

16 passt doch in einen u8.

Autor: Chris O. (lupin_iii)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Danke yalu. Die Version habe ich auch schon gefunden. Die braucht ca. 
210 statt 240 Takten. Also nicht wirklich viel weniger. Das Problem 
scheint wohl tatsächlich nicht weiter optimierbar zu sein. Ich bin jetzt 
noch beim überlegen, ob ich die "speed optimized version" von div16u aus 
der AVR200 Bibliothk nehmen soll, die 170 Takte braucht. Hat zwar eine 
Code Size von 196 Words, aber noch habe ich Platz im Speicher. Vielen 
Dank für die Antworten!

PS @Oh Mann: Auch Danke für den Versuch, aber ich glaube, in dem Fall 
hast du dich zu weit aus dem Fenster gelehnt ;-)

Autor: Morin (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> Morin, häng Dich nicht soweit aus'm Fenster!
> Vielleicht habe ich da grössere Kenntnisse und Erfahrung!
> Überleg nochmal!
> Tip: Du teilst in Deinem Beispiel durch dez. 16,
> die Frage ging um einen 8-Bit Integer als Divisor!

Vielleicht könntest du mal erklären inwiefern dez. 16 kein möglicher 
8-bit Divisor ist.

Oder, falls du dich weiterhin an der 16 aufhängen wilst, kann ich gerne 
das Beispiel 0x0100 / 0x02 bringen, also 256 / 2 = 128. Das richtige 
Ergebnis wäre also 128 = 0x0080. Nach deiner Methode berechnest du aber 
0x01 / 0x02, was 0.5 = 0x0.1 und nach dem Runden 0 = 0x00 ergibt, und 
nach dem Anhängen der Nullen 0x0000.

Autor: Morin (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Kleine Korrektur: das muss natürlich 0.5 = 0x0.8 heißen. Spielt aber 
hier keine Rolle; selbst wenn man deshalb auf- statt abrundet kommt was 
falsches raus.

Autor: Kai G. (runtimeterror)
Datum:
Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
Hab da mal was gebastelt. Das Makro braucht immer exakt 91 Zyklen für 
die von dir gewünschte Division und kommt ohne Zusatzregister, Stack, 
Ram, etc. aus. Sollte auf allen AVRs gleich laufen.

Bei Division durch 0 kommt immer 0xffff Rest 0x00 raus.

Sparen tut man durch deine Voraussetzung, dass Dividend-Low immer 0x00 
ist, gerade mal 8 Zyklen gegenüber einer "normalen" 16/8-Division. Na ja 
immerhin 8%.

Ach ja, ist alles unsigned, sollte aber kein Problem sein das 
anzupassen.

Der Code ist grob von mir getestet, kommentiert und für brauchbar 
befunden ;)

Keine Ahnung, was sich da noch optimieren lässt - ist nur'n 
Schnellschuss aus der Hüfte.

Vielleicht hilft's ja dem einen oder anderen.

Gruß

Kai

Autor: Kai G. (runtimeterror)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>sodass ich keine 200 Cycles für eine Division brauche?
Weiß einer, wie lange die AVR200-Routinen tatsächlich brauchen und wie 
die arbeiten? Mit kommt das so viel vor...

Autor: Chris O. (lupin_iii)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> Weiß einer, wie lange die AVR200-Routinen tatsächlich brauchen und wie
> die arbeiten? Mit kommt das so viel vor...

Jetzt nachdem ich atmel.com wieder erreichen kann (war vorher für ne 
Stunde tot), kann ich's dir genau sagen: 243 in der code size 
optimierten Version und 173 in der speed optimierten Version (steht in 
deren Doku). Dass das so viel ist, liegt vor allem daran, dass es sich 
um eine 16/16 Division handelt. 16/8 gibt's in deren Bibliothek nicht.

Der von dir erstellte Code macht zur Zeit jedenfalls das was er soll und 
das fast doppelt so schnell wie die 16/16 Version. Danke sehr! Ich 
glaube ich muss mir den Algorithmus mal aufzeichnen, so ganz blicke ich 
immer noch nicht durch, obwohl ich mir schon einige angesehen habe. Aber 
ich nehme mal an, dass die Einsparung von nur 8 Befehlen auf ein 
eingespartes rol pro Bit zurückzuführen ist.

Autor: Kai G. (runtimeterror)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Kein Problem.

>Aber
>ich nehme mal an, dass die Einsparung von nur 8 Befehlen auf ein
>eingespartes rol pro Bit zurückzuführen ist.

So ist es.

Wenn ich den Algorithmus kurz erklären soll, sag Bescheid - ist eine 
einfache schriftliche Division.

Ich kann ja mal schauen, wie schnell ich die 16/16-Version kriege, aber 
173 ist schon knackig schnell.

Schöne Grüße

Kai

Autor: Christoph Urbahn (krischimd)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo,
auf der Suche nach einer Divisionsroutine bin ich in diesem Thread 
gelandet und habe das Makro von Kai Giebeler ausprobiert. Kann es sein, 
dass die Routine nicht in jedem Fall dass richtige Ergebnis liefert!? 
Der AVR Simulator liefert mir z.B. bei Dividend = 0x0100 und Divisor = 
0xff das Ergebnis 0x00.

Soweit ich das erkennen kann, tritt das Problem auf, wenn der Divisor 
größer als 128 und das High Byte des Dividenden nicht gerade gleich dem 
Divisor ist. Denn dann kann es passieren, dass bei computeQuotientLowBit 
eine 1 im Remainder in das Carry geschoben wird (d.h. der Remainder ist 
eigentlich größer als 255 und damit auch größer als der Divisor) und bei 
der anschließenden Subtraktion nicht berücksichtigt wird.

Kann vielleicht jemand dazu Stellung nehmen? Ich befasse mich erst seit 
gestern mit der binären Division, deswegen fällt es mir noch ein 
bisschen schwer, solche Algorithmen zu überblicken...

Gruss,
Christoph

Autor: Kai G. (runtimeterror)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Was jetzt nur auf die Schnelle geschrieben... versuche mir das gleich 
mal anzusehen, wenn ich mit Bügeln durch bin :)

Hatte einige typische Extremwerte getestet - wenn da wirklich ein 
Problem vorliegt müsst's ein Programmierfahler sein, das Verfahren an 
sich sollte stimmen.

Autor: Michael G. (linuxgeek) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hegy wrote:
> Rechenoperationen wie malnehmen oder teilen brauchen immer viele
> Taktzyklen, es sei denn, du teilst durch 2^n, dann ist nach rechts
> schieben günstiger.

Potenzieren geht sehr schnell... modulares Potenzieren.

Autor: Kai G. (runtimeterror)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Mist... du hast Recht, der Divisor darf nicht das oberste Bit verwenden.

Ich schau mal, ob das einfach umzustellen ist. Wenn ich Glück habe muss 
nur das sub auf sbc abgeändert werden - befürchte aber, dass das nicht 
alles ist...

Autor: Christoph Urbahn (krischimd)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ich wollte damit in keinem Fall bewirken, dass du jetzt den restlichen 
Samstag damit verbringst, den Fehler zu beheben! ;)

Ein sbc allein wird es wohl nicht tun. Der Befehl ist ja zum 
Berücksichtigen eines Übertrages einer vorherigen Subtraktion da. D.h. 
im Falle eines gesetzten Carry würde nur eins mehr abgezogen werden.

Mir würde auf die Schnelle nur einfallen, ein zusätzliches 
Remainder-(High)-Byte zu nutzen. Das bedeutet dann aber ein weiteres 
rol, ein zusätzliches sbc nach dem sub und ein adc nach dem add...und 
schon ist es vorbei mit der schnellen Routine! Das ist also keine 
sinnvolle Lösung...

Autor: Kai G. (runtimeterror)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Das sbc ist mir nur auf die Schnelle eingefallen - funktioniert aus den 
von dir genannten Gründen natürlich nicht.

Ich komme ggf. mit einem bedingten Sprung nach dem Shiften aus - wenn 
das Carry danach gesetzt ist, kann der Divisor ja nur kleiner sein. 
Dadurch wird's leider wirklich langsamer und die Laufzeiz ist ggf. nicht 
mehr konstant (nicht tragisch, stört mich aber ;) )

>Ich wollte damit in keinem Fall bewirken, dass du jetzt den restlichen
>Samstag damit verbringst, den Fehler zu beheben! ;)

Wollte wenigstens schauen, ob's auf die Schnelle geht - sonst vergesse 
ich das :)

Danke auf jeden Fall für den Hinweis.

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.