I need some help over here on assignment 3 optimized algorithm

here is my main multiply function:
def multiply_optimized(poly1, poly2):
m,n = len(poly1),len(poly2)
if m ==1:
return [poly1[0]*poly2[i] for i in range(n)]
elif n == 1:
return [poly2[0]*poly1[i] for i in range(m)]
else:
n = max(m,n)
a,b = split(poly1, poly2)
a0,a1,b0,b1 = a[0],a[1],b[0],b[1]
u = multiply_optimized(a0,b0)
z = multiply_optimized(a1,b1)
y = multiply_optimized(add(a0,a1), add(b0,b1))
x = minus(minus(y, u),z)
pro = add(add(u, increase_exponent(x, n//2)), increase_exponent(z,n))
return pro

and i have written another function to subtract 2 polynomials that is:
def minus(poly1, poly2):
“”“Add two polynomials”""
result = [0] * max(len(poly1), len(poly2))
for i in range(len(result)):
if i > len(poly2)-1:
result[i] = poly1[i] - result[i]
else:
result[i] = poly1[i]-poly2[i]
return result

on giving the poly1 = [1,1] poly2 = [1,1] inputs the function gives [1, 4, 1] output.

can you tell me where i have done the mistake in the function? thanks.

Hey…

When I am running the code for poly1 = [1,1] and poly2 = [1, 1], I am getting [1, 2, 1] as output which is the correct output and Also I think your code is good but you just have to add the case for [] empty array…
Also in increase_exponent(z, n) you have to do n // 2 * 2 to go through the cases of odd length polynomial…

Read Here…

Also, go through this discussion as many of the problems are already solved…but don’t hesitate to ask if you are stuck…

yes i have corrected my code by using n//2n in the a1b1 part and it is working properly now but still i have not passed it my code is now this,
def multiply_optimized(poly1, poly2):
m,n = len(poly1),len(poly2)
if m == 0 and n == 0:
return [0]
if m == 0 or n == 0:
return [0]*max(m,n)
if m == 1:
return [poly1[0]*poly2[i] for i in range(n)]
elif n == 1:
return [poly2[0]poly1[i] for i in range(m)]
else:
x = max(m,n)
a,b = split(poly1, poly2)
a0,a1,b0,b1 = a[0],a[1],b[0],b[1]
#print(a0,a1,b0,b1)
u = multiply_optimized(a0,b0)
v = increase_exponent(multiply_optimized(a0, b1),x//2)
w = increase_exponent(multiply_optimized(a1, b0),x//2)
z = increase_exponent(multiply_optimized(a1,b1),2
x//2)
y = add(v,w)
#print(u,v,w,z)
pro = add(add(u,y),z)
return pro

and it is not passing all evaluation tests such as test#13, test#15, 16, 17, 18, 19. i dont know why…

Suppose you get polynomial as [] and [1, 2, 3]
In this case, your code will give [0, 0, 0]
But we don’t need any trailing zeroes so our result should be [].

Also for a case like [] and [] your code would give [0] and we need it to be [].

So please make corrections to the code…

Hope it helps