F.1 Stuck on function

Codebook
1

Can I have a hint as to where I am going wrong with this function?

List item

def fft_multiplication(poly_a, poly_b):
“”"Returns the result of multiplying two polynomials

Args:
    poly_a (array[complex]): 1-D array of coefficients 
    poly_b (array[complex]): 1-D array of coefficients 

Returns: 
    array[complex]: complex coefficients of the product
        of the polynomials
"""
##################
# YOUR CODE HERE #
################## 

# Calculate the number of values required
calcreq = len(poly_a) + len(poly_b) + 1
# Figure out the nearest power of 2
near2 = nearest_power_of_2(calcreq)
# Pad zeros to the polynomial
poly_a = np.pad(poly_a, (0, near2-len(poly_a)))
poly_b = np.pad(poly_b, (0,near2-len(poly_b)))
# Convert the polynomials to value representation 
ca = coefficients_to_values(poly_a)
cb = coefficients_to_values(poly_b)
# Multiply
cc = np.multiply(ca,cb)
# Convert back to coefficient representation
return values_to_coefficients(cc)
2

Hey @simsaidan! We’re happy to see that you’re using the codebook :slight_smile:

I would double check your calculation for the degree of the resulting polynomial (i.e., your calcreq variable) :grin:

3

I have almost the exact code, except for the definition of near2 and the return value

# Calculate the number of values required
calcreq = len(poly_a) + len(poly_b) + 1
# Figure out the nearest power of 2
near2 = nearest_power_of_2(calcreq+1)
# Pad zeros to the polynomial
poly_a = np.pad(poly_a, (0, near2-len(poly_a)))
poly_b = np.pad(poly_b, (0,near2-len(poly_b)))
# Convert the polynomials to value representation 
ca = coefficients_to_values(poly_a)
cb = coefficients_to_values(poly_b)
# Multiply
cc = np.multiply(ca,cb)
# Convert back to coefficient representation
return values_to_coefficients(cc) [0:calcreq-1]

I checked several times with different polynomials in a separate file and the code outputs the correct answer. However, in the codebook, I get the error

Error: operands could not be broadcast together with shapes (5,) (4,)

1 Like
4

The error is still with the calculation for the degree of the resulting polynomial! Let’s just take a step back and work out some things mathematically.

Let’s say I have two polynomials:

f(x) = a + bx + cx^2,

and

g(x) = \alpha + \beta x,

where a, b, c, \alpha, \beta are all real numbers for the sake of the argument. If we’re coding this in the context of this problem in the codebook,

len(f) = 3
len(g) = 2

Let’s multiply f and g:

\begin{align*} h(x) = f(x) \times g(x) & = \alpha (a + bx + cx^2) + \beta x (a + bx + cx^2) \\ & = \alpha a + (\alpha b + \beta a)x + (\alpha c + \beta b)x^2 + \beta c x^3 \end{align*}

This new polynomial h has len(h) = 4.

Now in your code that you posted,

len(h) = len(f) + len(g) + 1

this won’t give len(h) = 4! You’re going to get len(h) = 3 + 2 + 1 = 6, which is not correct. You just need to change how you’re calculating this quantity slightly to get the correct answer :).