Hallo Die Frage ist vielleicht ein bisschen komisch. Aber warum besitzt der AVR keinen Befehlssatz mit einer Divisionfunktion? Ich finde eigentlich dass gerade so einen Funktion sehr nützlich für einen AVR wäre. Es gibt ja sicher andere Befehle die nicht so wichtig sind. Liegt es daran dass es für einen RISC-Controller zu komplex ist eine Divisionsfunktion in einem oder paar wenigen Zyklen abzuarbeiten? Soviel ich weiss besitzen PICs(RISC) auch keinen Divisionsbefehl? Gruss Kapitän Blei
"Warum hat ein Cheesburger Käse und warum fehlt der am Hamburger?" RISC= Reduced Instruction Set. Sagt doch der Name. Wenn du alles hättest was du wolltest hättest du kein RISC mehr. Davon abgesehen geht Division u.v.m auch ganz einfach in Software. Nimm C und du musst nichtmal mehr wissen, wie's gemacht wird. Gruß Andreas
Mit RISC/CISC hat das wenig zu tun, sondern einfach damit dass ein Dividierer Platz wegnimmt, und man in einem Mikrocontroller eine echte Hardware-Division so selten braucht dass es einfach keinen Sinn macht dafür Platz zu verschwenden.
und wenn alle Stricke reissen, kann man immer noch anstatt einer Division mit dem Kehrwert multiplizieren.
Es geht auch nicht darum warum die Banane krumm ist. Obwohl PIC und AVR beide Risc sind, hat der AVR ja ein einiges grösseren Befehlsatz als der PIC. Also mit "Reduced_ Instruction Set" dürfte so was nicht so einfach zu erklären sein. Vor allem finde ich einen Divisionsbefehl im Vergleich mit anderen Befehlen die z.b. beim PIC fehlen doch recht wichtig. Die Division ist immerhin eine der 4 Grundoperationen der Mathematik
Nachtrag: <und wenn alle Stricke reissen, kann man immer noch anstatt einer Division mit dem Kehrwert multiplizieren.> Daran habe ich im Moment nicht gedacht. Aber für den Kehrwert brauche auch auch eine Division oder gibt es da einen anderen Trick?
> Die Division ist immerhin eine der 4 Grundoperationen der > Mathematik Schön, aber ein 8-bit uc soll meistens keine Mathe-Aufgaben lösen. Für viele Anwender wäre der Platz für eine Divisionseinheit verschwendet. Das macht nur die Chips teuerer.
> hat der AVR ja ein einiges grösseren Befehlsatz... Man muss aber auch beachten, dass viele AVR-Befehle eigentlich keine eigenen Befehle sind, sondern nur eigene Mnemonics für bestimmte Kombinationen anderer Befehle, was man schnell erkennt, wenn man sich die Opcodes bestimmter Befehle mal anschaut. Z.B. lassen sich alle Branch-Instruktionen, die sich auf Bits im SREG beziehen, von BRBC oder BRBS ableiten, nur dass die Operatoren bereits vorgegeben sind. Die Befehle zur Manipulation der Bits im SREG (sei, cli, set,...) sind alles Variationen von BSET bzw. BCLR. CBR ist ein ANDI des betreffenden Registers mit dem Komplement, CLR ist ein EOR des Registers mit sich selbst usw... Das nur als Auswahl, es gibt noch mehr Beispiele. Man sieht, dass der Befehlssatz dadurch erheblich zusammenschrumpft. Wie das beim PIC ist, weiß ich allerdings nicht.
> nur dass die Operatoren bereits vorgegeben sind...
Muss natürlich Operanden heißen und nicht Operatoren...
>>> <und wenn alle Stricke reissen, kann man immer noch >>> anstatt einer Division mit dem Kehrwert multiplizieren.> >>> Daran habe ich im Moment nicht gedacht. Aber für den Kehrwert brauche >>> auch auch eine Division oder gibt es da einen anderen Trick? Nein, es gibt keinen Trick, man braucht die Division. Wenn man durch eine Konstante dividieren möchte, dann kann man den Kehrwert bei der Programmentwicklung ausrechnen. Will man jedoch durch eine Variable teilen, deren Wert sich erst zur Laufzeit ergibt, dann nutzt der Kehrwert-Trick nichts. Warum es keinen Divisionsbefehl gibt wurde schon erklärt: es wäre eine aufwendige Hardware nötig. Diese ist für einen solchen Vielzweckcontroller beim heutigen Stand der Technik einfach nicht wichtig genug.
natürlich hätte ich am liebsten einen Fliesskommakoprozessor mit auf dem die integriert. wäre doch cool, aufm mega8 heftigst mit floats rumzutraktieren.
> Will man jedoch durch eine Variable teilen, deren Wert sich erst > zur Laufzeit ergibt, dann nutzt der Kehrwert-Trick nichts. Es sei denn, man will mehrere Werte durch diese Variable teilen. In diesem Fall kann man damit doch immerhin n Divisionen durch eine Division + n Multiplikationen ersetzen.
Das Hauptproblem ist, dass eine Division in einem Takt bei 20 MHz nur sehr schwer realisierbar ist. Wenn man mehrere Takte braucht, wird aber die Pipeline bei den RISC Prozessoren gesprengt und die ganze Ablaufsteuerung gerät ins trudeln. Bei einem CISC Prozessor (wie z. B. dem 8051) kann man sich bei der Division Zeit lassen, da dauert dann ein Division auch mal 48 Takte. Bei einem Risc geht das aber konzeptionell nicht. Aber man kann die Division ja von Hand aufdröseln. Ist ja nur eine Kombination von einem Haufen Shift und Compare befehlen. Dann braucht man auch nur 48 Takte :) Gruss Axel
wenn ich mich recht entsinne, ist eine Division nichts anderes als: int a, b, c; a = 123; b = 5; c = a * (~b); wobei der ~b ein inverses von b bildet - das ist 1/b. (wenn ich nicht ganz falsch liege...
1/b leider ist meistens nicht ganzzahlig darstellbar. Häufiger Ansatz ist hier, mit (1/b)*(2^n) zu multiplizieren und anschliessend die 2^n wieder rauszudividieren (shift). Leider landet man dabei gern bei der falschen Rundung (stört nicht immer, ist vermutlich korrigierbar).
Du liegst leider falsch. Wenns so einfach wäre... ~b bildet das Bitkomplement von b, d.h. es invertiert jedes einzelne Bit, was aber nichts mit einer Division zu tun hat!
Das 'Du liegst leider falsch' bezog sich natürlich auf Gernots Posting...
@Gernot ~b = -b - 1 Einerkomplement = Zweierkomplement - 1 Peter
Hmm... ich dachte wir hätten in der Schule mal eine Division zusammengesteckt. Aber das ist schon 10 Jahre her, und Elektronik hat mich damals 0 interessiert...
Ich habe mal irgendwo gelesen, dass wenn man eine Division in der Sprache C mit einem Integer macht, benötig dies 1000 Takte? Angeblich hat er ein einfaches Beispiel mit dem Simulator durchgespielt. Wenn es bis zu 1000 Takte braucht ist das iregendwie schon bedenklich ausser die Anwendung ist nicht Zeitkritisch.
Ist ja eigentlich ganz simpel. Angenommen, mann will 1001 durch 10 teilen. Also Beispiel: 1001:10 = 100 Rest 1 10 -- 000 00 --- 01 00 ---- 1 dabei wir das Ganze auf Schiebe und Vergleichsoperationen reduziert. Muss man jetzt nur in Software machen :) Gruss Axel
"wobei der ~b ein inverses von b bildet - das ist 1/b. (wenn ich nicht ganz falsch liege..." nicht ganz richtig, das ist das Reziprok. Das Inverse ist abhängig vom Kontext, zb. Boolsche Algebra ist es eine Negation, in modularen Ringen ist es das muliplikative Inverse, sowas ähnliches wie das Reziprok. Gruß Hagen
> Also mit "Reduced_ Instruction Set" dürfte so was nicht so einfach zu > erklären sein. Verständnisfrage zu RISC und CISC: Die Unterscheidung zwischen 'Reduced' und 'Complex' bezieht sich doch weniger auf die tatsächliche Anzahl bzw. die tatsächliche Komplexität der Befehle, sondern auf die Art- und Weise, wie diese vom Prozessor abgehandelt werden?
Korrekt und eine "Abhandlung" innerhalb dieser CPU ist die Art&Weise wie der Maschinenbefehl aus dem Speihcer geladen wird, danach dekodiert wird und anschließend abgearbeitet wird. Und bei einer RISC versucht man nun exakt diesen Prozess so schnell wie möglich zu gestalten, und das geht indem man alle Befehle so konstruiert das sie inetwa alle die gleiche Komplexität besitzen, ergo die gleich Zeit benötigen. Eine Division ist aber schon mathematisch gesehen sehr komplex und beötigt entweder sehr viele Taktzyklen (einfach weil sie dann iterativ abgearbeitet wird) oder aber sie benötigt fast mehr Silikon auf dem Die als der Rest der MCU. Das der AVR diese Operation nicht unterstützt ist kein Einzelfall. Es gibt viele RISCs bis hinauf in 32Bit Achitekturen die keine Division kennen. Einfach eine Kostenfrage. Und davon abgesehen gibt es mindestens 5 verschiedene Arten eine Divison durchzuführen, je nach Vorraussetzungen. Das Reziproke und die Multiplikation bieten sich an wenn man mit Konstanten dividiert oder aber N Dividionen durch 1 Division und N Multiplikationen ersetzt. Dann noch die "schnellen" Ersatzdisivionen wenn man seine Mathematik auf Binärsystem umstellen kann. Dann wird per Shifts dividiert. Dh. also auf einer RISC Machine wird diese Divison in einzelne Befehle zerlegt und das dann spezialisiert je nach Erfordernissen. Gruß Hagen
Der Unterschied liegt in der Abarbeitung der Befehle. Ein RISC Prozessor hat in der Regel eine Pipeline, in der die Befehle abgearbeitet werden. Dabei wird ein Befehl in drei Stufen unterteilt. Fetch, Decode und Execute. Es ist immer jeweils ein Befehl in der Fetch/Decode/Execute Stufe. Am Ende wird also ein Befehl in drei Takten abgearbeitet, aber jeder Takt ein Befehl abgeschlossen, wobei immer drei Befehle in der Pipeline sind. Ich habe das hier mal aufgezeichnet, die Befehle werden praktisch durch die Pipeline durchgeschoben. Pipeline Fetch Decode Execute Takt 1 Befehl1 Befehl0 Takt 2 Befehl2 Befehl1 Befehl0 Takt3 Befehl3 Befehl2 Befehl1 Der Vorteil ist, dass mit jedem Takt ein Befahl abgearbeiutet wird und durch die kompakten Befehle die Ausführungszeit in jeder Stufe der Pipeline sehr kurz ist, was die hohen Takte erlaubt. Das funktioniert natürlich nur mit Befehlen, die genau in dieses Schema zu pressen sind. Beim CISC haben die Befehle unterschiedliche Taktzahlen, lasen sich dadurch nicht in diese Pipeline pressen, es wird nur ein Befehl zur Zeit abgearbeitet, bis der fertig ist. Dann kann man auch mal 48 Takte für eine Division berücksichtigen. Beim Risc geht das aber nur schwer, weil die Division in einem Takt der Execute Einheit abgewickelt werden muss. Genauer gesagt, ist das natürlich durchaus möglich. Aber diese Division würde dann den maximalen Takt des Bausteines festlegen, ein ATMEGA8 würde dann wegen dieses Befehls nicht mit 8 MHz (entsprechend 125 ns pro Takt/Befehl) laufen, sondern vielleicht nur mit 5, weil der Div Befehl mindestens 200ns braucht. Gruss Axel
Feine Diskussion das :) Ich möchte dazu auch noch etwas beisteuern: Im Unterschied zur Multiplikation, bei der man mit einem kleinen Rechenwerk ohne weiteres auch größere Operanden verrechnen kann, müsste man bei der Division gleich den worst-case oder mehrere Rechenwerke nebeneinander implementieren. Mit anderen Worten: Bei der Multiplikation reicht der 8bit-mal-8bit-Hardwaremultiplizierer der AVRs, bei der Division müsste man aber z.B. gleich einen 32bit-durch-32bit-Monstrum auffahren, um wenigstens für die meisten Fälle gewappnet zu sein. Und da wir hier ja mit Ganzzahlen rechnen, wären dann auch gleich 8 Ergebnisregister zu reservieren, je vier für Quotient und Rest. Bei so viel Aufwand erscheint es mir fraglich, ob eine Hardwarelösung überhaupt noch gegen eine optimal programmierte Softwaredivision für z.B. 16bit durch 8bit anstinken kann. Gruß Johannes
Klingt alles sehr interessant. Gehe ich aber richtig in der Annahme dass gerade bei der Division mit einer Hochsprache wie C oder Basic diese eher ineffizient umgesetzt wird ?
Sorry, aber das ist ganz einfach falsch - die Unterscheidung RISC/CISC bezieht sich auf die Befehlssatzarchitektur (ISA), und hat nichts mit der Mikroarchitektur zu tun. IA32 (x86 Befehlssatz) ist ein CISC Befehlssatz, dennoch besitzt jeder x86 seit dem 486 eine Pipeline, und sehr viele Befehle kommen mit einem Befehl/Takt Durchsatz durch diese Pipeline. ARMv4t/ARMv5te ist ein RISC Befehlssatz, besitzt aber einige Befehle, die einen geringeren Durchsatz als einen Befehl/Takt haben, z.B. Multiplikationen, die bis zu 4 Takten brauchen können. Bei einem ARM7TDMI dauert auch jeder Load/Store zwei Takte (unabhängig von Wait-States etc.). Gruss, Dominic
> Gehe ich aber richtig in der Annahme dass gerade bei der Division mit > einer Hochsprache wie C oder Basic diese eher ineffizient umgesetzt > wird ? Hmm..ein guter Compiler sollte den Sourcecode doch in die je nach Situation besten Maschinenbefehle umsetzen, d.h. z.B. eine Division durch zwei direkt als Bit-Schieben umsetzen oder eine Division durch eine Konstante als Multiplikation mit (bereits vom Compiler berechneten) Reziprokwert. Nur wenn wirklich Variable1 / Variable2 geteilt wird, sollte eine echte Division ausgeführt werden. So könnte es zumindest sein, keine Ahnung wie dies in der Praxis aussieht.
wen's interresiert: einfache division (ohne nachkommastellen; sondern mit divisionsrest) auf dem avr mit asm:
1 | ;zahlen in die register laden |
2 | ldi r16, 11 ;dividend |
3 | ldi r17, 2 ;divisor |
4 | |
5 | div: ;division |
6 | ;überprüfen ob der dividend größer oder gleich als der divisor ist |
7 | ;wenn kleiner dann zu >shift< springen |
8 | cp r16, r17 |
9 | brlt rest |
10 | ;wenn größer dann r16 minus r17 ausführen und r18 um 1 erhöhen |
11 | sub r16, r17 |
12 | inc r18 |
13 | jmp div |
14 | |
15 | rest: |
16 | ;divisionsrest nach r19 schieben |
17 | mov r19, r16 |
18 | |
19 | ;nach der durchführung der division enthält r18 das ganzzahlige |
20 | ergebniss
|
21 | ;und r19 den rest, benötigt man nachkommastellen, so muss man r19 |
22 | linksschiben
|
23 | ;und weiterdividieren |
24 | |
25 | loop: ;endlosschleife |
26 | jmp loop |
PS: die endlosschleife am schluss hätte es net gebraucht, hab ich nur beim kopiren übersehen g
@Kapitän Blei Ja Du gehst richtig, aber ein ordentlicher Compiler hat eh eine Mathelib, die i.d.R. in asm geschrieben ist. Gruß Johannes
Per Atmel Application Note 200 gibt's allerlei handoptimierte Mul/Div Routinen fix und fertig.
Zur Effiuienze soviel.. Natürlich wird die Division in kleiner Rechenoperationen zerlegt. Geht ja auch nicht anders. Hier mal ein Beispiel, was der GCC mit abgeschalteter Optimierung erzeugt: in C: void main(void) { float zahl1 = 10.0; float zahl2 = 4.0; float zahl3 = 0.0; zahl3 = zahl1/zahl2; } erzeugter Assemblercode (Auszug): eine float Zahl benötigt 4 Register -> 32 bit LM2 - LM4 Zahlen in Register laden LM5 Berechnung main: .stabn 68,0,54,.LM1-main .LM1: /* prologue: frame size=12 */ ldi r28,lo8(__stack - 12) ldi r29,hi8(__stack - 12) out _SP_H_,r29 out _SP_L_,r28 /* prologue end (size=4) */ .stabn 68,0,56,.LM2-main .LM2: ldi r24,lo8(0x41200000) ldi r25,hi8(0x41200000) ldi r26,hlo8(0x41200000) ldi r27,hhi8(0x41200000) std Y+1,r24 std Y+2,r25 std Y+3,r26 std Y+4,r27 .stabn 68,0,57,.LM3-main .LM3: ldi r24,lo8(0x40800000) ldi r25,hi8(0x40800000) ldi r26,hlo8(0x40800000) ldi r27,hhi8(0x40800000) std Y+5,r24 std Y+6,r25 std Y+7,r26 std Y+8,r27 .stabn 68,0,58,.LM4-main .LM4: ldi r24,lo8(0x0) ldi r25,hi8(0x0) ldi r26,hlo8(0x0) ldi r27,hhi8(0x0) std Y+9,r24 std Y+10,r25 std Y+11,r26 std Y+12,r27 .stabn 68,0,60,.LM5-main .LM5: ldd r18,Y+5 ldd r19,Y+6 ldd r20,Y+7 ldd r21,Y+8 ldd r22,Y+1 ldd r23,Y+2 ldd r24,Y+3 ldd r25,Y+4 rcall __divsf3 movw r26,r24 movw r24,r22 std Y+9,r24 std Y+10,r25 std Y+11,r26 std Y+12,r27 .stabn 68,0,62,.LM6-main
Ring mit multiplikativem Inversem (a*a^-1=1): Körper z.B. die komplexen Zahlen Restklassenring: Z/nZ (Z mod n), die Einheitengruppe ist allerdings nicht immer vollständig (es gibt Elemente für die kein multipli. Inverses existiert). Wenn n prim ist, ist dies z.B. erfüllt und man hat wieder einen endlichen Körper. Zurück zum Thema: Angesprochen wurde schon Platzverbrauch und Takt (schlechtes Beispiel ist z.B. der Pentium4 mit 56-70(?) Taktzyklen für eine 32/32 Division). Wer sich für die eigentlichen Algorithmen interessiert, kann z.B. hier einsteigen: http://www.informatik.uni-ulm.de/ni/Lehre/WS02/CA/ArithIntegerE.PDF Ein Beispiel wie man soetwas optimiert: http://arith17.polito.it/final/paper-113.pdf > Genauer gesagt, ist das natürlich durchaus möglich. Aber diese > Division würde dann den maximalen Takt des Bausteines festlegen Nein, es kommt u.U. (nur) zu einem Stall in der Pipeline d.h. die Verarbeitung der folgenden Befehle wird angehalten bis die Division fertig ist. Sind mehrere ALUs vorhanden, könnten diese u.U. weiterlaufen. > So könnte es zumindest sein, keine Ahnung wie dies in der Praxis > aussieht. Gute Compiler machen das auch (Stichwort: Peephole-Optimizer) p.s. eigentlich sollte auch der Thread in mehrere kleinere aufgeteilt werden: Compilertheorie, math. Grundlagen, Integer-Divisions-Algorithmen etc.
Andererseits ist so ein Thread sehr schön um zu zeigen wie eines das andere ergibt ;) Gruß Hagen
Interessant ist, dass viele Motorola-µC (z.B. 68HC908) mul8->16 in 5 und div16->8 in 7 Takten können. Sind allerdings CISC. Aber es geht. Und verwende ich auch oft (z.B. Umwandlung hex -> dez).
"IA32 (x86 Befehlssatz) ist ein CISC Befehlssatz, dennoch besitzt jeder x86 seit dem 486 eine Pipeline, und sehr viele Befehle kommen mit einem Befehl/Takt Durchsatz durch diese Pipeline." Der 486 und folgende setzen die CISC Befehle aber meines Wissens intern in RISC Befehle (Microcode) um, die dann in der Pipeline abgearbeitet werden. "ARMv4t/ARMv5te ist ein RISC Befehlssatz, besitzt aber einige Befehle, die einen geringeren Durchsatz als einen Befehl/Takt haben, z.B. Multiplikationen, die bis zu 4 Takten brauchen können. Bei einem ARM7TDMI dauert auch jeder Load/Store zwei Takte (unabhängig von Wait-States etc.)." Auch jeder Sprungbefehl fällt in die Kategorie, das ist aber total besch... zu implementieren, reisst jedesmal den ganzen Programmablauf auseinander und bringt die Performance in die Knie. Deswegen haben RISC Prozessoren auch meist relativ grosse Registerbänke, um gerade Load/Store Befehle zu vermeiden. Formal ist die Definition schon so, wie Du das dargestellt hast, die Vorteile eines RISC Befehlssatzes ergeben sich aber vor allem aus der damit möglichen Pipeline-Architektur, die sehr schnell getaktet werden kann. Gruss Axel
> oder aber sie benötigt fast mehr Silikon
Zu viel Silikon sieht meistens ziemlich beschissen aus und greift sich
schlecht...
Multiplikation per Hardware zu beschleunigen ist überhaupt kein Problem. Der Algorithmus ist ziemlich parallel und genau so sieht dann auch die Hardware aus. 5 Takte sind da eher auf der langsamen Seite. Die 8-bitter mit 7 Takten für eine Division, das ist hingegen bemerkenswert. Denn die Algorithmen für die Division sind ziemlich sequentiell. Eem kann man allerdings etwas auf die Sprünge helfen, indem man 2 Bits auf einmal rechnet und mit Tabellen nachhilft (genau da lag übrigens der Divisionsfehler vom Pentium). Wundet sich wer, warum ausgerechnet 8051 und 6808 dividieren können, AVR, Z8, MSP430 jedoch nicht? Z8 und MSP430 sind übrigens CISC. Divisions-Algorithmen benötigen vor allem hinreichend viele Register und mindestens 2-Adress-Operationen. Hat man nur einen Akku zum Rechnen zur Verfügung (1-Adress-Operation), wird eine Divisionsroutine von unproduktiven Transportbefehlen dominiert. Und daher tun sich 6808 und 8051 mit einer Software-Division sehr viel schwerer als die register-orientierten AVR, Z8 oder MSP430. Man könnte auch bei letzteren Architekturen die Division per Hardware erheblich beschleunigen. Die erwähnte 2-Bit-pro-Iteration Methode ist per Software nicht hinzubekommen. Nur sind Divisionen viel seltener als Multiplikationen. Bei Microcontrollern ist der Bedarf nicht in dem Ausmass vorhanden, der Preisdruck aber hoch, also geht man einen Kompromiss ein und lässt das zulasten einer etwas langsameren Software-Implementierung weg.
Mit meinem Verständnis und Wissen kratze ich gerade ein bisschen an der Oberfläche eurer Beiträge herum. Das Thema ist aber höchst interessant! -> Könnt ihr vielleicht ein gutes Buch oder eine gute Webseite empfehlen, um sich mal grundsätzlich in diese ganze Prozessortechnik ein bisschen einzuarbeiten?
"der aber sie benötigt fast mehr _Silikon_ auf dem Die" Ja bescheuerter Tippfehler, meinte natürlich Silizium. Man sollte halt nicht während ein Kunde am Telefon palavert ein Posting verfassen :) Gruß Hagen
Ich seh da kein großes Problem, die Division in Hardware zu gestallten. Auch wenn hier Argumente kommen, die besagen, dass eine Division aufgrund der Taktmenge das Architekturkonzept versaut, kann ich nur sagen, dass z.B. Grafikkarten ganze 4D-Vektor-Divisionen (4mal 32-Bit Gleitkomma)in einem Takt hinbekommen. Selbst das normieren eines Vektors ist nur einen Takt lang. Und hierbei wird 4x multipliziert, 4x addiert, 1x Wurzel und 4x dividiert. Das Ergebnis muss am Ende des Taktes vorliegen, jedoch können Transitoren bekanntlich schneller als 20MHz oder 500MHz schwingen... somit wäre es möglich hardwareteschnisch implementierte Rechenketten zu bauen die Innerhelb eines Taktes viele Operationen ausführen.. wo ist das Problem? Geld? Bei der Massenproduktion? ISt doch nur eine Designfrage, oder? MFG
> Das Ergebnis muss am Ende des Taktes vorliegen, jedoch können > Transitoren bekanntlich schneller als 20MHz oder 500MHz schwingen... Dann allerdings nur mit einem Prozessor-Grundtakt von ebendiesen 20 oder 500 MHZ. Das heisst wiederum, man muss das ganze Design an diese enormen Taktraten anpassen. Und dann kann man schliesslich geradesogut den gesamten Chip mit dieser Geschwindigkeit laufen lassen. Einzige Möglichkeit ist Parallelität, und die braucht halt Platz, Strom, Silizium, Geld... Grafikchips sind eine völlige andere Liga von Chips, insbesondere was Preis und Stromverbrauch angeht. Es sagt ja auch niemand, dass es nicht möglich wäre - aber es macht keinen Sinn.
Ähm, sorry, Leute, aber irgendwie klingen die letzten Posts alle, als ob Ihr noch nie was vom AVR32 gehört habt. Gruß Johannes
Hier ist nur die Rede von AVR-Mikrocontrollern. Der AVR32 ist ne komplett neue Produktreihe und ein DSP bzw. MCU. Oder wolltest du auf was anderes hinaus? Dann entschuldige ich mich hiermit schonmal ;) MfG
Dennis, Du brauchst Dich nicht zu entschuldigen. Ich wollte just genau darauf hinaus, dass wir hier eigentlich über AVRs reden. Und nicht über 500MHz-Teile, Z8er, MPS430er oder Grafik-CPUs. Danke für Deine Unterstützung. Johannes
Und noch zweierlei: @William Ganz ab davon, dass es ursprünglich um Int- und nicht um Float-Division ging - den eigentlich interessanten Code hat Dein Listing verschwiegen, nämlich den von __divsf3. @Benjamin S. Als 16bit-durch-8bit, 16bit-durch-16bit oder gar 32bit-durch-irgendwas kommt das bestimmt nicht mehr so einfach ;) Nichts für ungut, aber ich hab über meine AVR-Jahre so um die zwanzig verschiedene zeit-optimierte Divisionen in Assembler verfasst, je nach Operandengröße. In einigen Fällen sogar als plumpe Subtraktionsschleifen, weil es damit am schnellsten ging. Gruß Johannes
"dass z.B. Grafikkarten ganze 4D-Vektor-Divisionen (4mal 32-Bit Gleitkomma)in einem Takt hinbekommen." Durchsatz ist nicht gleich Rechenzeit. Es mag sein dass diese Grafikkarten pro Takt eine Division durchführen können, indem sie die Schritte pipelinen, aber bis aus den Operanden ein Ergebnis wird, dürfte es immer noch einige Takte dauern. Ebenso Wurzel. Nur multiplizieren lässt sich gut runterdrücken.
"Das Ergebnis muss am Ende des Taktes vorliegen, jedoch können Transitoren bekanntlich schneller als 20MHz oder 500MHz schwingen... somit wäre es möglich hardwareteschnisch implementierte Rechenketten zu bauen die Innerhelb eines Taktes viele Operationen ausführen.. wo ist das Problem? Geld? Bei der Massenproduktion? ISt doch nur eine Designfrage, oder?" Ist eine Frage der Technologie. Eine 90nm oder gar 65nm Chip-Technologie, wie sie bei modernen Grafikkarten oder Prozessoren verwendet wird, ermöglicht natürlich extrem hohe Taktraten auch bei sehr komplexen Operationen. Leider haben diese Technologien extrem hohe Leckströme, ausserdem würde der AVR dann ein mehrfaches kosten. Und wer will schon einen AVR mit 1A standby-strom (ok, etwas übertrieben). Und 5V I/O würden auch nicht gehen. Man muss dann eben abwägen was man will und irgendwo Kompromisse eingehen. Wer eine Division in wenigen Takten will, muss dann eben auf einen ARM ausweichen, aber der hat dann u. U. zwei Versorgungsspannungen, verbraucht auch etwas mehr als nur ein paar mA und 5V I/O hat der auch nicht mehr. Gruss Axel
@Profi: Wo brauche ich bei der hex->dez Umwandlung eine Division? Das ist ja zum Schreien ineffektiv. Ich mache das ohne.
Zeig doch mal. Klar gehts auch ohne div. Aber wenn ich einen schnellen Hardware-Div (und Hardware mod) habe, dürfte das der schnellste Weg sein. Aber ich kenn auch nicht alle Assembler-Tricks. Also: Zeig mal, wie du das machst.
Eine 8:8-Bit Division in 58 Takten und 16:16 in 173 finde ich für einen 8bit Microcontroller akzeptabel. Kommt m.E. nicht oft vor, dass man das an zeitkritischer Stelle benötigt, als Grafik- oder DSP-Rechenknecht ist ja nicht gedacht.
@A.K. "Eine 8:8-Bit Division in 58 Takten und 16:16 in 173 finde ich für einen 8bit Microcontroller akzeptabel. Kommt m.E. nicht oft vor, dass man das an zeitkritischer Stelle benötigt, als Grafik- oder DSP-Rechenknecht ist ja nicht gedacht." Vielleicht hab ich bisher immer die falschen Sachen programmiert, aber wenn meine µC dividieren sollen, dann hab ich was dagegen, daß sie sich 'stundenlang' damit beschäftigen. Schließlich muß die Zeit, die für die Division benötigt wird, wo anders wieder hereingeholt oder durch einen höheren Takt ausgeglichen werden. Ein Standard 8051 benötigt 48 Quarzzyklen für eine 8:8 und ein C8051F120 macht das Ganze in 8 Zyklen (80ns bei 100MHz). Sind aber, so wie sich manche Mitglieder des Forums ausdrücken, 'veraltete' 8051-Kerne und deshalb wahrscheinlich nicht so beliebt ;-) Gruß Michael
Hast du schon mal konkret ein Problem damit gehabt, oder ist das eher eine allgmeine Befürchtung? Microcontroller sind dazu da, genau definierte Probleme zu lösen. Multiplikation und Division in Hardware machen die CPU komplizierter, somit teurer in der Herstellung, daher sind diese Funktionen nicht immer anzutreffen. Man suche sich den zum Problem passenden Controller aus. Wenn man sehr häufig dividiert, wird ein AVR ungeeignet sein. Wird evtl. auch ein ARM ungeeignet sein, der kann's nämlich auch nicht.
Kleiner Scherz am Rande: Im Gegensatz zur 68000 besass die Z8000-CPU eigene Befehle für 32-bittige Multiplikation und Division. Wer etwas Ahnung von der Sache hatte, hat diese Befehle jedoch für die C-üblichen "long" Rechnungen in den meisten Fällen nicht verwendet. Grund: Im Verhältnis zu den 16-bit Pendants waren die so schauderhaft langsam (>>700 Takte für die Division), dass der Ersatz durch geschickt genutzte 16-bittige Multiplikationen/Divisionen deutlich schneller war, und vor allem die Interrupt-Latenz nicht so gnadenlos in die Länge zog. Vor allem die Sache mit der Interrupt-Latenz... Eine 16bit Division wäre bei Controllern schon manchmal nützlich. Allerdings würde eine eher einfach gehaltene Implementierung die maximale Interrupt-Latenz derart vergrössern, dass der Controller dadurch an Nutzwert möglicherweise nicht gewinnt sondern verliert.
Die AT89LP Serie von Atmel(8051er) benötigt bei 20MHz Tackt 4 Oszillatorschwingungen fuer eine 8bit Division. Das mach also 200ns pro Division. Ein standard 8051er teilt den Takt davor nochmal durch 12 bzw. durch 6 bei neueren Chips. Dabei spielen diese Chips problemlos in den Preisliegen von AVRs. Gruss Tobias
> Vielleicht hab ich bisher immer die falschen Sachen programmiert, > aber wenn meine µC dividieren sollen, dann hab ich was dagegen, > daß sie sich 'stundenlang' damit beschäftigen. Na ja. Übertreib mal nicht masslos. Ein Z80 konnte auch nicht hardwaremaessig dividieren. Trotzdem konnte man damit tolle Sachen machen. Auf meinem 2-Mhz Z80 hatte ich ein Turbo Pascal laufen, das legte ein derartiges Tempo vor, da schleckts du dir mit deinem heutigen 2 Ghz Rechner die Finger danach ab. Der komplette Compiler, Editor, Runtime System samt zu entwickelndem Programm hatte alles in 64 Kbyte Platz. Was Windows mit seinem Speicher macht, möchte ich lieber nicht wissen.
Na gut. Dann ist der µC halt nich stundenlang, sondern µs lang beschäftigt. ;-) Das schnellste, was ich bis jetzt zu tun hatte, waren mit einem µC Daten analysieren und verarbeiten, die mit 1MHz ankamen. d.H. bei dem C8051F120 maximal 100 Maschinenzyklen für die Verarbeitung. Und da macht es sich schon bezahlt, wenn in 80ns die Division abgeschlossen ist. Die fehlende Division vom AVR hat mir noch keine Probleme gemacht, da ich bisher noch nicht so tief in die Programmierung eingestiegen bin. Bis jetzt hab ich einen Atmega16 nur dazu benutzt, um beim STK500 ein paar LEDs blinken zu lassen. Gruß Michael
Die ursprüngliche RISC-Philsophie, basierend auf Erkenntnissen der 70er und 80er Jahre: - Mach häufige Operationen schnell. - Mach seltene Operation möglich aber nicht unbedingt schnell. Kann heissen: durch Software ersetzen. - Lass alle brillianten Ideen weg, die kein Schwein benutzt. Eine Spezialität beispielsweise von VAX oder 68020. - Lass alles weg, was in Software schneller sind als in Hardware. Auch davon hatte die VAX so manches, aber beispielsweise auch die Z80 (LDIR). Wer sich über fehlende Divisionsbefehle beschwert, zeige mir bitte mal Microcontroller-Anwendungen in denen die hinreichend häufig vorkommen.
@Nobody: Bin jetzt zu bequem, das in 6808-Asm umzusetzen: unsigned i,x=55331; void main(void){ printf("\n"); for(i=5;i--;){ printf("%u",x%10); x/=10; } } die beiden Operationen %10 und /10 werden durch einen DIV erledigt, da danach im Accu das Ergebnis und im H-Register der Rest steht. Die Reihenfolge muss bei der Ausgabe reversiert werden! Oder bist Du der Meinung, die Subtraktionsmethode sei effektiver?
Auf einem AVR ja. Das liegt aber an der Umsetzung dieser Divisionen durch den Compiler. Durch deine Schleife wird quasi eine Zahl wie 12345 immer mit 10 dividiert, also von Rechts gesehen reduziert und das erfolgt intern iterativ mit Subtraktionen und Shifts. Mancht man das von Hand durch spezialisierte Subtraktionen so beginnt man 1 * 10000 zu subtrahieren, dann 2 1000 dann 3 100 4 * 10 und fertig. Macht summa sumarum also 10 Subtraktionen, fertig. Dieser Algo arbeitet aber von Links aus gesehen. Also vom MSB zum LSB und nicht wie deiner vom LSB zum MSB. Gruß Hagen
lol Im Prinzip geb ich dir Recht Hagen. Der Fairness halber muss man aber sagen (und das hast du auch, ich möchte es nur noch stärker herausstreichen): Das liegt aber mehr in diesem speziellen Beispiel als an irgend etwas anderem. Die Schleife ist so konstruiert, dass man hier mit fortlaufenden Subtraktionen zum Ziel kommt. Das muss aber nicht so sein. Alles in allem ein schönes Beispiel, dass man mit Nachdenken die Laufzeit drastisch drücken kann. Nicht umsonst heist die erste Grundregel in der Optimierung: Tu's nicht. Wenn du's aber tust, dann fang auf algorithmischer Ebene an. Ein vereinfachter Algorithmus bringt mehr als alle Low Level Bit-Pfriemeleien zusammen.
Naja es gibt immer noch Potential. Bei 98765 würde man 50000 subtrahieren, dann 30000 subtrahieren, dann 20000 und hätte erstmal -18765 errechent. Man weis also schon das '9' die führende Zahl ist. Wir benötigen also max. 4 Subtraktionen/Addition pro Stelle statt 9 im Worstcase. Gruß Hagen
Ach so, und bei 59999 brauche ich dann 32 Subtraktionen (und Increments und Jumps). Da bleibe ich lieber bei meinen 4 Divisionen (ich sprach ja vom 6808). Nobody fragte um 09:40 "Wo brauche ich bei der hex->dez Umwandlung eine Division? Das ist ja zum Schreien ineffektiv. Ich mache das ohne."
Hallo Jetzt mal die scheue Frage zwischendurch: Wäre es möglich, eine Division in einem Takt durchzuführen? Wäre es möglich, mit annähernd der bestehenden Hardware eines AVRs eine Hardware-Division in wenigen Takten durchzuführen? Wäre es möglich, gewisse Untereinheiten der CPU mit einem höheren als dem Quarztakt laufen zu lassen und so gewisse, eigentlich mehrtaktige Operationen, in einem Systemtakt laufen zu lassen? Gruss Michael
Ich kenne keinen mathematischen Algorithmus der eine Division ohne Iterationen durchführen kann. Das ist bei Multiplikation durchaus mathematisch machbar. Anderersseits weis ich das zb. Arnold Schönhage (ein deutscher Mathematiker) bewiesen hat das eine Division in jedem Falle in der rechnerischen Komplexität auf minimal 2 Multiplikationen reduzierbar ist. Dh. man kann nicht schneller dividieren als 2 Multiplikationen. Wenn man als für eine Mul 1 Takt benötigt dann benötigt eine Div immer doppel soviel. Eine Quadrierung einer Zahl ist zb. immer 1.5 mal schneller als eine Multiplikation durchführbar. Wobei wir vorsichtig sein müssen wenn wir von Divisionen/ Multiplikationen usw. reden, ich beziehe mich hier immer auf natürliche Ganzzahlen. Denn eine Divsion in zb. Galois Feldern (was man zb. bei CRCs benötigt) ist dort identisch schnell wie eine Multiplikation. Ein Grund warum man die Kryptographischen Algorithmen auf SmartCard Prozessoren vorzugsweise in GF(m^n) durchführt. Gruß Hagen
In der Praxis haben man es natürlich auch nicht mit der Menge ganzer Zahlen zu tun, sondern mit einer endlichen Teilmenge davon. Und dann sind Theoreme wie das genannte nicht anwendbar. Es ist z.B. eine Division mit Tabellen denkbar, was bei 8bit-Zahlen durchaus im Bereich des Machbaren liegt. Mit einer internen 64kB grossen Tabelle wäre es also möglich, eine 8-bit-Division in einem Takt abzuarbeiten. Ob es SINNVOLL ist, ist eine ganz andere Frage...
Hex besser gesagt, binär nach dezimal, läßt sich auch sehr schön mit BCD-Arithmetik lösen beim MSP430 würde das z.B. so aussehen: // Vorzeichenbehandlung und BCD nach ASCII sind weggelassen // in r4 short2bcd: clr r5 clr r6 mov #16, r7 loop: rla r4 dadd r5, r5 dadd r6, r6 dec r7 jnz loop
@Daniel: deshalb die Betonung auf "mathematischen Algorithmus". Das was du per Lookups machen willst ist ein technischer Trick. Man muß wirklich stark differenzieren und ganz genau definieren in welcher "Umwelt" man sich bewegt. Gruß Hagen
> Ich kenne keinen mathematischen Algorithmus der eine Division ohne > Iterationen durchführen kann. Das ist bei Multiplikation durchaus > mathematisch machbar. Anderersseits weis ich das zb. Arnold Schönhage > (ein deutscher Mathematiker) bewiesen hat das eine Division in jedem > Falle in der rechnerischen Komplexität auf minimal 2 Multiplikationen > reduzierbar ist. Dh. man kann nicht schneller dividieren als 2 > Multiplikationen. Das zweite Paper gelesen? http://arith17.polito.it/final/paper-113.pdf
@Hagen: Also "mathematisch" finde ich dann als Definition aber auch etwas schwach. Lookups sind auch kein "Trick", sondern einfach eine andere Form einer Funktionsdefinition - also durchaus "mathematisch". Das Problem vieler Theoreme ist halt, dass mit unendlichen Mengen gearbeitet wird, die in der Praxis auf einem Computer nie auftreten können. Das ist an sich erstmal kein Problem für sich, sondern das Problem besteht darin, dass diese Sachen einfach auf endliche Mengen übertragen werden. Oftmals kann man die Endlichkeit zwar vernachlässigen, aber gerade wenn man sich mit 8 oder 16 Bit rumschlägt, dann sind die Mengen doch oft so klein, dass man Theoreme über unendliche Mengen zwar anwenden kann, diese aber praktisch in vielen Fällen keine Relevanz haben, weil es Algorithmen gibt, die mit unendlichen Mengen nicht funktionieren.
> Mit einer internen 64kB grossen Tabelle wäre es also möglich, eine > 8-bit-Division in einem Takt abzuarbeiten. Oder in einer 256 Bytes grossen Tabelle den Kehrwert heraussuchen und damit multiplizieren, wäre langsamer, aber speicherschonender. Auf jeden Fall durchaus praxistauglich. Einzig das Problem, dass man beim Kehrwert das Komma etwas gleiten lassen müsste, besteht noch. Wie löst man sowas in der Praxis? Den Kehrwert um 8 Bit nach links Schieben und dann nur das obere Byte des Resultats der Mulitplikation beachten?
@Arc: " Das zweite Paper gelesen? http://arith17.polito.it/final/paper-113.pdf" Ja und ? Wir sollten strikt trennen zwischen der mathematischen Komplexität einer Operation und einer technischen Realisierung und deren Komplexität in zb Hardware. Das was ich aus diesem Paper raus lesen konnte ist das der vorgeschlagende Algo. immernoch um mehrfaches höhere Komplexität besitzt als eine Multiplikation. Auch wenn der Weg über die Signed Digit Repräsentation wirklich interessant ist. Mit dieser Form der Zahlendarstellung hatte ich bisher nur in der Exponentation in GF(p) also Elliptischen Kurven zu tuen gehabt. A. Schönhage bezieht sich ganz einfach auf die Fragestellung wie schnell oder besser gesagt wie aufwendig eine Divison im Vergleich zu einer Multiplikation ist. Und diese Frage hat er per mathematischen Beweis beantwortet. Einfach mal hier auf Suche gehen http://www.informatik.uni-bonn.de/~schoe/publis.html. Gruß Hagen
@Daniel: da gebe ich dir vollkommen Recht. Ein Mathematiker denkt immer infinitiv und der Ingenieur infinmal. Für den Mathefreak ist alles unendlich und für den Ingenieur hat alles Grenzen ;) Meine Aussage ansich war ja auch eher eine vielleicht interessante Information aus einem meiner Tätigkeitsbereiche der Sofwtareentwicklung einer Library zur Berechnung supergroßer Zahlen. Das sowas natürlich ein Spezialgebiet ist und wir hier über ein anderes Spezialgebiet diskutieren ist logisch, heist aber denoch nicht das es keine Parallitäten gäbe (zumindestens nicht nach meiner Sicht ;) Gruß Hagen
"Wie löst man sowas in der Praxis? Den Kehrwert um 8 Bit nach links Schieben und dann nur das obere Byte des Resultats der Mulitplikation beachten?" Dein Resultat mit dem Reziproken in der Multiplikation (bei zwei 8 Bit Zahlen) ist dann 16 Bit groß. In den obersten 8 Bits steht der Dividend und in den untersten die Bruchteile eg. Nachkommastellen. Zb. möchtest du durch 255 dividieren. Dann würde unser scalieretes reziprok also 1/255 * 256 = 1.0039 sein. Nun wilst du zb die Zahl 1024 / 255 rechen und das mit indem mit dem Reziproken = 1.0039 multipliziert wird. 1024 * 1.0039 = 1027.9936 / 256 (korrektur) macht 4.0156. 1024 / 255 = 4.0156. Aber wir rechnen ja nicht mit Nachkommastellen sondern Ganzzahlig also ist under Reziprok von 1/255*256 == 1. 1024 * 1 = 1024 / 256 = 4. Anders Beispiel: 1234 / 45 = 27.42 1/ 45 * 256 = 5.68889 als Ganzahl also rund 6. 1234 * 6 / 256 = 28 Die / 256 ist einfach ein versetzter Speicherzugriff auf unser 16 Bit breites Resultat, wir werten also nur die obersten 8 Bits davon aus. Dort finden wir nach unserer Rechnung die 28. Es ist bei so einer Division also wichtig zu wissen wie genau wir arbeiten müssen, bzw. wie groß der Fehler sein wird dadurch das wir 1/45 * 256 runden müssen. Gruß Hagen
Hi, kann man den Kehrwert einer Zahl nicht ganz einfach daraus bilden, dass man sie am Komma spiegelt? Ohne jetzt näher darüber nachzudenken liefert dieser Ansatz zumindest im unteren Zahlenbreich( Überschlag im Kopf mit 2 Versuchen) erstaunliche Resultate! Eine Multiplikation ist ja mit Shifts und XORs und ADDs relativ primitiv zu machen. Ich denke, eine Division geht auf ähnliche Weise. PS: Bitte poste mal einer auf meinen BLDC Thread, ich bin am verzweifeln, Analog isch der absolute Tod Gruß HL
> Ja und ? Wir sollten strikt trennen zwischen der mathematischen > Komplexität einer Operation und einer technischen Realisierung und > deren Komplexität in zb Hardware. Einer der Gründe weshalb ich in die Praxis gegangen bin (s.u.) > Das was ich aus diesem Paper raus lesen konnte ist das der > vorgeschlagende Algo. immernoch um mehrfaches höhere Komplexität > besitzt als eine Multiplikation. Auch wenn der Weg über die Signed > Digit Repräsentation wirklich interessant ist. Mit dieser Form der > Zahlendarstellung hatte ich bisher nur in der Exponentation in GF(p) > also Elliptischen Kurven zu tuen gehabt. Komplexität kann hier mehrere Bedeutungen haben, entweder des Algorithmus(Laufzeit) oder der Hardware. Beim sequentiellen Algorithmus: T=5n/4k + 1 bzw. da n die Anzahl der Bits ist O(n)=ln n, die Kombinatorische (Parallel Array-Divider) T = 1. Die Hardware hat dagegen O(n) = n bzw. n^2
Man was habe ich mit meiner frage hier ausgelöst? :-) Nein im ernst, diese "einfache Sache" ist ganz interessant und lehrreich. Gruss Kapitän Blei
>> kann man den Kehrwert einer Zahl nicht ganz einfach daraus bilden, >> dass man sie am Komma spiegelt? Nicht das ich wüsste das sowas korrekt wäre. Ich kenne im Grund nur drei mathematische Verfahren den Kehrwert zu berechnen. 1.) mit einer stinknormalen Division 2.) mit einer Newton Iteration 3.) das Reziproke über ein Reziprok Normalerweise wird man bei supergroßen Zahlen immer mit der Newton Iteration arbeiten (das trifft auch auf Wurzeln etc.pp. zu). Die Newton Iteration hat die beste Komplexität (ist also am schnellsten) und berechnet in jedem Teilschritt ihrer Iteration die doppelte Menge an Stellen/Ziffern zum vorherigem Iterationsschritt. Die 3.) Methode ist zwar sehr interessant hat aber nur Vorteile wenn man wiederum mit Konstanten arbeitet. Gruß Hagen
Ja, Kapitän Blei, so kann das abgehen! :-) Aber noch mal ganz zurück, warum der AVR keinen div-maschinenbefehl hat: Das AVR-konzept zielt von jeher ausdrücklich auf die verwendung einer hochsprache ab, speziell c, und da gibt es tatsächlich keinen fall, in dem eine beschleunigte division irgendwie interessant wäre. Ganz im gegensatz zur multiplikation. Weswegen die hardware-unterstützt ist... der yogibaer
Das ist ja nicht nur ein super spannender, sondern auch ein echt lehrreicher Fred! Es wurde hier des öfteren die Meinung vertreten, daß in den Steuerungsanwendungen für die die AVRs benutzt werden, kaum Divisionen vorkommen. Mag sein. Will man aber in Richtung Regelung gehen, wird es deutlich rechenintensiver und man kommt ohne Divisionen kaum noch aus. Als Beispiel fällt mir die Interpolation zwischen zwei Werten ein, wozu man dividieren muß: Alle Variablen u8 y = x * (y2 - y1) / (x2 - x1) + y1;
Warum hat der AVR keinen Divisionsbefehl? Der Grund ist ganz einfach: Es war dem Hersteller (Atmel) schlichtweg zu aufwendig (teuer) einen Hardware-Dividierer zu bauen. So ein Prozessor wird ja nicht nach dem technisch möglichen gebaut, sondern nach marketingtechnischen Aspekten der angepeilten Zielgruppe. Dabei gilt für den Hersteller immer die Devise: Die Kosten für Entwicklung, Herstellung und Vertrieb des Produktes möglichst klein zu halten, dafür aber das Produkt aus Verkaufspreis und Absatzzahlen möglichst hoch zu halten.
>y = x * (y2 - y1) / (x2 - x1) + y1; >Wie oft (pro Sekunde) wird das gerechnet? Das und noch naderes würde einmal pro Hauptschleife zu rechnen sein. Allerdings in 8bit Integer für jede Variable und das Endergebnis.
Das ist keine Antwort auf die Frage. Entscheidend ist nur, ob die Geschwindigkeit ausreicht. Eine 8:8 Divison braucht keine 4 µsec.
Also der AT89LP4052 braucht für die 8Bit Division 0,2µs bei 20Mhz. Für Regelungen kann man die Operanden auch einfach logarithmieren und dann voneinander abziehen. Da der Rechenfehler bei gleichen Operanden immer gleich ist, ist die Regelung im eingeschwungenen Zustand trotzdem 100% genau. Nur eben die Regelschritte bis dahin sind geringfügig abweichend. Die Regelung schwingt also nen Tick langsamer ein. Peter
<sich wundernd> > Für Regelungen kann man die Operanden auch einfach logarithmieren > und dann voneinander abziehen. Das ist tatsächlich schneller als dividieren? (da kommt ja auch noch ein potenzieren dazu). Ohne Scheiss?
Ohne jetzt wirklich Ahnung haben zu wollen, aber eine Logarithmustabelle im Flash (oder zwei, eine zum Logarithmieren, eine für den Rückweg) für 8 Bit sollte doch machbar sein, oder? Bei 16 Bit wirds dann aber eng... Haut mich, wenn ich irre... ;-) ...
also ich hab mal gelert das die Division durch 2 voll einfach ist. Man muß nur alles binär machen. nimm die Zahl, und lass sie einfach nach rechts rotieren. Ich weiß jetzt nur nicht ob der AVR ein rotate right hat. mußt du mal schauen
Hat er. Aber darum gehts hier nicht. Wir reden nicht vom einem Spezialfall, sondern vom allgemeinen Fall. Abgesehen davon überlässt man solche Sonderfälle sowieso dem Compiler. Der weiss ob rechts schieben schneller ist als dividieren und nimmt die Ersetzung während des Compilierens vor. Selbiges für Multiplizieren, nur dass Compiler oft auch für einige kleine ganze Zahlen spezielle Multiplizier- regeln haben. Nur wie gesagt: es geht hier nicht um die Sonderfälle.
Der HC11 kann übrigens 16:16 teilen. Wenn ich mich recht erinnere, kennt der zum normalen IDIV sogar noch FDIV. Ich glaub, ich zieh den ganzen alten Krempel mal wieder unter dem Tisch hervor...
Wie schon geschrieben wurde, es kommt nur das in den µC rein, was wirtschaftlich auch wirklich sinn macht. Gutes Beispiel: der 80C537 (uralt 8051 ) konnte damals schon: Fast 32-bit division, 16-bit 2 multiplication, 32-bit normalize and shift by peripheral MUL/DIV unit (MDU)
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.