fast_multiplication.cpp

#include <bits/stdc++.h>
using namespace std;

//given 2 ints (a,b) of bitcount 2n, we can divide the integers into two parts
//a0 = first n bits (0 to n-1), a1 = last n bits (n to 2n-1)
//therefore a = 2^n * a1 + a0 = (a1 << n) + a0
//similarly b = (b1 << n) + b0
//a * b = (2^(2*n) + 2^n)a1 * b1 + (2^n + 1) a0 * b0 + 2^n * (a1 - a0)*(b0 - b1) 

long long fast_multiply(int a, int b, int bitCount) {
    if(bitCount == 1) return a * b;
    int halved = bitCount / 2;
    int a1 = a >> halved;
    int a0 = ((1 << halved) - 1) & a;

    int b1 = b >> halved;
    int b0 = ((1 << halved) - 1) & b;

    long long p1 = fast_multiply(a1, b1, halved);
    long long p2 = fast_multiply(a0, b0, halved);
    long long p3 = fast_multiply( a1-a0 , b0 - b1, halved);
    return (p1 << bitCount) + (p1 << halved) + (p2 << halved) + p2 + (p3 << halved);
}

int main() {
    int p, q, bitCount = 32;
    cin >> p >> q; 
    long long a = fast_multiply(p, q, bitCount);
    cout << a << endl;
}