www.mikrocontroller.net

Forum: Mikrocontroller und Digitale Elektronik Multiplikationsroutine


Autor: Simon K. (simon) Benutzerseite
Datum:
Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: A.K. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: peter dannegger (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
So gehts noch einfacher:
long mulxy (long x, long y)
{
  return x * y;
}


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.

Autor: Eckhard (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo,

das Stichwort heißt Booth Algorithmus.

Eckhard

Autor: Wolfram (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: A.K. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
"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?

Autor: Simon K. (simon) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Mario (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: peter dannegger (Gast)
Datum:
Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Simon K. (simon) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Naja solange diese Routinen im * und / des Compilers integriert sind
habe ich damit nixx am Hut. In ASM werde ich sowas sowieso nie machen.

Autor: Profi (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@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...

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


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?

Autor: Rolf Magnus (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> 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.

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.