Programm zur Multiplikaton ohne den Befehl MUL

dydy

Hallo, Ich möchte ein Programm zur Multiplikation zweier Zahlen ohne den Befehl MUL zu benutzen. Könnte mir bitte jemand hier helfen um den Code zu schreiben?

Thanx

Mario Sandler

Benutze add in einer Schleife wäre mein Ansatz,
aber ich würd trotzdem mul nehmen

net 0

nimmste den einen wert als schleifenzähler und den anderen addierste immer wieder auf

hellihjb

performanter wird's, wenn man sich die grundlagen der binärzahlen zunutze macht:

int mul(int a, int b)
{
	int res=0;
	for (int i=0;i<numBits;i++)
	{
		if (a & 1) res+=b;
		a>>=1;
		b<<=1;
	}
	return res;
}

wobei numBits=32 bzw entsprechend der operandengroesse zu wählen ist.
für vorzeichenbehaftete zahlen benötigt man noch entsprechende überprüfungen.

volkard

hellihjb schrieb:

wobei numBits=32 bzw entsprechend der operandengroesse zu wählen ist.

oder du ändert in

for (int i=0;a!=0;i++)

rapso

volkard schrieb:

hellihjb schrieb:

wobei numBits=32 bzw entsprechend der operandengroesse zu wählen ist.

oder du ändert in
for (int i=0;a!=0;i++)

oder

while(a)

ist einfacher und fixer.

dydy

Hey Volkard und Rapso,

Ich meine sondern in Assembler und nicht C++

hellihjb

das kriegst du bestimmt selber hin, der algorithmus ist ja wirklich leicht und laesst sich 1:1 uebertragen...

dydy

hellihjb schrieb:

das kriegst du bestimmt selber hin, der algorithmus ist ja wirklich leicht und laesst sich 1:1 uebertragen...

Hi ehrlich gesagt, bin ich noch Anfänger, ich versuche das zu schreiben und kompilieren aber geht nicht. Kannst du mal den code in asm erklären?

gargyle

Gugstu hier
http://www.coding-board.de/board/showthread.php?t=19714

rapso

dydy schrieb:

hellihjb schrieb:

das kriegst du bestimmt selber hin, der algorithmus ist ja wirklich leicht und laesst sich 1:1 uebertragen...

Hi ehrlich gesagt, bin ich noch Anfänger, ich versuche das zu schreiben und kompilieren aber geht nicht. Kannst du mal den code in asm erklären?

klar können wir das, zeig deinen code und wir klären gerne wo das problem liegt.

hellihjb

ich mach mir mal die muehe...

// register eax und ebx enthalten zu multiplizierende operanden a & b
      mov  ecx,0     // ergebnis initial = 0
mulloop:
      test eax,1     // pruefe unterstes bit von operand a
      jz   skip      // wenn's nicht gesetzt ist, folgende addition ueberspringen
      add  ecx,ebx   // addiere operand b zum ergebnis
skip:
      shl  ebx,1     // alle bits von operand b um ein bit nach oben verschieben
      shr  eax,1     // alle bits von operand a um ein bit nach unten verschieben
      jnz  mulloop   // solang operand a ungleich 0...
done:
      // ergebnis in ecx

je nach verwendetem compiler sind die sprungmarken mit beliebig vielen @ zu versehen.
was der algorithmus macht ist, fuer jedes gesetzte bit "n" von operand a zum ergebnis b*(2^n) zu addieren, also das gleiche wie eine schriftliche multiplikation nur eben im dual- anstatt im dezimalsystem.
anstatt jeweils das n-te bit von operand a zu pruefen, wird immer das unterste bit geprueft und der komplette operand um eine bitstelle verschoben (shr eax,1), wobei automatisch das zero-flag gesetzt wird, falls operand a nur noch nullen enthaellt, und dadurch die schleife (mulloop) unterbrochen.
operand b wird entsprechend jeweils um eine stelle nach oben verschoben, sodass ebx bei jedem durchlauf "n" schon b*(2^n) enthaelt und bei einem gesetzten bit0 in eax einfach auf das ergebnis addiert werden muss.
der algorithmus funktioniert auch fuer negative zahlen, weil das vorzeichen im obersten bit erhalten bleibt. nachteil in dem fall ist, dass die loop fuer einen negativen operand a immer 32 durchlaeufe macht, da ja dessen oberstes bit gesetzt ist. fuer kleine zahlen waere es also performanter das vorzeichen im vorfeld zu ueberpruefen, den algorithmus mit positivem a auszufuehren und das vorzeichen am ende entsprechend anzupassen.
da die fortfuehrung der schleife erst am ende geprueft wird, wird sie auch einmal fuer den fall a=0 durchlaufen, was quatsch ist, aber den code kuerzer macht - wer performant mit 0 multiplizieren will, findet dafuer auch sicherlich geistreichere moeglichkeiten...
darueber hinaus koennen in operand a beliebige bitmuster stehen, sodass die sprungvorhersage zum ueberspringen der addition relativ wahrscheinlich versagen wird. performanter waere daher die addition immer auszufuehren und aus dem zustand des gesetzten bit0 eine entsprechende bitmaske zu erzeugen, die den zu addierenden operand b entweder auf 0 setzt (bit0=0) oder unveraendert laesst (bit0=1), zb so:

mov  edx,eax // operand a in temporaeres register laden
and  edx,1   // nur bit0 behalten
dec  edx     // 1 subtrahieren (bit0=0: 0xffffffff  bit0=1: 0)
not  edx     // bits negieren (bit0=0: 0  bit0=1: 0xffffffff)
and  edx,ebx // und-verknuepfung mit operand b (bit0=0: 0  bit0=1: b)
add  ecx,edx // zum ergebnis addieren

damit sollte das thema eigentlich inhaltlich erschoepft sein...