Manish Sharma

Apr 1, 2021

5 min read

Polynomial Multiplication

A divide and conquer approach using Karatsuba’s method

Photo by Chris Liverani on Unsplash
  • If you multiply A(x) and B(x) without the optimization as done in the last step, you would end up with 4 terms which is basically the same thing I talked about at the beginning — the naive or elementary approach to multiplication, we have been doing since our elementary math class in school — having the complexity O(n²)
  • We will get to that in a moment…
 // A[] represents coefficients
// of first polynomial
// B[] represents coefficients
// of second polynomial
// m and n are sizes of A[] and B[] respectively
static int[] multiply(int A[], int B[],
int m, int n) {
int[] prod = new int[m + n - 1]; // Initialize the product polynomial for (int i = 0; i < m + n - 1; i++){
prod[i] = 0;
}
// Multiply two polynomials term by term
// Take ever term of first polynomial
for (int i = 0; i < m; i++){ // Multiply the current term of first polynomial
// with every term of second polynomial.
for (int j = 0; j < n; j++){
prod[i + j] += A[i] * B[j];
}
} return prod; }
private double[] karatsubaMultiplyRecursive(double[] multiplicand, double[] multiplier) {double[] product = new double[2 * multiplicand.length];// Handle the base case where the polynomial has only one                                                                     coefficient                         if (multiplicand.length == 1) {                              product[0] = multiplicand[0] * multiplier[0];                                   return product;                         
}
int halfArraySize = multiplicand.length / 2;

// Declare arrays to hold halved factors
double[] multiplicandLow = new double[halfArraySize]; double[] multiplicandHigh = new double[halfArraySize]; double[] multipliplierLow = new double[halfArraySize]; double[] multipliierHigh = new double[halfArraySize]; double[] multiplicandLowHigh = new double[halfArraySize]; double[] multipliplierLowHigh = new double[halfArraySize];// Fill in the low and high arraysfor (int halfSizeIndex = 0; halfSizeIndex < halfArraySize; ++halfSizeIndex) { multiplicandLow[halfSizeIndex] = multiplicand[halfSizeIndex];

multiplicandHigh[halfSizeIndex] = multiplicand[halfSizeIndex + halfArraySize];

multiplicandLowHigh[halfSizeIndex] =
multiplicandLow[halfSizeIndex] +
multiplicandHigh[halfSizeIndex];

multipliplierLow[halfSizeIndex] = multiplier[halfSizeIndex];
multipliierHigh[halfSizeIndex] = multiplier[halfSizeIndex + halfArraySize]; multipliplierLowHigh[halfSizeIndex] = multipliplierLow[halfSizeIndex] + multipliierHigh[halfSizeIndex]; } // Recursively call method on smaller arrays and construct the low and high parts of the productdouble[] productLow = karatsubaMultiplyRecursive(multiplicandLow, multipliplierLow); double[] productHigh = karatsubaMultiplyRecursive(multiplicandHigh, multipliierHigh); double[] productLowHigh = karatsubaMultiplyRecursive(multiplicandLowHigh, multipliplierLowHigh); //Construct the middle portion of the product double[] productMiddle = new double[multiplicand.length]; for (int halfSizeIndex = 0; halfSizeIndex < multiplicand.length; ++halfSizeIndex) { productMiddle[halfSizeIndex] = productLowHigh[halfSizeIndex] -
productLow[halfSizeIndex] - productHigh[halfSizeIndex]; }
// Assemble the product from the low, middle and high parts. Start with the low and high parts of the product. for (int halfSizeIndex = 0, middleOffset = multiplicand.length / 2; halfSizeIndex < multiplicand.length; ++halfSizeIndex) { product[halfSizeIndex] += productLow[halfSizeIndex];
product[halfSizeIndex + multiplicand.length] +=
productHigh[halfSizeIndex];
product[halfSizeIndex + middleOffset] +=
productMiddle[halfSizeIndex];
}
return product; }
  • For the partitioning of the polynomial, we would try to have equal terms for A1 and A0 but for odd number of terms, have more terms for A1 — Similar partitioning for B
  • Normalize: we need to make sure that the degree of both the polynomials is made equal by padding the “shorter” polynomial with 0’s as the coefficients for the higher powers that are missing