B-Complement Multiplikation in Altklausur

Question

Edit: Fehler gefunden. cp = -3 / 4 = -1 und nicht 0, da -1 = 4q + r und somit q = -1 und nicht 0.

Ich habe eine Frage zum Algorithmus zur B-Complement Multiplikation. In der Altklausur SoSe 2020 bin ich auf folgende Aufgabe gestoßen, wobei ich bei dem rot markierten Kästchen auf ein Problem gestoßen bin:

https://imgur.com/a/r7g4hcY

Laut Algorithmus muss ich wie folgt rechnen:

let(sm = xin * yin + pin + cin);
cp [i][j] = sm / B;

pp [i][j] = sm % B;

pp [i][N] = gamma (cp [i][N-1]);

Da meine 2 hier ein most significant bit ist, muss ich alpha(2) für xin nehmen. Ergo ergibt sich für sm: -2 * 2 + 0 + 1 = -4 + 1 = -3

Ebenso ergäbe sich hier bei mir für pp[0][3] = -3 mod 4 = 1 (in der Lösung 1)
Allerdings ist cp bei mir dann = -3 / 4 = 0, in der Lösung steht aber -1
Und pp[0][4] = gamma (0) = 0, in der Lösung dann gamma (-1) = 3, was einfach nur ein Folgefehler bei mir wäre.

Um es also auf den Punkt zu bringen: Wie komme ich hier auf das Carry-Bit von -1?

Wo habe ich mich hier verrechnet? Oder wo liegt mein Denkfehler?

Comments

Ich denke, dass Sie ein Opfer eines Taschenrechners geworden sind: Beachten Sie hierzu die Folien 42 und 104 aus DiRa-04-IntegerArithmetic)!

---

Jap, beim Taschenrechner käme da natürlich eine Zahl < 1 raus.

Answer 1

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. 

Comments

Vielen vielen Dank für die ausführliche Antwort. Mein Problem lag genau in dem einen Schritt, cp als sm / B zu berechnen, da ich bei negativen Werten für sm dann zu cp = 0 kam, aber man (wie Sie ja auch gezeigt haben, ich aus der Vorlesung aber vergessen hatte) dann logischerweise auf cp = -1 kommt, da bspw. -1 = -1 * 4 + 3.