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?
Rechenoperationen wie malnehmen oder teilen brauchen immer viele Taktzyklen, es sei denn, du teilst durch 2^n, dann ist nach rechts schieben günstiger.
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.
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 !
> 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
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!
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 ;-)
> 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.
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.
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
>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...
> 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.
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
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
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.
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.
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...
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...
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.
Thread beobachten
Seitenaufteilung abschaltenBitte 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.