# ---
# jupyter:
#   jupytext:
#     text_representation:
#       extension: .py
#       format_name: light
#       format_version: '1.5'
#       jupytext_version: 1.14.4
#   kernelspec:
#     display_name: Python 3
#     language: python
#     name: python3
# ---

# ## 1. Integer Multiplication

# ![Integer Multiplication](images/integer-multiplication.PNG)

def MSB(num):
    "Compute most significant bit of a binary number."
    assert((1 << 32) > num)
    n = 32
    while n >= 0:
        if ((1 << n) & num) != 0:
            return n + 1
        n -= 1
    return 1 # 


def integer_multiplication_simple(a, b):
    "naive implementation of integer multiplication using divide and conquer."
    n = max(MSB(a), MSB(b))
    if n == 1:
        return a * b
    else:
        if n & 1 == 1:
            n += 1
        half = n // 2
        aR = a % (1 << half)
        aL = a >> half
        bR = b % (1 << half)
        bL = b >> half
        cLL = integer_multiplication_simple(aL, bL)
        cLR = integer_multiplication_simple(aL, bR)
        cRL = integer_multiplication_simple(aR, bL)
        cRR = integer_multiplication_simple(aR, bR)
        A = cLL << n
        B = (cLR + cRL) << half
        C = cRR
        return A + B + C


import random
n = 123456
for _ in range(100):
    a, b = random.randint(1, n), random.randint(1, n)
    assert(integer_multiplication_simple(a, b) == a * b)


# ![Integer Multiplication](images/integer-multiplication-divide.PNG)

def integer_multiplication(a, b):
    "Implementation of integer multiplication using divide and conquer."
    n = max(MSB(a), MSB(b))
    if n == 1:
        return a * b
    else:
        if n & 1 == 1:
            n += 1
        half = n // 2
        aR = a % (1 << half)
        aL = a >> half
        bR = b % (1 << half)
        bL = b >> half
        cLL = integer_multiplication(aL, bL)
        cRR = integer_multiplication(aR, bR)
        cM = integer_multiplication(aL + aR, bL + bR) - cLL - cRR
        A = cLL << n
        B = cM << half
        C = cRR
        return A + B + C


import random
n = 123456
for _ in range(100):
    a, b = random.randint(1, n), random.randint(1, n)
    assert(integer_multiplication(a, b) == a * b)



StarcoderdataJupyterScriptsDedupFiltered