mikrocontroller.net

Forum: Mikrocontroller und Digitale Elektronik Schnelle Division durch 5


Autor: Daniel (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo,

Bei Multiplikation gibt es einfache Tricks x*5=x*(4+1)=x<<2+x
Gibt es etwas vergleichbares für die Division?

Mein Ausgangsproblem ist: [hbyte][lbyte]:5
Mein Instructionset ist: PIC16

Ich habe zwar eine Routine geschrieben, aber sie nimmt mir
zu viel Speicher weg. Deswegen suche ich bessere/schnellere/
platzsparendere Varianten dafür. Wer kann mir helfen?

Grüsse, Daniel

Autor: Mika (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Und was hinderd dich, es für die Division genau andersherum zu 
machen...?

Also x/5=x/(4+1)=x>>2-x.

Viele Grüße,
Mika

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Mika schrieb:
> Und was hinderd dich, es für die Division genau andersherum zu
> machen...?
>
> Also x/5=x/(4+1)=x>>2-x.

?
Die Tatsache, dass da Unsinn herauskommt?

Autor: Christian --- (kakuijin)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Keine Garantie: x/5 = x*0.2
nen versuch ist es wert ;)

Autor: Karlheinz (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> Und was hinderd dich, es für die Division genau andersherum zu
> machen...?

> Also x/5=x/(4+1)=x>>2-x.

Gegenbeispiel: 16/5 = 16/(4+1) != 16>>2-16

Autor: Stefan Hennig (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Naja, weiß ja nicht, wofür Du die Division brauchst und vor allem weiß 
ich nicht, ob der PIC schnelle Multiplikationen kann, aber vielleicht 
kann man auch iterativ vorgehen:

Zu lösen: y=x/5

Entspricht: finde ganzzahliges y, so dass möglichst genau gilt: 5*y=x

Iteration:
y_0 = x >> 2

Fehler: e_i = x - 5*y_i
oder auch: e_i = x - y_i - (y_i<<2)

Korrektur:
y_i+1 = y_i + e_i>>2

Auf meinem Taschenrechner geht das auch mit dem groben initialen Wert 
mit maximal 6 Iterationen für Deinen 16-Bit Wertebereich. Ist natürlich 
sehr speziell, aber vielleicht ein Ansatz für Dein Problem.

Grüße,
 Stefan

Autor: Marius Wensing (mw1987)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Da du nicht geschrieben hast wie genau die Routine sein muss, schlage 
ich mal folgendes vor:

x / 5 ist ungefähr x * 13/64... Das lässt sich nur mit Additionen und 
Shift-Operationen darstellen:

x / 5 = (x + (x << 2) + (x << 3)) >> 6

MfG
Marius

Autor: Stefan Hennig (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@Marius:
Coole Idee. Ziemlich genau. Kann man vielleicht noch mit einer 
Korrekturtabelle ganz genau machen.

Was mir aber noch aufgefallen ist:
Sowohl Marius' als auch meinen Vorschlag kann man nicht mit reiner 
16-Bit Arithmetik für den gesamten Wertebereich umsetzen. Bei meinem 
Vorschlag muss man vorzeichenbehaftet rechnen (+1 Bit), bei Marius 
entstehen Zwischenergebnisse mit 19 Bit.

Wie gesagt: Hängt alles vom Einsatzzweck ab.

Grüße,
 Stefan

Autor: chris (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Den Vorschlag von Markus kann man noch weiter treiben, z.B.:

x*51/256,
x*819/4096
x*13107/65536

Im letzten Fall läuft das Ganze zwar auf eine 32bit Multiplikation 
hinaus, dafür steht am Ende das Ergebnis in den beiden ersten Bytes.

Gruß, Chris

Autor: Route_66 (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo! 51/256 ist noch eine bessere Iteration:
x merken in y
x mal 2 (einmal links schieben)
x+y (ist jetzt 3 mal ursprüngliches x) und wieder in y merken
jetzt x mal 16 (viermal links schieben) ergibt 48 mal ursprüngliches x
wieder x+y ergibt jetzt 51 mal ursprüngliches x
jetzt den LOW-Teil von x "wegwerfen" bedeutet geteilt durch 256

Autor: Route_66 (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
sorry, too slow

Autor: Oliver W. (olliw)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
sucht doch mal im Netz nit google -> z.B.
http://www.hackersdelight.org/divcMore.pdf
http://blogs.msdn.com/devdev/archive/2005/12/12/502980.aspx
diese Routinen benutze ich gerne

Autor: Stefan Hennig (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo Leute!
Mir ist da ein Muster aufgefallen:

In Binärdarstellung ist 0.2=0.001100110011...
Und: 51d=110011b
Und: 819d=1100110011b
Und: (Ihr ahnt es schon) 13107d=11001100110011b

Damit kann man Marius' (und natürlich auch Chris') Formeln auch so 
schreiben: (wenn man annimmt, dass (x<<3)>>6 == x>>3, etc. [1])

y=(x>>3)+(x>>4)+(x>>7)+(x>>8)+(x>>10)+(x>>11)+... [2]

Also als Reihenentwicklung. Die Genauigkeit kann man dann so einstellen 
wie man's braucht.

Grüße,
  Stefan

[1] natürlich kann man die Rechnung so nicht ausführen, weil man die 
weggefallenen Nachkommabits mit aufsummieren muss
[2] Marius hat mit 13 statt mit 12 im Zähler gerechnet, weil er gerundet 
hat, aber für die Reihenentwicklung ist das unerheblich.

Autor: Stefan Hennig (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Korrektur:

y=(x>>3)+(x>>4)+(x>>7)+(x>>8)+(x>>11)+(x>>12)+...

Sorry.

Autor: Arc Net (arc)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Stefan Hennig schrieb:
> Hallo Leute!
> Mir ist da ein Muster aufgefallen:

Wenn man Zeit sparen will:
http://spiral.ece.cmu.edu/mcm/gen.html
bzw.
http://spiral.net/index.html

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.