Schnelle Division durch 5

[Daniel (Gast)]

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

[Mika (Gast)]

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

[Karl H. (kbuchegg)]

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?

[Christian -. (kakuijin)]

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

[Karlheinz (Gast)]

> 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

[Stefan Hennig (Gast)]

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

[Marius W. (mw1987)]

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

[Stefan Hennig (Gast)]

@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

[chris (Gast)]

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

[Route_66 (Gast)]

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

[Route_66 (Gast)]

sorry, too slow

[Oliver W. (olliw)]

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

[Stefan Hennig (Gast)]

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.

[Stefan Hennig (Gast)]

Korrektur:

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

Sorry.

[Arc N. (arc)]

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