<!DOCTYPE HackMD>
# Computer Organisation Project 4: Booth's Multiplication

> [name=林濬祺 (B11032043)] [time=26 Apr 12023][color=#CC77FF]

## Parametre settings

- A:= 11032043
- B:= 121705972753849 = 0x6EB0 **E145** E5B9
- 0x**E145** = 0b1**110 0001 0100 0101**
- C:= 0b0**110 0001 0100 0101**
- -C:=0b1001 1110 1011 1011
- D:= 0b1**110 0001 0100 0101**

## Booth's Multiplication of CxD

Step                Product                  Next
00    00000000 00000000 11100001 01000101 0  10: sub
01   [phone] 10111011
      10011110 10111011 11100001 01000101 0
      11001111 01011101 11110000 10100010 1  01: add
02   +01100001 01000101
      00110000 10100010 11110000 10100010 1
      00011000 01010001 01111000 01010001 0  10: sub
03   [phone] 10111011
      10110111 00001100 01111000 01010001 0
      11011011 10000110 00111100 00101000 1  01: add
04   +01100001 01000101
      00111100 11001011 00111100 00101000 1
      00011110 01100101 10011110 00010100 0  00: shift
05    00001111 00110010 11001111 00001010 0  00: shift
06    00000111 10011001 01100111 10000101 0  10: sub
07   [phone] 10111011
      10100110 01010100 01100111 10000101 0
      11010011 00101010 00110011 11000010 1  01: add
08   +01100001 01000101
      00110100 01101111 00110011 11000010 1
      00011010 00110111 10011001 11100001 0  10: sub
09   [phone] 10111011
      10111000 11110010 10011001 11100001 0
      11011100 01111001 01001100 11110000 1  01: add
10   +01100001 01000101
      00111101 10111110 01001100 11110000 1
      00011110 11011111 00100110 01111000 0  00: shift
11    00001111 01101111 10010011 00111100 0  00: shift
12    00000111 10110111 11001001 10011110 0  00: shift
13    00000011 11011011 11100100 11001111 0  10: sub
14   [phone] 10111011
      10100010 10010110 11100100 11001111 0
      11010001 01001011 01110010 01100111 1  11: shift
15    11101000 10100101 10111001 00110011 1  11: shift
16    11110100 01010010 11011100 10011001 1  done
CxD = 11110100 01010010 11011100 10011001    (by my algorithm)
CxD = 11110100 01010010 11011100 10011001    (by built-in multiplication)

P.S
-
I wrote a little C++ program to help me out, since doing it by hand is too tedious to me, especially when I have a whole lot of `sub` and `add`. Here is the code:

#include <iostream>
#include<string>

void out16(int x){
    for(int i=16;i--;) //i from 15 downto 0
        {
        std::cout << ((x>>i) & 1);
        if(i==8)
        std::cout<<' ';
        }
    return;
}

void out32(int x)
{
    out16(x>>16);
    std::cout<<' ';
    out16(x);
    return;
}

int main() {
    // Write C++ code here
    int addc = 0b0110'0001'0100'0101, d = 0b1110'0001'0100'0101, subc = static_cast<int>(-static_cast<short>(addc));
    int s = d;
    bool comp = false;
    std::cout<<"Step" << std::string(16,' ')<<"Product"<<std::string(18, ' ') <<"Next\n"
               "00    ";
    out32(s);
    std::cout<<' '<<comp<<"  ";
    for(int i=0;i++<16;)
        switch((comp?1:0) - (s&1))
        {
            case 1:
                std::cout<<"01: add\n";
                s += addc<<16;
                std::cout<< (i<10 ? "0":"") <<i<<"   +";
                out16(addc);
                std::cout<<"\n      ";
                out32(s);
                std::cout<<' '<<comp<<"\n      ";
                comp = s&1;
                s/=2;
                if(s<0)s--;
                out32(s);
                std::cout<<' '<<comp<<"  ";
                break;
            case -1:
                std::cout<<"10: sub\n";
                s += subc<<16;
                std::cout<< (i<10 ? "0":"") <<i<<"   +";
                out16(subc);
                std::cout<<"\n      ";
                out32(s);
                std::cout<<' '<<comp<<"\n      ";
                comp = s&1;
                s/=2;
                if(s<0)s--;
                out32(s);
                std::cout<<' '<<comp<<"  ";
                break;
            case 0:
                if(comp)
                    std::cout<<"11: shift\n"<<(i<10 ? "0":"") <<i<<"    ";
                else
                    std::cout<<"00: shift\n"<<(i<10 ? "0":"") <<i<<"    ";
                comp = s&1;
                s/=2;
                if(s<0)s--;
                out32(s);
                std::cout<<' '<<comp<<"  ";
                break;
        }
        
    std::cout<<"done\nCxD = ";
    out32(s);
    
    std::cout<<"    (by my algorithm)\nCxD = ";
    short sc = 0x6145, sd = 0xe145;
    out32(static_cast<int>(sc)*sd);
    std::cout<<"    (by built-in multiplication)";
    return 0;
}