KARASTUBA MULTIPLICATION-An efficient multiplication algorithm

Karastuba multiplication algorithm is one of the fastest algorithms for multiplication
I learnt this algorithm from Coursera. The concept is very easy to understand. Only algorithm is taught in Coursera. So I tried and it works well..
This is my source code.
       

#include<iostream>

#include<string>

#include<math.h>

using namespace std;

int karatsuba(int n1,int n2,int z1,int z2){

    int z=max(l1,l2);

    if(z==1){

        return n1*n2;

    }

    int m=z/2;

    int a=n1/(int)floor(pow(10,m)),

        b=n1%(int)floor(pow(10,m)),

        c=n2/(int)floor(pow(10,m)),

        d=n2%(int)floor(pow(10,m)),

        ac=karatsuba(a,c,z1/2,z2/2),

        bd=karatsuba(b,d,z1/2,z2/2),

        e=karatsuba(a+b,c+d,z1/2,z2/2)-ac-bd;

    return(ac*pow(10,z)+bd+e*pow(10,z/2));

}

int main(){

    string n1,n2;

    int num1,num2,l1,l2;

    cin>>n1>>n2;

    l1=n1.length();

    l2=n2.length();

    num1=stoi(n1);

    num2=stoi(n2);

    int ans=karatsuba(num1,num2,l1,l2);

    cout<<ans;

    return 0;

}

 


Comments