|
Anzeige
|
Schnelle Division durch 5
Gast
#1431280
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
Gast
#1431285
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 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? Keine Garantie: x/5 = x*0.2 nen versuch ist es wert ;)
Gast
#1431299
> 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
Gast
#1431330
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 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
Gast
#1431346
@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
Gast
#1431350
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
Gast
#1431356
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
Gast
#1431360
sorry, too slow 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
Gast
#1431384
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.
Gast
#1431387
Korrektur: y=(x>>3)+(x>>4)+(x>>7)+(x>>8)+(x>>11)+(x>>12)+... Sorry. 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 |
Anzeige
|
