Description
Objectives:
1. Find all integers in a given range that are congruent to an integer under some modulo .
2. Find the -representation of a given integer.
3. Apply numerical algorithms for computing the sum of two numbers in binary
representation.
4. Apply numerical algorithms for computing the product of two numbers in binary
representation.
Problem 1:
Complete the function equiv_to(a, m, low, high) that returns a list of all the integers in
the range such that .
EXAMPLES:
Finding all integers such that :
IN: equiv_to(3, 5, -10, 15)
OUT: [-7, -2, 3, 8, 13]
Finding all integers such that :
IN: equiv_to(12, 15, -29, -11)
OUT: [-18]
Finding all integers such that :
IN: equiv_to(-20, 4, 3, 21)
OUT: [4, 8, 12, 16, 20]
a m
b
x
[low, high] x ≡ a (mod m)
−10 ≤ x ≤ 15 x ≡ 3 (mod 5)
−29 ≤ x ≤ −11 x ≡ 3 (mod 5)
3 ≤ x ≤ 21 x ≡ −20 (mod 4)
HINT:
By definition, all integers that are equivalent to under modulo must satisfy that
Hence,
Notice that if all the values must to be in the range , then
What lower- and upper-bound does this place on ? How do these -values allow us to find the
goal -values?
Problem 2:
Complete the function b_rep(n, b) that computes the base -representation of an integer
n given in decimal representation (i.e. typical base 10 representation). Your implementation
must use ALGORITHM 1.2.1 of the “Integer Representations & Algorithms” lecture notes.
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 base -representation. For example, the
function implementation can not use the functions bin() or int(a, base=2) .
The function should satisfy the following:
1. INPUT:
n – a positive integer representing a number in decimal representation
b – an integer representing the desired base
1. OUTPUT:
a string containing the -expansion of integer a .
EXAMPLES:
IN: b_rep(10, 2)
OUT: 1010
IN: b_rep(10, 8)
x a m
x − a = m ⋅ k for some integer k
x = mk + a
x [low, high]
low ≤ mk + a ≤ high
k k
x
In [ ]:
def equiv_to(a, m, low, high):
k_low = # FIXME: update k_low
k_high = # FIXME: update k_high
k_vals = list(range(k_low, k_high +1))
x_vals = # FIXME: update x_vals
return x_vals
b
b
b
OUT: 12
IN: b_rep(10, 16)
OUT: A
Problem 3:
Complete the function binary_add(a, b) that computes the sum of the binary numbers
and
using ALGORITHM 1.2.3 of the “Integer Representations & Algorithms” lecture notes.
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:
1. INPUT:
a – a string of the 0’s and 1’s that make up the first binary number. Assume the string
contains no spaces.
b – a string of the 0’s and 1’s that make up the second binary number. Assume the
string contains no spaces.
1. OUTPUT:
the string of 0’s and 1’s that is the result of computing .
EXAMPLE:
IN: binary_add( ‘101011’ , ‘11011’) In [22]:
def b_rep(n, b):
digits = [] # stores the digits of the b-expansion
q = n
while q != 0:
digit = # FIXME: Update digit
if b == 16 and digit > 9:
hex_dict = {10: ‘A’, 11 : ‘B’, 12: ‘C’, 13: ‘D’, 14: ‘E’, 15 : ‘F’}
digit = # FIXME: Update digit
digits.append(digit)
q = # FIXME: Update q
return # FIXME: Return the string of digits
a = (ai−1
, ai−2
,…, a0)2
b = (bj−1
, bj−2
,…, b0)2
a + b
OUT: ‘1000110’
Problem 4:
Complete function binary_mul(a, b) that computes the product of the binary numbers
and
using ALGORITHM 1.2.4 of the “Integer Representations & Algorithms” lecture notes. No credit
will be given to functions that employ any other implementation. The function can not use builtin 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:
1. INPUT:
a – a string of the 0’s and 1’s that make up the first binary number. Assume the string
contains no spaces.
b – a string of the 0’s and 1’s that make up the second binary number. Assume the
string contains no spaces. In [42]:
def binary_add(a, b):
# removing all whitespace from the strings
a = a.replace(‘ ‘, ”)
b = b.replace(‘ ‘, ”)
# padding the strings with 0’s so they are the same length
if len(a) < len(b):
diff = len(b) – len(a)
a = “0” *diff + a
elif len(a) > len(b):
diff = len(a) – len(b)
b = “0” *diff + b
# addition algorithm
result = “”
carry = 0
for i in reversed(range(len(a))):
a_i = int(a[i])
b_i = int(b[i])
result += # FIXME: Update result
carry = # FIXME: Update carry
if carry == 1:
result += # FIXME: Update result
return # FIXME return the appropriate string
a = (ai−1, ai−2,…, a0)2
b = (bj−1, bj−2,…, b0)2
1. OUTPUT:
the string of 0’s and 1’s that is the result of computing .
EXAMPLE:
IN: binary_mul( ‘101011’ , ‘11011’)
OUT: ‘10010001001’
a × b
In [75]:
def binary_mul(a, b):
# removing all whitespace from the strings
a = a.replace(‘ ‘, ”)
b = b.replace(‘ ‘, ”)
# multiplication algorithm
partial_products = []
i = 0 # tracks the index of the current binary bit of string ‘a’ beginning at 0, r
for bit in reversed(a):
if bit == ‘1’:
partial_products.append(“””FIXME: Append the correct object to partial pro
i += 1
result = ‘0’
while len(partial_products) > 0:
result = binary_add(“FIXME: Input the correct arguments”)
del partial_products[0]
return # FIXME: Return the appropriate result
