FAST C/C++ Implementation of the Karatsuba Multiplication algorithm.Fast Multiplication of 2 integers using Karatsuba Algorithm as a part of practice.

karatsuba.cpp

#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
typedef long long ll;
#define fi(i,n) for(int i=0;i<n;i++)
#define Fi(i,k,n) for(int i=k;i<n;i++)
#define fd(i,n) for(int i=n-1;i>=0;i--)
#define Fd(i,k,n) for(int i=n-1;i>=k;i--)
#define pop(i) __builtin_popcount(i)
const int mod = 1000000007;
#define deb(x) cout<<#x<<" "<<x<<"\n"
#define PI 3.1415926535897932384626
#define all(x) x.begin(),x.end()
#define sortall(x) sort(all(x))
#define mp make_pair
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define F first
#define S second
#define itr(it,a) for(it=a.begin();it!=a.end();it++)
#define bs(a,b) binary_search(all(a),b)
#define lb(a,b) lower_bound(all(a),b)
#define ub(a,b) upper_bound(all(a),b)
#define nod(x) floor(log10(x))+1
#define pb(s) push_back(s)
bool isSmaller(string str1, string str2) 
{ 
    int n1 = str1.length(), n2 = str2.length(); 
  
    if (n1 < n2) 
        return true; 
    if (n2 > n1) 
        return false; 
  
    for (int i=0; i<n1; i++) 
    { 
        if (str1[i] < str2[i]) 
            return true; 
        else if (str1[i] > str2[i]) 
            return false; 
    } 
    return false; 
} 
  
string findDiff(string str1, string str2) 
{ 
    // Before proceeding further, make sure str1 
    // is not smaller 
    if (isSmaller(str1, str2)) 
        swap(str1, str2); 
  
    // Take an empty string for storing result 
    string str = ""; 
  
    // Calculate lengths of both string 
    int n1 = str1.length(), n2 = str2.length(); 
    int diff = n1 - n2; 
  
    // Initially take carry zero 
    int carry = 0; 
  
    // Traverse from end of both strings 
    for (int i=n2-1; i>=0; i--) 
    { 
        // Do school mathematics, compute difference of 
        // current digits and carry 
        int sub = ((str1[i+diff]-'0') - 
                   (str2[i]-'0') - 
                   carry); 
        if (sub < 0) 
        { 
            sub = sub+10; 
            carry = 1; 
        } 
        else
            carry = 0; 
  
        str.push_back(sub + '0'); 
    } 
  
    // subtract remaining digits of str1[] 
    for (int i=n1-n2-1; i>=0; i--) 
    { 
        if (str1[i]=='0' && carry) 
        { 
            str.push_back('9'); 
            continue; 
        } 
        int sub = ((str1[i]-'0') - carry); 
        if (i>0 || sub>0) // remove preceding 0's 
            str.push_back(sub+'0'); 
        carry = 0; 
  
    } 
  
    // reverse resultant string 
    reverse(str.begin(), str.end()); 
  
    return str; 
} 
  

string addString(string x,string y){
    string z="";
    int d=0;
    int n1=x.length();
    int n2=y.length();
    int u=abs(n1-n2);
    
    if(n1>n2){
        fi(i,u){
            y='0'+y;
        }
    }
    
    if(n1<n2){
        fi(i,u){
            x='0'+x;
        }
    }
    
    
    string num[10]={"0","1","2","3","4","5","6","7","8","9"};
    
    for(int i=x.length()-1;i>=0;i--){
        int a=x[i]-48;
        int b=y[i]-48;
        int c=a+b+d;
        int u=c%10;
        d=c/10;
        z=num[u]+z;

    }
    if(d!=0){
        z=num[d]+z;
    }
    return z;

}
string shift(string x,int n){
    //to add 0's
    fi(i,n){
        x=x+'0';
    }
    return x;
}
string karatsuba(string x,string y){
    int n1=x.length();
    int n2=y.length();
    string num[10]={"0","1","2","3","4","5","6","7","8","9"};
    string s="";

    if(n1==1 && n2==1){
        int i=x[0]-48;
        int j=y[0]-48;
        int k=i*j;
        int u=k%10;
        k=k/10;
        s=s+num[u];
        if(k!=0){
            s=num[k]+s;
        }
        return s;

    }
    int u=abs(n1-n2);
    int n=max(n1,n2);
    
    if(n1>n2){
        fi(i,u){
            y='0'+y;
        }
    }
    
    if(n1<n2){
        fi(i,u){
            x='0'+x;
        }
    }
    string a,b,c,d;
    a=x.substr(0,n-n/2);
    b=x.substr(n-n/2,n/2);
    c=y.substr(0,n-n/2);
    d=y.substr(n-n/2,n/2);
    cout<<a<<"\n"<<b<<"\n"<<c<<"\n"<<d<<"\n";
    
    string s1=karatsuba(a,c);
    deb(s1);
    string s2=karatsuba(b,d);
    deb(s2);
    string s3=karatsuba(addString(a,b),addString(c,d));
    deb(s3);
    string e=addString(s1,s2);
    deb(e);
    int o=e.length();
    int o2=s3.length();
    if(o!=o2){
        fi(j,o2-o){
            e='0'+e;
        }
    }
    string s4=findDiff(s3,e);
    deb(s4);
    string s5=addString(shift(s1,2*floor(n/2)),addString(shift(s4,floor(n/2)),s2));
    
    deb(s5);
    string result=s5;
    return result.erase(0, min(result.find_first_not_of('0'), result.size()-1));

       
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    string a,b;
    cin>>a>>b;
    cout<<karatsuba(a,b);
    //cout<<a.substr(0,3);
    return 0;

//8539734222673567065463550869546574495034888535765114961879601127067743044893204848617875072216249073013374895871952806582723184
}

FAST C/C++ Implementation of the Karatsuba Multiplication algorithm.