(Python programing Lnaguage)

All functions must be documented with comments giving a precise specication of what the function is supposed to do. For example: def hasDivisor(n, a, b): # Returns True if and only if there exists a number i # between a and b which is a divisor of n. if a > b: # range is empty return False elif isDivisor(a, n): # n is divisible by a return True else: # recurse on the smaller range a+1 to b return hasDivisor(n, a+1, b)

Part 1 In the last question of Assignment 1, we asked you to multiply two 4-bit numerals by repeated addition. This is not the way computers actually perform integer multiplication, nor is it a particularly efficient algorithm. Instead consider the long multiplication method we have all learned to do by hand in decimal notation, e.g. 1 N 4 2 2 6 7 4 4 2 4 4 8 00 3 2 2 4 The same approach can be applied to binary arithmetic as well, for example to calculate ten (1010 in binary) multiplied by eleven (1011 in binary): 1 0 1 0 x 1 0 1 1 1 0 1 0 1 0 1 0 0 0 0 0 1 0 1 0 1 1 0 1 1 1 0 The answer, 1101110, is indeed one hundred and ten (sixty-four + thirty-two + eight + four + two). 1. Mathematically design an algorithm which, given two binary numerals ArnQm-1...Ajay and bubn-1...babo, computes the binary numeral cp@p-1...61c representing their product. Note that we have not specified a maximum size of these numerals. Your algorithm must follow the same digit-by-digit approach as long multiplication. Right now, do not worry about how the algorithm might be implemented in a programming language! Define it as a mathematical function that can be evaluated manually by a human being. You should express it in terms of basic operations that are possible on sequences of bits, such as single-bit operations, and rearranging, removing, or adding bits. You can also assume that an addition operation is available, so you can take two binary numerals of arbitrary size and get their sum as a binary numeral epp-1...C1C0 = Am@m-1...0120 + bnbn-1 ...babo. To develop this algorithm, you may need to introduce multiple helper func- tions to do simpler tasks; that is part of your job in this question. For each such helper functions you define, you must also provide a mathematically precise specification 2. Prove the correctness of your algorithm and all its helper functions. For the helper functions, this just means proving that for all valid inputs, the output matches your specification. For the multiplication algorithm, correctness means proving that the algo- rithm actually does perform multiplication. Recall that a binary numeral am@m-1...ajay represents the natural number 27, 2" am. So, you have to prove that if your algorithm applied to two binary numerals am@m-1...0720 and bubn-1...bybo computes the binary numeral cpcp-1...Cico, then = 2C; = (51 2'ai) (>> mul4((False, True, False, True), (True, True, False, True)) (False, True, True, True, False, True, True, False) In your program, you are allowed to use logical Boolean operators (and, or, not), equality testing (==, !=), conditional statements (if, elif, else), tuples, functions, and recursion. You can also reuse your functions from i=1 = Part 2 Now we that we have designed the algorithm, we should also analyze its computa- tional complexity. 4. Determine the time and space complexity of the algorithm you designed in Question 1. Your answer should be in big O notation, and should depend on m and n, the lengths of the input numerals am@m-1 ... 214, and bubn-1 ... bubo. For the time complexity, consider only the time required for single-bit oper- ations, such as addition of three bits, multiplication of two bits, checking whether a bit is 0 or 1, etc. You may assume that each such operation takes one unit of time, and that rearranging, adding, or removing bits from a numeral does not require additional time. For the space complexity, assume that each bit requires one unit of space, so storing an m-bit numeral amam-1... 21atakes m space. Note that to complete the analysis, you may also need to analyze the time and space complexity analysis of binary addition. You should clearly state what addition algorithm you are considering here. You do not need to prove its correctness. 5. Traditionally when performing long multiplication, we first compute all the intermediate products (e.g. the numbers 744 and 248 in the decimal example on page 2) and then add them up afterwards. Instead, we could iteratively add up each product as soon as we compute it. (a) Redesign your algorithm using this iterative approach, so that it re- quires no deferred additions. (b) Implement this iterative algorithm as a Python function mul41(a,b). 4