Forum: Mikrocontroller und Digitale Elektronik Warum besitzt der AVR keine Division-Funktion?


von Kapitän Blei (Gast)


Lesenswert?

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

von Andreas B (Gast)


Lesenswert?

"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

von Andreas S. (andreas) (Admin) Benutzerseite


Lesenswert?

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.

von Karl heinz B. (kbucheg)


Lesenswert?

und wenn alle Stricke reissen, kann man immer noch
anstatt einer Division mit dem Kehrwert multiplizieren.

von Kapitän Blei (Gast)


Lesenswert?

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

von Kapitän Blei (Gast)


Lesenswert?

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?

von Dirk D. (dirkd)


Lesenswert?

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

von johnny.m (Gast)


Lesenswert?

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

von johnny.m (Gast)


Lesenswert?

> nur dass die Operatoren bereits vorgegeben sind...
Muss natürlich Operanden heißen und nicht Operatoren...

von smps1233ln (Gast)


Lesenswert?

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

von Kapitän Blei (Gast)


Lesenswert?

Ok danke für die Erklärungen.


Gruss

Kapitän Blei

von keks (Gast)


Lesenswert?

natürlich hätte ich am liebsten einen Fliesskommakoprozessor mit auf dem
die integriert. wäre doch cool, aufm mega8 heftigst mit floats
rumzutraktieren.

von Rolf Magnus (Gast)


Lesenswert?

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

von Axel (Gast)


Lesenswert?

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

von Gernot F. (gernotfrisch)


Lesenswert?

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

von A.K. (Gast)


Lesenswert?

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

von johnny.m (Gast)


Lesenswert?

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!

von johnny.m (Gast)


Lesenswert?

Das 'Du liegst leider falsch' bezog sich natürlich auf Gernots
Posting...

von Peter D. (peda)


Lesenswert?

@Gernot

~b = -b - 1

Einerkomplement = Zweierkomplement - 1


Peter

von Gernot F. (gernotfrisch)


Lesenswert?

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

von Kapitän Blei (Gast)


Lesenswert?

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.

von Axel (Gast)


Lesenswert?

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

von Hagen R. (hagen)


Lesenswert?

"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

von Thomas O. (Gast)


Lesenswert?

abo

von mr.chip (Gast)


Lesenswert?

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

von Hagen R. (hagen)


Lesenswert?

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

von Axel (Gast)


Lesenswert?

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

von Johannes A. (Gast)


Lesenswert?

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

von Kapitän Blei (Gast)


Lesenswert?

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 ?

von Dominic R. (dominic)


Lesenswert?

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

von mr.chip (Gast)


Lesenswert?

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

von Benjamin S. (b_sieber)


Lesenswert?

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

von Benjamin S. (b_sieber)


Lesenswert?

PS: die endlosschleife am schluss hätte es net gebraucht, hab ich nur
beim kopiren übersehen g

von Johannes A. (Gast)


Lesenswert?

@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

von A.K. (Gast)


Lesenswert?

Per Atmel Application Note 200 gibt's allerlei handoptimierte Mul/Div
Routinen fix und fertig.

von William (Gast)


Angehängte Dateien:

Lesenswert?

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

von arc (Gast)


Lesenswert?

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.

von Hagen R. (hagen)


Lesenswert?

Andererseits ist so ein Thread sehr schön um zu zeigen wie eines das
andere ergibt ;)

Gruß Hagen

von Profi (Gast)


Lesenswert?

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

von Marco S. (masterof)


Lesenswert?

und er ist gut zum verstehen eines µcontroller.

von Axel (Gast)


Lesenswert?

"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

von Unbekannter (Gast)


Lesenswert?

> oder aber sie benötigt fast mehr Silikon

Zu viel Silikon sieht meistens ziemlich beschissen aus und greift sich
schlecht...

von A.K. (Gast)


Lesenswert?

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.

von mr.chip (Gast)


Lesenswert?

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?

von Hagen R. (hagen)


Lesenswert?

"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

von Der Albi (Gast)


Lesenswert?

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

von mr.chip (Gast)


Lesenswert?

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

von Johannes A. (Gast)


Lesenswert?

Ähm, sorry, Leute,

aber irgendwie klingen die letzten Posts alle, als ob Ihr noch nie was
vom AVR32 gehört habt.

Gruß
Johannes

von Dennis Strehl (Gast)


Lesenswert?

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

von Johannes A. (Gast)


Lesenswert?

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

von Johannes A. (Gast)


Lesenswert?

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

von A.K. (Gast)


Lesenswert?

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

von Axel (Gast)


Lesenswert?

"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

von Nobody (Gast)


Lesenswert?

@Profi: Wo brauche ich bei der hex->dez Umwandlung eine Division? Das
ist ja zum Schreien ineffektiv. Ich mache das ohne.

von Karl heinz B. (kbucheg)


Lesenswert?

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.

von A.K. (Gast)


Lesenswert?

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.

von Michael F. (grisu901)


Lesenswert?

@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

von A.K. (Gast)


Lesenswert?

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.

von A.K. (Gast)


Lesenswert?

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.

von Tobias S. (tobias)


Lesenswert?

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

von Karl heinz B. (kbucheg)


Lesenswert?

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

von Michael F. (grisu901)


Lesenswert?

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

von A.K. (Gast)


Lesenswert?

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.

von Profi (Gast)


Lesenswert?

@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?

von Hagen R. (hagen)


Lesenswert?

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

von Karl H. (kbuchegg)


Lesenswert?

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.

von Hagen R. (hagen)


Lesenswert?

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

von Profi (Gast)


Lesenswert?

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

von mr.chip (Gast)


Lesenswert?

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

von Hagen R. (hagen)


Lesenswert?

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

von Daniel M. (usul27)


Lesenswert?

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

von arc (Gast)


Lesenswert?

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

von Hagen R. (hagen)


Lesenswert?

@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

von arc (Gast)


Lesenswert?

> 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

von Daniel M. (usul27)


Lesenswert?

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

von mr.chip (Gast)


Lesenswert?

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

von Hagen R. (hagen)


Lesenswert?

@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

von Hagen R. (hagen)


Lesenswert?

@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

von Hagen R. (hagen)


Lesenswert?

"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

von Hannes L. (Gast)


Lesenswert?

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

von arc (Gast)


Lesenswert?

> 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

von Kapitän Blei (Gast)


Lesenswert?

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

von Hagen R. (hagen)


Lesenswert?

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

von yogibaer (Gast)


Lesenswert?

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

von MikroMan (Gast)


Lesenswert?

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;

von A.K. (Gast)


Lesenswert?

Wie oft (pro Sekunde) wird das gerechnet?

von Unbekannter (Gast)


Lesenswert?

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.

von MikroMan (Gast)


Lesenswert?

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

von A.K. (Gast)


Lesenswert?

Das ist keine Antwort auf die Frage. Entscheidend ist nur, ob die
Geschwindigkeit ausreicht. Eine 8:8 Divison braucht keine 4 µsec.

von Peter D. (peda)


Lesenswert?

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

von Karl heinz B. (kbucheg)


Lesenswert?

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

von Hannes L. (hannes)


Lesenswert?

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

...

von Christian (Gast)


Lesenswert?

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

von Karl heinz B. (kbucheg)


Lesenswert?

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.

von Propper (Gast)


Lesenswert?

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

von buz11 (Gast)


Lesenswert?

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
Noch kein Account? Hier anmelden.