~KARATSUBA Algorithm~
-> developed by anatoly Karatsuba in the 1960 and published in 1962
-> Fast multiplication method which uses divide and conquer.
-> Time complexity = O(n^(log 3 base 2)) = O(n^1.585).
Time taken for larger numbers to multiple is O(n^2).
-> Reduces the number of Recursive multiplications, required by breaking down the
numbers into smaller parts.
APPLICATION:
-> Used in cryptoGraphy(RSA and where large number multiplication is common).
-> Large integer Arithmetic; requiring precise calculations for larger numbers.
-> Extends into faster Multiplication algorithms such as TOOM COOK and Schönhage -
Strassen algorithms.
CODE:
import [Link].*;
class Karatsuba{
static int karatsuba(int x, int y){
if(x < 10 && y < 10){
return x * y;
}
else{
int n = [Link](getNumDigits(x), getNumDigits(y));
n += n%2;
int factor = (int)[Link](10, n/2);
int a = x / factor;
int b = x % factor;
int c = y / factor;
int d = y % factor;
int ac = karatsuba(a,c);
int bd = karatsuba(b,d);
int ad_bc = (a + b)*(c + d) - ac - bd;
return (int) (ac * (int)[Link](factor, 2) + ad_bc * factor + bd);
}
}
static int getNumDigits(int a){
int digits = 0;
while(a != 0){
a /= 10;
digits++;
}
return digits;
}
public static void main(String[] args){
Scanner input = new Scanner([Link]);
int x = [Link]();
int y = [Link]();
[Link]("The karatsuba product of %d and %d is %d", x, y,
karatsuba(x, y));
}
}
