KaratSuva

/*
 * Biginteger multiplication
 * Algorithm: Karatsuva multiplication
 * Order: n^1.58
 * Note : 1) All the number should be kept in reverse order in vector
          2) After all computation Ans should be normalized
          3) BASE should be kept such that BASE*logn*32 doesnt overflow
          4) initially for two numbers lentg should be power of ontherwise
             otherwise padded extra field with zero
 */

#include<stdio.h>
#include<string.h>
#include<vector>
#include<algorithm>
using namespace std;
/* can be set any value like 10^8 */
const long BASE = 10;
/* used to set all value base 10 or defined Base*/
void Norm( vector<long> &A ){
    long i,Carry = 0;
    for( i=0;i<A.size();i++ ){
        long v = A[i] + Carry;
        A[i] = v%BASE;
        Carry = v/BASE;
    }
}
/* to check is all value of A is zero  */
bool AllZero( vector<long> &A ){
    long i;
    for( i=0;i<A.size();i++ ){
        if( A[i] ) return false;
    }
    return true;
}
/* multiple to num A and B , result in Ret */
/* A should be represented as A1*Base^(n/2) + A0 */
/* B should be represented as B1*Base^(n/2) + B0 */
void KaratSuva( vector<long> &A,vector<long> &B,vector<long> &Ret ){
    long i,j,n = A.size();
    Ret.resize( 2*n );
    /* check is any num is zero */
    if( AllZero( A ) || AllZero( B ) ){
        return;
    }
    /* normal multiplication for n lower value
    limit should be power of 2 ( 16,32,64 )
    any value can be used but 32 seems to b bettr */
    if( n<=32 ){
        for( i=0;i<n;i++ ){
            for( j=0;j<n;j++ ){
                Ret[i+j] += A[i]*B[j];
            }
        }
        return;
    }

    vector<long> A1( A.begin()+n/2,A.end());
    vector<long> A0( A.begin(),A.begin()+n/2 );
    vector<long> B1( B.begin()+n/2,B.end());
    vector<long> B0( B.begin(),B.begin()+n/2 );

    vector<long> A1_B1,A0_B0;
    KaratSuva( A1,B1,A1_B1 );
    KaratSuva( A0,B0,A0_B0 );

    for( i=0;i<n/2;i++ ){
        A1[i] += A0[i];
        B1[i] += B0[i];
    }

    vector<long> A_B;
    KaratSuva( A1,B1,A_B );
    for( i=0;i<n;i++ ){
        A_B[i] -= A1_B1[i]+A0_B0[i];
    }

    for( i=0;i<n;i++ ){
        Ret[i] += A0_B0[i];
        Ret[i+n/2] += A_B[i];
        Ret[i+n] += A1_B1[i];
    }
}