c# - 没有 FFT 的一维快速卷积

Question

我需要一个针对 2 个大数组的一维卷积。我在 C# 中使用此代码，但运行它需要很长时间。

我知道，我知道! FFT 卷积非常快。但是在这个项目中我不能使用它。不使用FFT是项目的一个约束(请不要问为什么:/)。

这是我在 C# 中的代码(顺便说一句，从 matlab 移植而来):

var result = new double[input.Length + filter.Length - 1];
for (var i = 0; i < input.Length; i++)
{
    for (var j = 0; j < filter.Length; j++)
    {
        result[i + j] += input[i] * filter[j];
    }
}

那么，有谁知道任何快速卷积算法 widthout FFT 吗？

Answer 1

卷积在数值上与具有额外环绕步骤的多项式乘法相同。因此，所有的多项式和大整数乘法算法都可以用来进行卷积。

FFT 是获得快速 O(n log(n)) 运行时间的唯一方法。但是您仍然可以使用像 Karatsuba's algorithm 这样的分而治之的方法来获得次二次运行时间。 .

一旦您理解了 Karatsuba 的算法，它的工作原理就相当容易实现。它在 O(n^1.585) 中运行，并且可能比尝试 super 优化经典 O(n^2) 方法更快。