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.
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
Post a Comment