Forum: Mikrocontroller und Digitale Elektronik Multiplikationsroutine

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.

Hallo,

das Stichwort heißt Booth Algorithmus.

Eckhard

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?

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

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