My own karatsuba Multiplication Algorithm Implementation

This is my implementation of Karatsuba Multiplication Algorithm. although the ideal implementation would be using strings, I tried to do it with ‘long long int’ which is quite easy when compared to the ‘string’ version.


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
long long int karatsuba(long long int a,long long int b, int c);
int main(int argc, char const *argv[])
{
long long int integer1,integer2,result;
int length;
scanf("%lld", &integer1);
scanf("%lld", &integer2);
scanf("%d", &length);
result=karatsuba(integer1,integer2, length);
printf("%lld\n", result);
return 0;
}
long long int karatsuba(long long int a,long long int b, int c)
{
long long int red1,red2,red3,red4,res1,res2,res3,res4,final;
if (c>1)
{
final=a*b;
}
else
{
red1=a/(pow(10,c/2));
red2=a-(red1*pow(10,c/2));
red3=b/pow(10,c/2);
red4=b-(red3*pow(10,c/2));
res1=karatsuba(red1,red3,c/2);
res2=karatsuba(red2,red4,c-(c/2));
res3=karatsuba(red1+red2,red3+red4, c-(c/2));
res4=res3-res1-res2;
final=(res1*pow(10,c))+(res4*pow(10,c/2))+(res2);
}
return final;
}

Advertisements

One thought on “My own karatsuba Multiplication Algorithm Implementation

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s