FFT Conv FLOPs

Problem

Estimate FFT convolution cost: pad to the next power of two n >= signal_len + kernel_len - 1, then flops = 3 * 5 * n * log2(n) (three FFTs) + 6 * n (complex multiplies). For n = 1 the FFT part is zero.

The signature is fft_conv_flops(signal_len, kernel_len). Return an integer.

Hint

FFT convolution only wins for large kernels or very long signals.

Test cases

case 1

in: [1024,3]

expected: 350208

case 2

in: [16,4]

expected: 2592

case 3

in: [7,3]

expected: 1056

case 4

in: [1,1]

expected: 6

case 5

in: [100,1]

expected: 14208

Starter codePython

import math
def fft_conv_flops(signal_len, kernel_len):
    # Your code here
    pass

5 test cases · run your code against them in the editor