# Polynomial multiplication using Karatsuba method

I am trying to solve a problem, which requires me to output the xor of all coefficients in the product of 2 input polynomials. Having seen that the normal O(n^2) multiplication is not optimal, I tried to accomplish the same task by using the Karatsuba method which is equivalent to the one for numbers. It turned out that my code ran even slower in practice than the O(n^2) one, even though it gave me the correct answer.

#include <bits/stdc++.h>

using namespace std;

// In ra đa thức
// Print the polynomial coefficient
void print(vector<int> a) {
for (int &i: a) cout << i << " ";
cout << endl;
}

// Lũy thừa bậc 2 tiếp theo của 1 số
// The next power of 2 of a number
int nextPowerOf2(int n)
{
n--;
n |= n >> 1;
n |= n >> 2;
n |= n >> 4;
n |= n >> 8;
n |= n >> 16;
n++;
return n;
}

// Đưa 2 đa thức về cùng bậc, trả về bậc chung
// Make 2 polynomials to have the same degree
int equalize(vector<int> &a, vector<int> &b) {
int x = a.size(), y = b.size();
if (x > y) {
b.resize(x);
return x;
}
else if (x < y) {
a.resize(y);
return y;
}
return x;
}

// Loại bỏ các hệ số đa thức bậc cao nhất bằng 0
// Remove the highest degree coefficients which are equal
void cuttail(vector<int> &a) {
while (a.back() == 0)
a.pop_back();
}

// Hàm tính tổng 2 đa thức
// Sum of 2 polynomials
vector<int> sum(vector<int> a, vector<int> b) {
int deg = equalize(a, b);
vector<int> c(deg);
for (int i = 0; i < deg; i++)
c[i] = a[i] + b[i];
return c;
}

// Hàm tính hiệu 2 đa thức
// Difference of 2 polynomials
vector<int> diff(vector<int> a, vector<int> b) {
int deg = a.size();
vector<int> c(deg);
for (int i = 0; i < deg; i++)
c[i] = a[i] - b[i];
return c;
}

// Hàm tính tích 2 đa thức
// Product of 2 polynomials
vector<int> prod(vector<int> a, vector<int> b) {
int deg = a.size();
int hdeg = deg/2;
if (deg == 1) return {a * b};
vector<int> a1(hdeg), a2(hdeg), b1(hdeg), b2(hdeg), v(deg), u(deg), w(deg*2);
for (int i = 0; i < deg/2; i++) {
a1[i] = a[i];
b1[i] = b[i];
a2[i] = a[i + hdeg];
b2[i] = b[i + hdeg];
}
u = prod(a1, b1);
v = prod(a2, b2);
w = prod(sum(a1, a2), sum(b1, b2));
w = diff(diff(w, u), v);
vector<int> wdeg(hdeg, 0), vdeg(deg, 0);
w.insert(w.begin(), wdeg.begin(), wdeg.end());
v.insert(v.begin(), vdeg.begin(), vdeg.end());
return sum(u, sum(w, v));
};

int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int n, m;
cin >> n;
vector<int> a(n+1);
for (int &i: a)
cin >> i;
cin >> m;
vector<int> b(m+1);
for (int &i: b)
cin >> i;
int deg = nextPowerOf2(equalize(a, b));
a.resize(deg);
b.resize(deg);
vector<int> c = prod(a, b);
cuttail(c);
int result = 0;
for (int i: c)
result = result ^ i;
cout << result;
return 0;
}


I highly doubted that the vector allocation is behind the slow speed of multiplication, but I don't know how to fix it. I would appreciate if you can take a look at my code and give me some idea to improve it.

EDIT: As requested, I have a test case given here:

3 83 86 77 15

4 93 35 86 92 49

The 2 input polynomials are in the degree of 3 and 4 respectively: $$83 + 86x + 77x^2 + 15x^3$$ and $$93 + 35x + 86x^2 + 92x^3 + 49x^4$$ The output is 20731, which is the xor of all coefficients of the product of 2 input polynomials above (7719 xor 10903 xor 17309 xor 19122 xor 19126 xor 12588 xor 5153 xor 735 = 20731)

