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 &lt;bits/stdc++.h&gt;

using namespace std; 

// In ra đa thức
// Print the polynomial coefficient
void print(vector&lt;int&gt; a) {
    for (int &amp;i: a) cout &lt;&lt; i &lt;&lt; &quot; &quot;;
    cout &lt;&lt; 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 &gt;&gt; 1; 
    n |= n &gt;&gt; 2; 
    n |= n &gt;&gt; 4; 
    n |= n &gt;&gt; 8; 
    n |= n &gt;&gt; 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&lt;int&gt; &amp;a, vector&lt;int&gt; &amp;b) {
    int x = a.size(), y = b.size();
    if (x &gt; y) {
        b.resize(x);
        return x;
    }
    else if (x &lt; 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&lt;int&gt; &amp;a) {
    while (a.back() == 0)
        a.pop_back();
}

// Hàm tính tổng 2 đa thức
// Sum of 2 polynomials
vector&lt;int&gt; sum(vector&lt;int&gt; a, vector&lt;int&gt; b) {
    int deg = equalize(a, b);
    vector&lt;int&gt; c(deg);
    for (int i = 0; i &lt; 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&lt;int&gt; diff(vector&lt;int&gt; a, vector&lt;int&gt; b) {
    int deg = a.size();
    vector&lt;int&gt; c(deg);
    for (int i = 0; i &lt; 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&lt;int&gt; prod(vector&lt;int&gt; a, vector&lt;int&gt; b) {
    int deg = a.size();
    int hdeg = deg/2;
    if (deg == 1) return {a[0] * b[0]};
    vector&lt;int&gt; a1(hdeg), a2(hdeg), b1(hdeg), b2(hdeg), v(deg), u(deg), w(deg*2);
    for (int i = 0; i &lt; 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&lt;int&gt; 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 &gt;&gt; n;
    vector&lt;int&gt; a(n+1);
    for (int &amp;i: a)   
        cin &gt;&gt; i;
    cin &gt;&gt; m;
    vector&lt;int&gt; b(m+1);
    for (int &amp;i: b)
        cin &gt;&gt; i;
    int deg = nextPowerOf2(equalize(a, b));
    a.resize(deg); 
    b.resize(deg);
    vector&lt;int&gt; c = prod(a, b);
    cuttail(c);
    int result = 0;
    for (int i: c) 
        result = result ^ i;
    cout &lt;&lt; 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)
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[0] * b[0]};

Knowing that for smaller vectors, a naive algorithm is actually faster, you can replace this line with:
if (deg &lt; 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&lt;int&gt; sum(const vector&lt;int&gt; &amp;a, const vector&lt;int&gt; &amp;b) {
    ...
}