Muliply optimised works but not implemented correctly

Hi,

I failed my assignment 3 due to my optimized function implementation. However, my code passed all the tests. There’s no chance a mistake was made no?

While evaluating the notebook, the code is checked in many different private test cases, maybe some of these test cases failed for your code.

Failed mine as well, The code works, but strangely not as efficient as the basic multiply.

``````def multiply_dnc_optimized(poly1, poly2):
if len(poly1) == 0:
return 0
elif len(poly2) == 0:
return 0
if len(poly1) <= 1:
return [poly1[0] * poly2[i] for i in range(len(poly2))]
elif len(poly2) <= 1:
return [poly2[0] * poly1[i] for i in range(len(poly1))]
else:
n = max(len(poly1) , len(poly2))
(poly1_0, poly1_1),(poly2_0, poly2_1) = split(poly1, poly2)
#         print((poly1_0, poly1_1),(poly2_0, poly2_1))

U = multiply_dnc_optimized(poly1_0, poly2_0)

#         print((poly1_0, poly1_1),(poly2_0, poly2_1))
Z = multiply_dnc_optimized(poly1_1, poly2_1)

#         print((poly1_0, poly1_1),(poly2_0, poly2_1))
Y_Z_U = increase_exponent(sub(sub(Y,Z),U),n//2)

for k in range(len(result)-1,0,-1):
if result[k] == 0:
result.pop()
return result
``````

Any hints as to where I’m going wrong ?

Helper functions:

``````def resolve_len(poly1, poly2):
if len(poly1) < len(poly2):
poly1.append(0)
resolve_len(poly1, poly2)
elif len(poly2) < len(poly1):
poly2.append(0)
resolve_len(poly1, poly2)
return poly1,poly2

def sub(poly1, poly2):
"""Subtract two polynomials"""
poly1, poly2 = resolve_len(poly1, poly2)
result = [0] * max((len(poly1), len(poly2)))
for i in range(len(result)):
result[i] = poly1[i] - poly2[i]
return result
``````

Basic test Eval:

``````evaluate_test_cases(multiply_basic2, tests)

TEST CASE #0

Input:
{'poly1': [2, 0, 5, 7], 'poly2': [3, 4, 2, 0]}

Expected Output:
[6, 8, 19, 41, 38, 14]

Actual Output:
[6, 8, 19, 41, 38, 14]

Execution Time:
0.017 ms

Test Result:
PASSED

TEST CASE #1

Input:
{'poly1': [7], 'poly2': [2]}

Expected Output:
[14]

Actual Output:
[14]

Execution Time:
0.007 ms

Test Result:
PASSED

TEST CASE #2

Input:
{'poly1': [1, 3, 5, 7], 'poly2': [1, 3, 5, 7]}

Expected Output:
[1, 6, 19, 44, 67, 70, 49]

Actual Output:
[1, 6, 19, 44, 67, 70, 49]

Execution Time:
0.013 ms

Test Result:
PASSED

TEST CASE #3

Input:
{'poly1': [2, 4, 6, 10], 'poly2': [3, 0, 0, 0]}

Expected Output:
[6, 12, 18, 30]

Actual Output:
[6, 12, 18, 30]

Execution Time:
0.013 ms

Test Result:
PASSED

TEST CASE #4

Input:
{'poly1': [0, 1, 19, 2], 'poly2': [2, 2, 2, 2]}

Expected Output:
[0, 2, 40, 44, 44, 42, 4]

Actual Output:
[0, 2, 40, 44, 44, 42, 4]

Execution Time:
0.011 ms

Test Result:
PASSED

TEST CASE #5

Input:
{'poly1': [1, 2, 3, 4], 'poly2': [0, 0, 0, 0]}

Expected Output:
[0]

Actual Output:
[0]

Execution Time:
0.012 ms

Test Result:
PASSED

SUMMARY

TOTAL: 6, PASSED: 6, FAILED: 0
[([6, 8, 19, 41, 38, 14], True, 0.017),
([14], True, 0.007),
([1, 6, 19, 44, 67, 70, 49], True, 0.013),
([6, 12, 18, 30], True, 0.013),
([0, 2, 40, 44, 44, 42, 4], True, 0.011),
([0], True, 0.012)]
``````

Optimized test eval:

``````evaluate_test_cases(multiply_dnc_optimized, tests)

TEST CASE #0

Input:
{'poly1': [2, 0, 5, 7], 'poly2': [3, 4, 2, 0]}

Expected Output:
[6, 8, 19, 41, 38, 14]

Actual Output:
[6, 8, 19, 41, 38, 14]

Execution Time:
0.07 ms

Test Result:
PASSED

TEST CASE #1

Input:
{'poly1': [7], 'poly2': [2]}

Expected Output:
[14]

Actual Output:
[14]

Execution Time:
0.004 ms

Test Result:
PASSED

TEST CASE #2

Input:
{'poly1': [1, 3, 5, 7], 'poly2': [1, 3, 5, 7]}

Expected Output:
[1, 6, 19, 44, 67, 70, 49]

Actual Output:
[1, 6, 19, 44, 67, 70, 49]

Execution Time:
0.104 ms

Test Result:
PASSED

TEST CASE #3

Input:
{'poly1': [2, 4, 6, 10], 'poly2': [3, 0, 0, 0]}

Expected Output:
[6, 12, 18, 30]

Actual Output:
[6, 12, 18, 30]

Execution Time:
0.151 ms

Test Result:
PASSED

TEST CASE #4

Input:
{'poly1': [0, 1, 19, 2], 'poly2': [2, 2, 2, 2]}

Expected Output:
[0, 2, 40, 44, 44, 42, 4]

Actual Output:
[0, 2, 40, 44, 44, 42, 4]

Execution Time:
0.107 ms

Test Result:
PASSED

TEST CASE #5

Input:
{'poly1': [1, 2, 3, 4], 'poly2': [0, 0, 0, 0]}

Expected Output:
[0]

Actual Output:
[0]

Execution Time:
0.167 ms

Test Result:
PASSED

SUMMARY

TOTAL: 6, PASSED: 6, FAILED: 0
[([6, 8, 19, 41, 38, 14], True, 0.07),
([14], True, 0.004),
([1, 6, 19, 44, 67, 70, 49], True, 0.104),
([6, 12, 18, 30], True, 0.151),
([0, 2, 40, 44, 44, 42, 4], True, 0.107),
([0], True, 0.167)]
``````

Note the ms time for optimized is greater than basic, trying to figure out the way I can decrease it. Appreciate your help in advance.

We can divide and conquer as much as we want, but without a proper threshold (the moment where we stop subdividing further and use basic version) we can even increase execution time.

I’ve decided to let python find suitable threshold for me (tests for polynomials up to x511):

1 Like

Thanks for this. This gives some perspective.

Could you provide the code for the threshold. I tried executing it, but possibly I’m wrong here. Also fixed some bugs in my code regarding the increase_exponent.

``````def multiply_dnc_optimized(poly1, poly2, i=0, threshold=None):
print("=================ith iteration:==================================", i)
i+=1
if len(poly1) == 0:
return 0
elif len(poly2) == 0:
return 0
if len(poly1) == 1:
return [poly1[0] * i for i in poly2]
elif len(poly2) == 1:
return [poly2[0] * i for i in poly1]
else:
n = max(len(poly1) , len(poly2))
(poly1_0, poly1_1),(poly2_0, poly2_1) = split(poly1, poly2)
print((poly1_0, poly1_1),(poly2_0, poly2_1))

U = multiply_dnc_optimized(poly1_0, poly2_0,i)
#print(f"U:{U}")

print((poly1_0, poly1_1),(poly2_0, poly2_1))
Z = multiply_dnc_optimized(poly1_1, poly2_1,i)
#print(f"Z:--->{Z}")

print((poly1_0, poly1_1),(poly2_0, poly2_1))
#print(f"Y:--->{Y}")

Y_Z_U = increase_exponent(sub(sub(Y,Z),U),n//2)
#print(f"Y_Z_U:--->{Y_Z_U}")

# Corrected the issue : Increase exponent was wrong. First calculate floor division by 2 and then square it.
for k in range(len(result)-1,0,-1):
if result[k] == 0:
del result[k]
else:
break
print(f"Result:{result}")
print(f"THRESHOLD : {threshold}")
return result

``````

Threshold is something that is kinda “global” for a function in my case.

In my case I’ve just set `multiply_optimized.basic_threshold` (and obviously used it inside the function) variable to any value I want to test and then ran the tests.

Use timers (actually, peek inside the `evaluate_test_cases` function to see how they do it) to calculate how much it takes to run for specific threshold. In my case I’ve run the basic version only once, because I’ve decided that the test subset won’t change between executions (I think I’ve sampled 500 tests). Test for every threshold you want, pick the fastest one.

I don’t think the function you have now is suitable for any thresholding right now.

I basically had one condition that governed the behavior (and there are no other conditions in this function tbh):

``````if n > multiply_optimized.basic_threshold:
# optimized
else:
# use basic
``````

You would have to modify heavily your solution to account for the threshold, since for now you basically subdivide until one of the polynomials is a scalar (your threshold is 1).

1 Like

I think I may have pasted a different code there [ one submitted for reval ]. But trying out a couple of things for testing the eval times:
Here is the code which includes the threshold parameter. Included the below snippet right before splitting and assigning U, Z, Y.

``````print("Inside DNC:" ,poly1, poly2)
if len(poly1) == 0:
return 0
elif len(poly2) == 0:
return 0
elif len(poly1) <= threshold  or len(poly2)  <= threshold:
return multiply_basic(poly1, poly2)  # Using the same basic function.
``````

Test

``````test0 = {
'input': {
'poly1': [2, 0, 5, 7, 4, 0, 0, 5],
'poly2': [3, 4, 2, 4, 5, 0 ,3]
},
'output': [6, 8, 19, 49, 60, 50, 67, 66, 55, 31, 32, 25, 0, 15]
}
``````

The basic multiplication output for the input polynomials:

``````==========Start test===========
Inside BASIC:  [2, 0, 5, 7, 4, 0, 0, 5] [3, 4, 2, 4, 5, 0, 3, 0]
15
[6, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[6, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[6, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[6, 8, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[6, 8, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[6, 8, 19, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[6, 8, 19, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[6, 8, 19, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[6, 8, 19, 28, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[6, 8, 19, 49, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[6, 8, 19, 49, 10, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[6, 8, 19, 49, 10, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[6, 8, 19, 49, 20, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[6, 8, 19, 49, 48, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[6, 8, 19, 49, 60, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[6, 8, 19, 49, 60, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[6, 8, 19, 49, 60, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[6, 8, 19, 49, 60, 20, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[6, 8, 19, 49, 60, 34, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[6, 8, 19, 49, 60, 50, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[6, 8, 19, 49, 60, 50, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[6, 8, 19, 49, 60, 50, 6, 0, 0, 0, 0, 0, 0, 0, 0]
[6, 8, 19, 49, 60, 50, 6, 0, 0, 0, 0, 0, 0, 0, 0]
[6, 8, 19, 49, 60, 50, 31, 0, 0, 0, 0, 0, 0, 0, 0]
[6, 8, 19, 49, 60, 50, 59, 0, 0, 0, 0, 0, 0, 0, 0]
[6, 8, 19, 49, 60, 50, 67, 0, 0, 0, 0, 0, 0, 0, 0]
[6, 8, 19, 49, 60, 50, 67, 0, 0, 0, 0, 0, 0, 0, 0]
[6, 8, 19, 49, 60, 50, 67, 0, 0, 0, 0, 0, 0, 0, 0]
[6, 8, 19, 49, 60, 50, 67, 0, 0, 0, 0, 0, 0, 0, 0]
[6, 8, 19, 49, 60, 50, 67, 0, 0, 0, 0, 0, 0, 0, 0]
[6, 8, 19, 49, 60, 50, 67, 0, 0, 0, 0, 0, 0, 0, 0]
[6, 8, 19, 49, 60, 50, 67, 35, 0, 0, 0, 0, 0, 0, 0]
[6, 8, 19, 49, 60, 50, 67, 51, 0, 0, 0, 0, 0, 0, 0]
[6, 8, 19, 49, 60, 50, 67, 51, 0, 0, 0, 0, 0, 0, 0]
[6, 8, 19, 49, 60, 50, 67, 51, 0, 0, 0, 0, 0, 0, 0]
[6, 8, 19, 49, 60, 50, 67, 66, 0, 0, 0, 0, 0, 0, 0]
[6, 8, 19, 49, 60, 50, 67, 66, 0, 0, 0, 0, 0, 0, 0]
[6, 8, 19, 49, 60, 50, 67, 66, 0, 0, 0, 0, 0, 0, 0]
[6, 8, 19, 49, 60, 50, 67, 66, 15, 0, 0, 0, 0, 0, 0]
[6, 8, 19, 49, 60, 50, 67, 66, 15, 0, 0, 0, 0, 0, 0]
[6, 8, 19, 49, 60, 50, 67, 66, 35, 0, 0, 0, 0, 0, 0]
[6, 8, 19, 49, 60, 50, 67, 66, 35, 0, 0, 0, 0, 0, 0]
[6, 8, 19, 49, 60, 50, 67, 66, 35, 0, 0, 0, 0, 0, 0]
[6, 8, 19, 49, 60, 50, 67, 66, 55, 0, 0, 0, 0, 0, 0]
[6, 8, 19, 49, 60, 50, 67, 66, 55, 0, 0, 0, 0, 0, 0]
[6, 8, 19, 49, 60, 50, 67, 66, 55, 21, 0, 0, 0, 0, 0]
[6, 8, 19, 49, 60, 50, 67, 66, 55, 21, 0, 0, 0, 0, 0]
[6, 8, 19, 49, 60, 50, 67, 66, 55, 21, 0, 0, 0, 0, 0]
[6, 8, 19, 49, 60, 50, 67, 66, 55, 21, 0, 0, 0, 0, 0]
[6, 8, 19, 49, 60, 50, 67, 66, 55, 31, 0, 0, 0, 0, 0]
[6, 8, 19, 49, 60, 50, 67, 66, 55, 31, 0, 0, 0, 0, 0]
[6, 8, 19, 49, 60, 50, 67, 66, 55, 31, 12, 0, 0, 0, 0]
[6, 8, 19, 49, 60, 50, 67, 66, 55, 31, 12, 0, 0, 0, 0]
[6, 8, 19, 49, 60, 50, 67, 66, 55, 31, 12, 0, 0, 0, 0]
[6, 8, 19, 49, 60, 50, 67, 66, 55, 31, 32, 0, 0, 0, 0]
[6, 8, 19, 49, 60, 50, 67, 66, 55, 31, 32, 0, 0, 0, 0]
[6, 8, 19, 49, 60, 50, 67, 66, 55, 31, 32, 0, 0, 0, 0]
[6, 8, 19, 49, 60, 50, 67, 66, 55, 31, 32, 0, 0, 0, 0]
[6, 8, 19, 49, 60, 50, 67, 66, 55, 31, 32, 25, 0, 0, 0]
[6, 8, 19, 49, 60, 50, 67, 66, 55, 31, 32, 25, 0, 0, 0]
[6, 8, 19, 49, 60, 50, 67, 66, 55, 31, 32, 25, 0, 0, 0]
[6, 8, 19, 49, 60, 50, 67, 66, 55, 31, 32, 25, 0, 0, 0]
[6, 8, 19, 49, 60, 50, 67, 66, 55, 31, 32, 25, 0, 0, 0]
[6, 8, 19, 49, 60, 50, 67, 66, 55, 31, 32, 25, 0, 15, 0]
Actual : [6, 8, 19, 49, 60, 50, 67, 66, 55, 31, 32, 25, 0, 15]
Expected: [6, 8, 19, 49, 60, 50, 67, 66, 55, 31, 32, 25, 0, 15]
==========End test===========

Process returned 0 (0x0)        execution time : 0.415 s

``````

Using optimized: Threshold 4

``````==========Start test===========
Inside DNC: [2, 0, 5, 7, 4, 0, 0, 5] [3, 4, 2, 4, 5, 0, 3]
Inside DNC: [2, 0, 5, 7] [3, 4, 2, 4]
Inside BASIC:  [2, 0, 5, 7] [3, 4, 2, 4]
7
[6, 0, 0, 0, 0, 0, 0]
[6, 8, 0, 0, 0, 0, 0]
[6, 8, 0, 0, 0, 0, 0]
[6, 8, 4, 0, 0, 0, 0]
[6, 8, 4, 0, 0, 0, 0]
[6, 8, 19, 0, 0, 0, 0]
[6, 8, 19, 8, 0, 0, 0]
[6, 8, 19, 8, 0, 0, 0]
[6, 8, 19, 28, 0, 0, 0]
[6, 8, 19, 49, 0, 0, 0]
[6, 8, 19, 49, 0, 0, 0]
[6, 8, 19, 49, 0, 0, 0]
[6, 8, 19, 49, 10, 0, 0]
[6, 8, 19, 49, 38, 0, 0]
[6, 8, 19, 49, 38, 20, 0]
[6, 8, 19, 49, 38, 34, 0]
Inside DNC: [4, 0, 0, 5] [5, 0, 3]
Inside BASIC:  [4, 0, 0, 5] [5, 0, 3, 0]
7
[20, 0, 0, 0, 0, 0, 0]
[20, 0, 0, 0, 0, 0, 0]
[20, 0, 0, 0, 0, 0, 0]
[20, 0, 12, 0, 0, 0, 0]
[20, 0, 12, 0, 0, 0, 0]
[20, 0, 12, 0, 0, 0, 0]
[20, 0, 12, 0, 0, 0, 0]
[20, 0, 12, 0, 0, 0, 0]
[20, 0, 12, 0, 0, 0, 0]
[20, 0, 12, 25, 0, 0, 0]
[20, 0, 12, 25, 0, 0, 0]
[20, 0, 12, 25, 0, 0, 0]
[20, 0, 12, 25, 0, 0, 0]
[20, 0, 12, 25, 0, 0, 0]
[20, 0, 12, 25, 0, 0, 0]
[20, 0, 12, 25, 0, 15, 0]
Inside DNC: [6, 0, 5, 12] [8, 4, 5, 4]
Inside BASIC:  [6, 0, 5, 12] [8, 4, 5, 4]
7
[48, 0, 0, 0, 0, 0, 0]
[48, 24, 0, 0, 0, 0, 0]
[48, 24, 0, 0, 0, 0, 0]
[48, 24, 30, 0, 0, 0, 0]
[48, 24, 30, 0, 0, 0, 0]
[48, 24, 70, 0, 0, 0, 0]
[48, 24, 70, 24, 0, 0, 0]
[48, 24, 70, 24, 0, 0, 0]
[48, 24, 70, 44, 0, 0, 0]
[48, 24, 70, 140, 0, 0, 0]
[48, 24, 70, 140, 0, 0, 0]
[48, 24, 70, 140, 0, 0, 0]
[48, 24, 70, 140, 25, 0, 0]
[48, 24, 70, 140, 73, 0, 0]
[48, 24, 70, 140, 73, 20, 0]
[48, 24, 70, 140, 73, 80, 0]
THRESHOLD : 4
Actual : [6, 8, 19, 49, 60, 50, 67, 66, 55, 31, 32, 25, 0, 15]
Expected: [6, 8, 19, 49, 60, 50, 67, 66, 55, 31, 32, 25, 0, 15]
==========End test===========

Process returned 0 (0x0)        execution time : 0.258 s
``````

Test2:

``````test2 = {
'input': {
'poly1': [1, 3, 5, 7],
'poly2': [1, 3, 5, 7]
},
'output': [1, 6, 19, 44, 67, 70, 49]
}
``````

Using basic

``````==========Start test===========
Inside BASIC:  [1, 3, 5, 7] [1, 3, 5, 7]
7
[1, 0, 0, 0, 0, 0, 0]
[1, 3, 0, 0, 0, 0, 0]
[1, 6, 0, 0, 0, 0, 0]
[1, 6, 5, 0, 0, 0, 0]
[1, 6, 14, 0, 0, 0, 0]
[1, 6, 19, 0, 0, 0, 0]
[1, 6, 19, 7, 0, 0, 0]
[1, 6, 19, 22, 0, 0, 0]
[1, 6, 19, 37, 0, 0, 0]
[1, 6, 19, 44, 0, 0, 0]
[1, 6, 19, 44, 0, 0, 0]
[1, 6, 19, 44, 21, 0, 0]
[1, 6, 19, 44, 46, 0, 0]
[1, 6, 19, 44, 67, 0, 0]
[1, 6, 19, 44, 67, 35, 0]
[1, 6, 19, 44, 67, 70, 0]
Actual : [1, 6, 19, 44, 67, 70, 49]
Expected: [1, 6, 19, 44, 67, 70, 49]
==========End test===========

Process returned 0 (0x0)        execution time : 0.192 s
``````

Using optimized: Threshold = 2

``````==========Start test===========
Inside DNC: [1, 3, 5, 7] [1, 3, 5, 7]
Inside DNC: [1, 3] [1, 3]
Inside BASIC:  [1, 3] [1, 3]
3
[1, 0, 0]
[1, 3, 0]
[1, 6, 0]
[1, 6, 0]
Inside DNC: [5, 7] [5, 7]
Inside BASIC:  [5, 7] [5, 7]
3
[25, 0, 0]
[25, 35, 0]
[25, 70, 0]
[25, 70, 0]
Inside DNC: [6, 10] [6, 10]
Inside BASIC:  [6, 10] [6, 10]
3
[36, 0, 0]
[36, 60, 0]
[36, 120, 0]
[36, 120, 0]
THRESHOLD : 2
Actual : [1, 6, 19, 44, 67, 70, 49]
Expected: [1, 6, 19, 44, 67, 70, 49]
==========End test===========

Process returned 0 (0x0)        execution time : 0.208 s
``````

Using optimized Threshold= 3

``````==========Start test===========
Inside DNC: [1, 3, 5, 7] [1, 3, 5, 7]
Inside DNC: [1, 3] [1, 3]
Inside BASIC:  [1, 3] [1, 3]
3
[1, 0, 0]
[1, 3, 0]
[1, 6, 0]
[1, 6, 0]
Inside DNC: [5, 7] [5, 7]
Inside BASIC:  [5, 7] [5, 7]
3
[25, 0, 0]
[25, 35, 0]
[25, 70, 0]
[25, 70, 0]
Inside DNC: [6, 10] [6, 10]
Inside BASIC:  [6, 10] [6, 10]
3
[36, 0, 0]
[36, 60, 0]
[36, 120, 0]
[36, 120, 0]
THRESHOLD : 3
Actual : [1, 6, 19, 44, 67, 70, 49]
Expected: [1, 6, 19, 44, 67, 70, 49]
==========End test===========

Process returned 0 (0x0)        execution time : 0.174 s
``````

Makes sense now. It depends on the length of the subproblem size and the decision to use the recursion further or not.

Thanks much @Sebgolos

1 Like

Your thresholds seem to be quite low compared to what I got. I have a feeling you’re providing them per-test.
What I did is to use a bit more generalized threshold (I’ve literally produced thousands of tests using `multiply_basic` with lengths varying from 0 to 512 elements for a polynomial). So in my case the threshold is kinda “use it for any case and you should be ok” (or at least when you know that polynomials can have 0 to 512 elements).