বাইনারি ডিভিশন

# Restoring Division -- বিট-লেভেল সিমুলেশন, L19-এর subtractor লজিক পুনর্ব্যবহার করে
# (toy বিট-স্ট্রিং রেজিস্টার সিমুলেশন -- কোনো বাস্তব CPU ইনস্ট্রাকশন নয়)

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 subtract_bits(a_bits, b_bits):
    """L19-এর adder_subtractor(subtract_mode=True) -- b ইনভার্ট করে cin=1 দেয়"""
    inverted_b = "".join("1" if c == "0" else "0" for c in b_bits)
    return ripple_carry_adder(a_bits, inverted_b, cin=1)

def restoring_division(dividend, divisor, bits):
    """Restoring Division -- প্রতিটি বিট-পজিশনের সিদ্ধান্ত ট্রেস করে quotient, remainder রিটার্ন করে"""
    if divisor == 0:
        raise ZeroDivisionError("divisor শূন্য -- অ্যালগরিদম চালানোর আগেই রিজেক্ট করা হলো")
    if dividend >= 2 ** bits or divisor >= 2 ** bits:
        raise ValueError(f"অপারেন্ড {bits}-বিটে ধরবে না")

    remainder = "0" * (bits + 1)                     # সাইন-সহ কাজের জন্য ১ বিট বাড়তি
    quotient = bin(dividend)[2:].zfill(bits)
    divisor_bits = "0" + bin(divisor)[2:].zfill(bits)  # remainder-এর সমান প্রস্থে

    trace = []
    for step in range(1, bits + 1):
        combined = (remainder + quotient)[1:] + "0"    # remainder:quotient একত্রে বামে শিফট
        remainder = combined[:bits + 1]
        quotient = combined[bits + 1:]

        sub_result, _ = subtract_bits(remainder, divisor_bits)
        is_negative = sub_result[0] == "1"              # সাইন বিট চেক

        if is_negative:
            decision = "ঋণাত্মক -> রিস্টোর (বিয়োগ বাতিল), quotient bit = 0"
            quotient_bit = "0"
            # remainder অপরিবর্তিত থাকে (রিস্টোর)
        else:
            decision = "অ-ঋণাত্মক -> ফলাফল রাখা হলো, quotient bit = 1"
            quotient_bit = "1"
            remainder = sub_result

        quotient = quotient[:-1] + quotient_bit
        trace.append((step, remainder, quotient, sub_result, decision))

    return int(quotient, 2), int(remainder, 2), trace

quotient, remainder, trace = restoring_division(13, 3, 4)

print("13 ÷ 3, 4-বিট Restoring Division")
print("-" * 60)
for step, rem, quo, sub, decision in trace:
    print(f"ধাপ {step}: বিয়োগের ফলাফল={sub}  {decision}")
    print(f"        নতুন remainder={rem}  quotient(এখন পর্যন্ত)={quo}")

print()
print(f"চূড়ান্ত ভাগফল (quotient) = {quotient}")
print(f"চূড়ান্ত ভাগশেষ (remainder) = {remainder}")
print(f"পুনর্গঠন-যাচাই: {quotient} x 3 + {remainder} = {quotient * 3 + remainder}  (মূল dividend 13 হওয়া উচিত)")
assert quotient * 3 + remainder == 13
assert (quotient, remainder) == (13 // 3, 13 % 3)
print("cross-check (Python // এবং %):", 13 // 3, 13 % 3, "-- MATCH")

print()
print("=== division-by-zero হ্যান্ডলিং ===")
try:
    restoring_division(13, 0, 4)
except ZeroDivisionError as e:
    print(f"সঠিকভাবে রিজেক্ট হলো -> ZeroDivisionError: {e}")