• @pacmaninbw Thank you a lot. This is an optional self-research homework for in my Programming Technique class, which is provided by my teacher who is involved in training teams for competitive programming competitions. I guess that's why the problem looks like a coding challenge. Unfortunately, the problem is not written in English, so I provided a brief description of the problem in the question above Oct 2 '20 at 17:58
• Can you provide some examples for ease of testing? Oct 3 '20 at 1:22
• @L.F. Yes, the first input polynomial is 3 83 86 77 15 (degree 3, with 4 coefficients from the lowest degree to the highest degree). The second input polynomial is 4 93 35 86 92 49. I have to output 20731, which is 7719 xor 10903 xor 17309 xor 19122 xor 19126 xor 12588 xor 5153 xor 735 = 20731 (xor of all coefficients in the product polynonimal) Oct 3 '20 at 1:26
• Thanks. You can edit the question to present the data in the required format. Oct 3 '20 at 1:27
• turned out that my code ran even slower in practice than the O(n^2) one as in where the n² algorithm took 2 hours, my Karatsuba implementation overtaxed my patience? The cross-over points are pretty high in integer multiplication; eye-balling the overhead, I'd not expect them to be lower here. Padding may not be the best idea. I somehow doubt int is appropriate for the product coefficients when the degree is high enough to warrant use of Karatsuba's. Oct 3 '20 at 6:26

# Algorithmic complexity is not a good indicator of real-world performance

When you have to choose between an $$\\mathcal{O}(N^2)\$$ or $$\\mathcal{O}(N^{1.58})\$$ algorithm, you would think that the latter is faster, however that is only true for sufficiently large values of $$\N\$$. In practice, unless you have more than a thousand digits to multiply, the simple $$\\mathcal{O}(N^2)\$$ algorithm is faster.

# Don't make the inputs of equal length

If you want to multiply a polynomial of degree 100 with a polynomial of degree 1, then your program will expand the latter polynomial to degree 100, and then do the multiplication. But most of the work is now wasted on multiplying things by 0. Try to make your algorithm work for vectors of different lengths.

# Avoid creating unnecessary intermediate results

If the goal is purely to get the XOR of the coefficients of the product, then you don't actually need to store the product before calculating the final result of the XORs. Instead, with a trivial algorithm, you can just simply do:

int result{};
for (auto i: a)
for (auto j: b)
result ^= i * j;


This avoids creating a temporary vector, which requires heap memory allocation, and avoids an additional pass over the temporary result to get the final answer. Again, this doesn't reduce algorithmic complexity, but it does reduce how many cycles you have to spend for each iteration of the $$\\mathcal{O}(N^2)\$$ algorithm even further.

# Use a hybrid approach

In your implementation of Karatsuba's algorithm, you have this line:

if (deg == 1) return {a * b};


Knowing that for smaller vectors, a naive algorithm is actually faster, you can replace this line with:

if (deg < CUTOFF)
return naive_product(a, b);


Where you set the constant CUTOFF to some value that you have to determine experimentally. This approach is similar to those taken by state-of-the-art sorting algorithms, which typically also use a divide-and-conquer approach and when the problem gets small enough, they will use insertion sort.

# Pass vectors by const reference

Most of your functions like prod(), sum(), and so on, take parameters by value. This is very inefficient, since it means a copy of the vectors used as input arguments will be made. Pass them by const reference instead, it's as simple as:

vector<int> sum(const vector<int> &a, const vector<int> &b) {
...
}

• Thanks for your comment. Yes, except for the given test, I was given that there are 5 hidden tests with the ith test having 2 polynomials of degree 10^i, so Karatsuba is the solution I thought that is appropriate here. I have an issue here: I did think about avoiding to create intermediate results, but it is the fact that (a + b) XOR c is not equal to a XOR c + b XOR c, so I really can't think of a better solution Oct 3 '20 at 11:27