title: Karatsuba algorithm for multiplication of polynomials
body: <p>I am trying to implement the recursive Karatsuba algorithm for multiplication of two polynomials (of the same degree). My code still doesn't work for polynomials with degree greater than 1. Can anyone explain to me what I am doing wrong in my function? It should work for even and also for odd numbers of coefficients.</p>
  
  <p>The polynomials are stored in an array of <code>long</code>. Every element represents one coefficient, so <code>1 2 3 4</code> means <code>1 + 2x + 3x^2 + 4x^3</code> and the argument <code>size</code> is the number of coefficients.</p>
  
  <pre><code>long* karatsuba(const long *A, const long *B, int size) {
      long *lowA, *highA, *lowB, *highB, *midA, *midB;
  
      if (size == 1)
          return naive(A, B, size, size);
  
      int half = size / 2;
  
      lowA = new long[half];
      lowB = new long[half];
      midA = new long[half];
      midB = new long[half];
      highA = new long[half];
      highB = new long[half];
  
      // init low coefficients
      for(int i=0; i&lt;half; i++){
          lowA[i] = A[i];
          lowB[i] = B[i];
      }
  
      // init high // init low coefficients
      for(int i=half; i&lt;size; i++){
          highA[i-half] = A[i];
          highB[i-half] = B[i];
      }
  
      // init mid // init low coefficients
      for(int i=0; i&lt;half; i++){
          midA[i] = lowA[i] + highA[i];
          midB[i] = lowB[i] + highB[i];
      }
  
      long *z0 = karatsuba(lowA, lowB, half);
      long *z1 = karatsuba(midA, midB, half);
      long *z2 = karatsuba(highA, highB, half);
  
      // compute the result
      long *result = new long[2*size-1];
      for(int i=0; i&lt;half; i++){
          result[i + 2*half] = z2[i];
          result[i + half] = z1[i] - z0[i] - z2[i];
          result[i] = z0[i];
      }
      return result;
  }
  </code></pre>
  
  <p>My main problem is that this function doesn't compute the correct results.</p>