CECS 229: Programming Assignment #1

CECS 229: Programming Assignment #1


Submission Instructions:
To receive credit for this assignment, you must submit to CodePost this file converted to a Python script named pa1.py

Objectives:
Compute the quotient and remainder of two numbers.
Apply numerical algorithms for computing the sum of two numbers in binary representation.
Apply numerical algorithms for computing the modular exponentiation of a positive integer.
Problem 1:
Program a function div_alg(a, d) that computes the quotient and remainder of
a÷d
 
according to the Division Algorithm (THM 4.1.2).

The function should satisfy the following:

INPUT:
a - an integer representing the dividend
d - positive integer representing the divisor
OUTPUT:
a dictionary of the form {'quotient' : q, 'remainder' : r} where q and r are the quotient and remainder values, respectively. The remainder should satisfy,  0≤r<d
 .
EXAMPLE: 

>> div_alg( 101 , 11 )

{'quotient' : 9, 'remainder' : 2}

'''Problem 1 Solution:'''
# Writing a function to compute the quotient and remainder according to the Division Algorithm
def div_alg(a, d: int): # a -> dividend; d(a positive integer) -> divisor
    q = 0  # q -> quotient
    r = abs(a) # r -> remainder in absolute value
    # Running a while loop to compute the quotient and remainder
    while r >= d:
        r -= d
        q += 1
    if a < 0 and r > 0:
        r = d - r
        q = -(q + 1)
    return {'quotient': q, 'remainder': r} # {q = a div d is the quotient, r = a mod d is the remainder}
print(div_alg(10, 3))
print(div_alg(101, 11))
Problem 2:
Program a function binary_add(a, b) that computes the sum of the binary numbers
a=(ai−1,ai−2,…,a0)2
 
and
b=(bj−1,bj−2,…,b0)2
 
using the algorithm discussed in lecture. No credit will be given to functions that employ any other implementation. The function can not use built-in functions that already perform some kind of binary representation or addition of binary numbers. For example, the function implementation can not use the functions bin() or int(a, base=2).

The function should satisfy the following:

INPUT:
a - a string of the 0's and 1's that make up the first binary number. The string may contain spaces.
b - a string of the 0's and 1's that make up the first binary number. The string may contain spaces.
OUTPUT:
the string of 0's and 1's that is the result of computing  a+b
 . The string must be separated by spaces into blocks of 4 characters or less, beginning at the end of the string.
EXAMPLE: 

>> binary_add( '10 1011' , '11011')

'100 0110'

'''Problem 2 Solution:'''
# Writing a function to convert a string binary to numerical binary
def stringBin_to_numBin(bin):
    decimal = 0
    bin = bin[::-1] # Reverses the binary number string
    for i in range(len(bin)): # Iterates through the binary number string
        if bin[i] == '1': # Checks if the current digit is 1
            decimal += 2 ** i  # Computes the decimal value of the binary number
    return decimal # Returns the decimal value of the binary number

# Writing a function to compute the sum of two binary numbers with base-b expansions
def base_expansion(n, b): # n -> integer; b -> base(positive integers with b > 1)
    q = n # q -> dividend that is updated in each iteration
    k = 0 # k -> index of the current coefficient in the base expansion
    exp_result = [] # holds the list of coefficients
    while q != 0:
        a = q % b # a -> coefficient of the base b
        q = q // b # q -> dividend that is updated in each iteration
        exp_result.append(a) # adds coefficient to the list every iteration
        k += 1 # Updates the index of the coefficient
    return exp_result[::-1] # returns the list of coefficients in reverse order

# Writing a function to compute the sum of two binary numbers with base-2 expansions
def binary_add(a, b): # a and b are binary numbers
    # Removes the spaces in the binary numbers
    a = a.replace(' ', '')
    b = b.replace(' ', '')
    # Converts the binary numbers to integers
    a = stringBin_to_numBin(a)
    b = stringBin_to_numBin(b)
    bin_num1 = base_expansion(a, 2) # bin_num1 -> binary number a
    bin_num2 = base_expansion(b, 2) # bin_num2 -> binary number b
    carry = 0 # c -> carry bit
    sum = '' # sum -> sum of the two binary numbers

    # Checks if the length of the binary numbers are equal
    # Adds 0s to the beginning of the shorter binary number
    if len(bin_num1) < len(bin_num2):
        bin_num1 = [0] * (len(bin_num2) - len(bin_num1)) + bin_num1 
    else:
        bin_num2 = [0] * (len(bin_num1) - len(bin_num2)) + bin_num2

    for i in range(0, max(len(bin_num1), len(bin_num2))):
        x = (bin_num1[len(bin_num1) - 1 - i] + bin_num2[len(bin_num2) - 1 - i] + carry) % 2 # Computes the sum of the two binary numbers
        y = (bin_num1[len(bin_num1) - 1 - i] + bin_num2[len(bin_num2) - 1 - i] + carry) // 2 # Computes the carry bit using quotient
        sum = str(x) + sum # Adds/Updates the sum to the sum string
        carry = y # Updates the carry bit
    if carry == 1:
        sum = str(carry) + sum # Adds the carry bit to the sum string if the carry bit is 1

    final_sum = '' # Holds the sum with spaces every 4 digits
    count = 0 # Holds the count of the digits
    for i in range(len(sum) -1, -1, -1): # Iterates through the sum in reverse order
        count += 1 # Increments the count 
        final_sum = str(sum[i]) + final_sum # Adds the current digit to the final sum
        if count % 4 == 0 and i != 0: # Check for the 4th digit 
            final_sum = ' ' + final_sum # Adds a space to the sum every 4 digits
        else: 
            final_sum = final_sum # Does not add a space to the sum

    return final_sum
print(binary_add('100','100'))
print(binary_add('11','100'))
print(binary_add('10111','1100000'))
print(binary_add('1101 1011 1100', '1101 1011 1100'))
1000
111
111 0111
1 1011 0111 1000
Problem 3:
Program a function mod_exp(b, n, m) that computes
bnmodm
 
using the algorithm discussed in lecture. No credit will be given to functions that employ any other implementation. For example, if the function implementation simply consists of b ** n % m, no credit will be given.

The function should satisfy the following:

INPUT:
b - positive integer representing the base
n - positive integer representing the exponent
m - positive integer representing the modulo
OUTPUT:
the computation of  bnmodm
  if b, n, m are positive integers, 0 otherwise.
EXAMPLE: 

>> mod_exp( 3 , 644, 645 )

36

'''Problem 3 Solution:'''
# Writing a function that computes the modular exponentiation of a number
def mod_exp(b, n, m): # b -> base; n -> exponent; m -> modulus (all positive integers)
    result = 1 # result -> the final result of the modular exponentiation
    if b < 0 or n < 0 or m < 0: # Checks if the base, exponent, and modulus are positive integers
        result = 0 # Returns as the result 0 to satisfy the condition
        pass    
    k = bin(n)[2:] # k -> converting the exponent 'n' into binary form using 'bin' without the '0b'
    power = b % m # power -> base to the power of 2
    for i in range(len(k) -1, -1, -1): # Iterates through the binary form of the exponent in reverse order
        if k[i] == '1': # Checks if the current digit is 1
            result = (result * power) % m # Computes the result
        power = (power * power) % m # Computes the power
    return result # result = b^n mod m
print(mod_exp(-89, 1070, 625))
print(mod_exp(9, 6, 2))
print(mod_exp(89, 1149, 538))
print(mod_exp(98, 757, 596))
print(mod_exp(39, 1148, 281))
print(mod_exp(3, 644, 645))
print(mod_exp(11, 644, 645))
0
1
207
160
1
36
1