Ich hab mal hier ne Routine für die Multiplikation entwickelt, die nur auf Schiebungen basiert. Jenachdem welche Bits gesetzt sind, wird geschoben oder nicht und alles aufaddiert. Wie findet ihr das? Ist das schon uralter Kram und in jedem Compiler integriert oder ist das ne nette Routine? PS: Ich suche sowas für Division. Habe schon etwas rumprobiert, aber scheine keine Zusammenhänge zu finden, wie ich die Division in 2^x Schritte aufteilen kann.
Naja, Du glaubst doch nicht wirklich, dass Du die Multiplikation neu erfunden hast, oder? So ähnlich funktioniert das überall wo der Prozessor nicht selber etwas zur Verfügung stellt. Jedenfalls wenn sizeof(int)==4. Bei 16bit int lang's 16fach statt 32fach. Statt if(...) erg += (y<<i); wird's erheblich besser mit if(...) { erg += y; } y <<= 1; jedenfalls bei AVRs, 8051 und so. Für die Division gibt es auch sowas in der Art.
So gehts noch einfacher:
1 | long mulxy (long x, long y) |
2 | {
|
3 | return x * y; |
4 | }
|
Der daraus erzeugte Assemblercode ist bestimmt schneller und kleiner als jede C-Routine. Peter P.S.: Aufm AVR oder 8051 funktioniert Deine Routine nicht, da dort int nur 16-bittig ist, deshalb long für 32Bit nehmen.
Nett, aber nicht nur Compiler sondern auch die meisten Prozessoren haben sowas schon integriert ;-) Eine Anmerkung: dein Code setzt eine Int größe von 32 Bit unsigned voraus! Auf einem Prozessor dessen Compiler 32bit als int grösse hat würde ich die Multiplikation in Hardware voraussetzen. (Abgesehen von abgespeckten NIOS Varianten) Du übergibts int (signed) das wird ein bisschen komplizierter mit dem Vorzeichen. Allemal eine nette Übung, allerdings besser in Assembler zu betreiben, da man da eine Chance hat, schneller als die Multiplikation des Compilers zu sein. Wenn es dich immer noch interessieren sollte, in einem Buch habe ich mal die Division in Software gehabt. Ging irgendwie mit Subtraktion.
"Du übergibts int (signed) das wird ein bisschen komplizierter mit dem Vorzeichen." Nur wenn ein Ergebnis von n*n=>2n Bits benötigt wird. Bei n*n=>n Bits besteht kein Unterschied. "Booth Algorithmus" In Software?
in deckung geh okok Leute ;) Ist übrigens in MSVC (noch) geschrieben @Peter: JAJA, ich hab doch extra gefragt ob der Compiler das so rechnet ;) Kann ja sein dass der x mal y aufaddiert.
auf den PIC's ist das z.t. noch notwendig. Ich habe mich gerade vor kurzem mit derartigem (Multiplikation+Division) herumschlagen müssen (Platz und Geschwindigkeit). Ich denke aber dass ein derartiges Problem nur noch am "Rande" vorkommt. Desweiteren gibt's bei Microchip auch APP-Notes die eine komplette Library beschreiben (allerdings nicht ganz effizient) und auch den (ASM-)Code dazugeben - inklusive komplizierterer Rechenoperationen, realisiert über CORDIC-Algortihmen. Wenn (reges) Interesse besteht kann ich dazu einen Artikel im Wiki-verfassen. Gruß Mario
Anbei mal Mul und Div für 56 Bit * / 24 Bit in AVR-Assembler Das Schema läßt sich bequem auf 80 Bit * / 80 Bit erweitern. Peter
Naja solange diese Routinen im * und / des Compilers integriert sind habe ich damit nixx am Hut. In ASM werde ich sowas sowieso nie machen.
@Mario: schreiben wir gemeinsam was? Hier von mir eine extrem kompakte und schnelle mul32x32->64: C-Code zur Verdeutlichung und Erklärung: http://www.mikrocontroller.net/forum/read-1-343046.html#350551 und die Umsetzung in AVR-Asm (68HC08 hab ich schon auf meinem anderen PC, kommt noch nach): http://www.mikrocontroller.net/forum/read-1-343046.html#351199 Peter: Deine Routinen sind ja wirklich sehr ausgeklügelt! Das ist wichtig für Prozessoren, die keinen mul können. Kannst Du bitte mitteilen, welche mul haben und welche nicht? @All: Bin gerade dabei, eine 24x40->64 Routine zu proggen, später sind noch andere Kombinationen geplant (auch 24x56 für Peter ;-)). Bei Ergebnissen >64bit wird's schwierig mit dem Überprüfen der Ergebnisse, da kein mir bekannter Hex-Tipper (Rechner) mehr als 64 bit interne Stellen hat. Oder weiß jemand einen?
> Jenachdem welche Bits gesetzt sind, wird geschoben oder nicht und > alles aufaddiert. So wie's halt jeder macht. > PS: Ich suche sowas für Division. Habe schon etwas rumprobiert, > aber scheine keine Zusammenhänge zu finden, wie ich die Division > in 2^x Schritte aufteilen kann. So, wie man eine Multiplikation als forgesetzte Addition lösen kann, kann man die Division mit Subtraktion machen. Überleg dir einfach mal, wie du in der Grundschule dividiert hast und übertrage das auf Dualzahlen. @Profi: bc kann mit beliebig großen Zahlen arbeiten und geht auch mit hex.
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.