Schauen wir uns das im Detail an: Wir wollen die Zahlen 4-Komplementzahlen y=31022 und x=2311 multiplizieren. Mit dem Baugh-Wooley-Verfahren ergibt sich dann das folgende Schema (Seite 142, DiRa-04-IntegerArithmetic):
α(2)*2 3*2 1*2 1*2
α(2)*2 3*2 1*2 1*2
α(2)*0 3*0 1*0 1*0
α(2)*1 3*1 1*1 1*1
α(2)*α(3) 3*α(3) 1*α(3) 1*α(3)
--------------------------------------------------------------------
p8 p7 p6 p5 p4 p3 p2 p1 p0
Mit α(2)=-2 und α(3)=-1 ergibt dies zunächst
(-2)*2 3*2 1*2 1*2
(-2)*2 3*2 1*2 1*2
(-2)*0 3*0 1*0 1*0
(-2)*1 3*1 1*1 1*1
(-2)*(-3) 3*(-3) 1*(-3) 1*(-3)
--------------------------------------------------------------------
p8 p7 p6 p5 p4 p3 p2 p1 p0
Nun muss man die Partialprodukte ausrechnen und aufaddieren. Der Algorithmus (Seite 144, DiRa-04-IntegerArithmetic) macht dies wie folgt:
x[0]= 2 y[0]= 1 pp[-1, 1]= 0 cp[ 0,-1]= 0-> sm= 2 cp[0,0]= 0 pp[0,0]= 2
x[0]= 2 y[1]= 1 pp[-1, 2]= 0 cp[ 0, 0]= 0-> sm= 2 cp[0,1]= 0 pp[0,1]= 2
x[0]= 2 y[2]= 3 pp[-1, 3]= 0 cp[ 0, 1]= 0-> sm= 6 cp[0,2]= 1 pp[0,2]= 2
x[0]= 2 y[3]=-2 pp[-1, 4]= 0 cp[ 0, 2]= 1-> sm=-3 cp[0,3]=-1 pp[0,3]= 1
--> pp[0,4]= 3
x[1]= 2 y[0]= 1 pp[ 0, 1]= 2 cp[ 1,-1]= 0-> sm= 4 cp[1,0]= 1 pp[1,0]= 0
x[1]= 2 y[1]= 1 pp[ 0, 2]= 2 cp[ 1, 0]= 1-> sm= 5 cp[1,1]= 1 pp[1,1]= 1
x[1]= 2 y[2]= 3 pp[ 0, 3]= 1 cp[ 1, 1]= 1-> sm= 8 cp[1,2]= 2 pp[1,2]= 0
x[1]= 2 y[3]=-2 pp[ 0, 4]=-1 cp[ 1, 2]= 2-> sm=-3 cp[1,3]=-1 pp[1,3]= 1
--> pp[1,4]= 3
x[2]= 0 y[0]= 1 pp[ 1, 1]= 1 cp[ 2,-1]= 0-> sm= 1 cp[2,0]= 0 pp[2,0]= 1
x[2]= 0 y[1]= 1 pp[ 1, 2]= 0 cp[ 2, 0]= 0-> sm= 0 cp[2,1]= 0 pp[2,1]= 0
x[2]= 0 y[2]= 3 pp[ 1, 3]= 1 cp[ 2, 1]= 0-> sm= 1 cp[2,2]= 0 pp[2,2]= 1
x[2]= 0 y[3]=-2 pp[ 1, 4]=-1 cp[ 2, 2]= 0-> sm=-1 cp[2,3]=-1 pp[2,3]= 3
--> pp[2,4]= 3
x[3]= 1 y[0]= 1 pp[ 2, 1]= 0 cp[ 3,-1]= 0-> sm= 1 cp[3,0]= 0 pp[3,0]= 1
x[3]= 1 y[1]= 1 pp[ 2, 2]= 1 cp[ 3, 0]= 0-> sm= 2 cp[3,1]= 0 pp[3,1]= 2
x[3]= 1 y[2]= 3 pp[ 2, 3]= 3 cp[ 3, 1]= 0-> sm= 6 cp[3,2]= 1 pp[3,2]= 2
x[3]= 1 y[3]=-2 pp[ 2, 4]=-1 cp[ 3, 2]= 1-> sm=-2 cp[3,3]=-1 pp[3,3]= 2
--> pp[3,4]= 3
x[4]=-1 y[0]= 1 pp[ 3, 1]= 2 cp[ 4,-1]= 0-> sm= 1 cp[4,0]= 0 pp[4,0]= 1
x[4]=-1 y[1]= 1 pp[ 3, 2]= 2 cp[ 4, 0]= 0-> sm= 1 cp[4,1]= 0 pp[4,1]= 1
x[4]=-1 y[2]= 3 pp[ 3, 3]= 2 cp[ 4, 1]= 0-> sm=-1 cp[4,2]=-1 pp[4,2]= 3
x[4]=-1 y[3]=-2 pp[ 3, 4]=-1 cp[ 4, 2]=-1-> sm= 0 cp[4,3]= 0 pp[4,3]= 0
--> pp[4,4]= 0
Also, was ist nun der Fehler?
An der fraglichen Stelle finden wir oben die folgenden Zahlen:
x[0]= 2 y[3]=-2 pp[-1, 4]= 0 cp[ 0, 2]= 1-> sm=-3 cp[0,3]=-1 pp[0,3]= 1 --> pp[0,4]= 3
Diese Werte wurden wie folgt berechnet:
sm = x[0] * y[3] + pp[-1,4] + cp[0,2] = 2*(-2) + 0 + 1 = -3
-3 = (-1)*4+1 = cp[0,3] * 4 + pp[0,3]
--> cp[0,3]=-1 pp[0,3]= 1
--> pp[0,4]= gamma(cp[0,3]) = gamma(cp[0,3]) = 3
Insofern stimmt das Bild in der Musterlösung mit dem Algorithmus überein und beide sind korrekt!
Beachten Sie, dass -3 = (-1)*4+1 gilt, so dass (-3) div 4 = -1 ist. Beachten Sie auch (das haben Sie aber schon gesehen), dass man beim letzten Übertrag einer Zeile die Funktion gamma anwenden muss.