/*
* The given code is provided to assist you to complete the required tasks. But the
* given code is often incomplete. You have to read and understand the given code
* carefully, before you can apply the code properly.
*/
/*
* Please review Lecture 5 Algorithms Part I, slide 49 to complete this task.
* */
package assignment.task2;
public class MultiplicationAlgorithm {
/**
* Using divide-and-conquer to implement the Karatsuba multiplication to compute the product x times y.
* x and y are two n-digit input numbers.
*
* @param input x
* @param input y
*/
public static long KMultiply(long x, long y){
// TODO: Complete this method
tracker.calltracking(x,y); //Do not modify this method. Otherwise, you will be penalized for violation.
// START YOUR CODE
// Recursive termination condition
if(x<10||y<10)
return x*y;
// find length of both numbers x and y
int xlength = String.valueOf(x).length();
int ylength = String.valueOf(y).length();
//Calculate split length - n
int halfl = Math.max(xlength,ylength) / 2;
// recursively compute a*c,b*d,(a+b)*(c+d)
long a = Long.valueOf(String.valueOf(x).substring(0,xlength-halfl)); // to xlength-halfl-1 and include 0
long b = Long.valueOf(String.valueOf(x).substring(xlength-halfl));
long c = Long.valueOf(String.valueOf(y).substring(0,ylength-halfl));
long d = Long.valueOf(String.valueOf(y).substring(ylength-halfl));
long z2 = KMultiply(a,c);
long z0 = KMultiply(b,d);
long z1 = KMultiply((a+b),(c+d))-z0-z2;
// (a*c)*10^n + (a*d+c*d)*10^(n/2) + (b*d)
return (long)(z2*Math.pow(10,(2*halfl))+ z1*Math.pow(10,halfl)+z0);
// return 0;
// END YOUR CODE
}
}