title: 1D Fast Convolution without FFT
body: <p>I need an 1D Convolution against 2 big arrays. I'm using this code in C# but it takes a loooong time to run. </p>
  
  <p>I know, i know! FFT convolutions is very fast. But in this project i CAN'T use it. 
  It is a constraint of the project to not use FFT (please don't ask why :/).</p>
  
  <p>This is my code in C# (ported from matlab, by the way): </p>
  
  <pre><code>var result = new double[input.Length + filter.Length - 1];
  for (var i = 0; i &lt; input.Length; i++)
  {
      for (var j = 0; j &lt; filter.Length; j++)
      {
          result[i + j] += input[i] * filter[j];
      }
  }
  </code></pre>
  
  <p>So, anyone knows any fast convolution algorithm widthout FFT? </p>