CODEWITHSUNDEEP
c++algorithmmultiplicationkaratsuba
user8005765
user8005765

Reputation:

Karatsuba algorithm for multiplication of polynomials

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.

The polynomials are stored in an array of long. Every element represents one coefficient, so 1 2 3 4 means 1 + 2x + 3x^2 + 4x^3 and the argument size is the number of coefficients.

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<half; i++){
        lowA[i] = A[i];
        lowB[i] = B[i];
    }

    // init high // init low coefficients
    for(int i=half; i<size; i++){
        highA[i-half] = A[i];
        highB[i-half] = B[i];
    }

    // init mid // init low coefficients
    for(int i=0; i<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<half; i++){
        result[i + 2*half] = z2[i];
        result[i + half] = z1[i] - z0[i] - z2[i];
        result[i] = z0[i];
    }
    return result;
}

My main problem is that this function doesn't compute the correct results.

Upvotes: 1

Views: 3410

Answers (1)

greybeard
greybeard

Reputation: 2467

I noticed one-and-a-half issues concerning correctness:

  1. the index in "the combination loop" is limited to the recursive calls parameter length instead of the result length (almost twice the parameter length)
  2. when the limit is correct, the intermediate results "overlap", necessitating accumulation instead of assignment.

I never used "modern C++" "in anger" - if this works, but leaves you dissatisfied with the code, consider posting your concerns on Code Review.

Upvotes: 0

Related Questions