বাইনারি মাল্টিপ্লিকেশন — Booth's Algorithm

# Booth's Algorithm -- বিট-লেভেল সিমুলেশন, L18 conversion ও L19 adder/subtractor পুনর্ব্যবহার করে
# (কোনো বাস্তব CPU ইনস্ট্রাকশন নয় -- সম্পূর্ণ toy বিট-স্ট্রিং সিমুলেশন)

def to_twos_complement(n, bits):
    if n >= 0:
        return bin(n)[2:].zfill(bits)
    positive_bits = to_twos_complement(-n, bits)
    inverted = "".join("1" if c == "0" else "0" for c in positive_bits)
    return bin((int(inverted, 2) + 1) % (2 ** bits))[2:].zfill(bits)

def from_twos_complement(bits_str):
    n = len(bits_str)
    value = int(bits_str, 2)
    return value - 2 ** n if bits_str[0] == "1" else value

def full_adder(a, b, cin):
    s = a ^ b ^ cin
    cout = (a & b) | (cin & (a ^ b))
    return s, cout

def ripple_carry_adder(a_bits, b_bits, cin=0):
    n = len(a_bits)
    result = ["0"] * n
    carry = cin
    for i in range(n - 1, -1, -1):
        a, b = int(a_bits[i]), int(b_bits[i])
        s, carry = full_adder(a, b, carry)
        result[i] = str(s)
    return "".join(result), carry

def adder_subtractor(a_bits, b_bits, subtract_mode=False):
    if subtract_mode:
        b_bits = "".join("1" if c == "0" else "0" for c in b_bits)
        cin = 1
    else:
        cin = 0
    return ripple_carry_adder(a_bits, b_bits, cin)

def booth_multiply(multiplicand, multiplier, bits):
    """Booth's Algorithm -- প্রতিটি ধাপের বিট-পেয়ার, action ও intermediate অবস্থা ট্রেস করে রিটার্ন করে"""
    M = to_twos_complement(multiplicand, bits)
    Q = to_twos_complement(multiplier, bits)
    A = "0" * bits
    Q_minus1 = "0"
    trace = []
    for step in range(1, bits + 1):
        pair = Q[-1] + Q_minus1
        if pair == "10":
            action = "A = A - M (subtract)"
            A, _ = adder_subtractor(A, M, subtract_mode=True)
        elif pair == "01":
            action = "A = A + M (add)"
            A, _ = adder_subtractor(A, M, subtract_mode=False)
        else:
            action = "no-op (00/11), শুধু শিফট"
        a_after_op = A
        # A : Q : Q_minus1 একত্রে arithmetic right shift (সাইন বিট সংরক্ষণ করে)
        combined = A + Q + Q_minus1
        sign_bit = combined[0]
        shifted = sign_bit + combined[:-1]
        A, Q, Q_minus1 = shifted[:bits], shifted[bits:2 * bits], shifted[-1]
        trace.append((step, pair, action, a_after_op, A, Q, Q_minus1))
    return A + Q, trace

product_bits, trace = booth_multiply(3, -2, 4)

print("M (multiplicand=3) =", to_twos_complement(3, 4))
print("Q (multiplier=-2)  =", to_twos_complement(-2, 4))
print()
for step, pair, action, a_after_op, A, Q, Qm1 in trace:
    print(f"ধাপ {step}: বিট-পেয়ার(Q0,Q-1)={pair}  action={action}")
    print(f"        অ্যারিথমেটিকের পর A={a_after_op}   শিফটের পর A={A} Q={Q} Q-1={Qm1}")

final_decimal = from_twos_complement(product_bits)
print()
print(f"চূড়ান্ত প্রোডাক্ট বিট (A:Q) = {product_bits}  ->  দশমিক = {final_decimal}")
print("cross-check (Python native 3 * -2):", 3 * -2)
assert final_decimal == 3 * -2
print("MATCH -- Booth's Algorithm সঠিকভাবে -6 দিয়েছে")