Here you can ask questions and find or give answers to organizational, academic and other questions about studying computer science.

1.1k questions

1.2k answers

1.6k comments

531 users

0 votes
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?
in * TF "Emb. Sys. and Rob." by (160 points)
edited by
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.

1 Answer

+1 vote
 
Best answer

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. 

by (166k points)
selected by
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.

Related questions

0 votes
1 answer
0 votes
1 answer
asked Aug 21, 2020 in * Other Teaching Fields by Eichi (200 points)
0 votes
1 answer
asked Aug 27, 2023 in * TF "Emb. Sys. and Rob." by User100 (290 points)
Imprint | Privacy Policy
...