**************PYTHON PSEUDOCODE gassmultiply.py******************** def split(x,
ID: 3667382 • Letter: #
Question
**************PYTHON PSEUDOCODE gassmultiply.py********************
def split(x, n):
left = x >> n//2
right = x - (left << n//2)
return left, right
def multiply(x, y):
xbits = x.bit_length()
ybits = y.bit_length()
n = max(xbits, ybits)
limit = 32
if n <= limit: return x * y
xl, xr = split(x, n)
yl, yr = split(y, n)
r1 = multiply(xl, yl)
r3 = multiply(xr, yr)
r2 = multiply(xl+xr, yl+yr)-r1-r3
n2 = n/2
return (r1 << (2*n2)) + (r2 << n2) + r3
*******************************************
For the following problems, x and y are 132-bit numbers. Your task is to analyze the best-case and the worst-case behavior of this algorithm as follows:
(a) What is the minimum number of calls to multiply(function) performed by this algorithm? (Include original call to multiply(x,y) in your count)
(b) Find an example of 132-bit numbers x and y such that the algorithm uses only this minimum number of calls
(c) What is the maximum number of calls to multiply(function) performed by this algorithm? (Include the original call to multiply(x,y) in your count)
(d) Again, find an example.
Explanation / Answer
(a)
since in the function ,, we have three recursive calling areas
So each one call 3 times .. so 3x3 = 9
Including first call itself, totally 10
(b)
Least 132 bit number to be sent for minimum calls are (1,1) respectively.
(c)
Maximum number of calls would be ..
3 x (limit) + 1
since we are stopping loop if it reached limit
So
===> 3 x 32 + 1 = 97
(d) Max calls --> 132 bit number to be sent are (2^132, 2^132)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.