/*
* 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.
* */
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.
*/
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
String num1 = String.valueOf(x);
String num2 = String.valueOf(y);
if(num1.length() < 10 || num2.length() < 10) return Long.parseLong(num1) * Long.parseLong(num2);
// 计算拆分长度
int size1 = num1.length();
int size2 = num2.length();
int halfN = Math.max(size1, size2) / 2;
/* 拆分为a, b, c, d */
String a = num1.substring(0, size1 - halfN);
String b = num1.substring(size1 - halfN);
String c = num2.substring(0, size2 - halfN);
String d = num2.substring(size2 - halfN);
// 计算z2, z0, z1, 此处的乘法使用递归
long z2 = KMultiply(Long.parseLong(a), Long.parseLong(c));
long z0 = KMultiply(Long.parseLong(b), Long.parseLong(d));
long z1 = KMultiply((Long.parseLong(a) + Long.parseLong(b)), (Long.parseLong(c) + Long.parseLong(d))) - z0 - z2;
return (long)(z2 * Math.pow(10, (2*halfN)) + z1 * Math.pow(10, halfN) + z0);
// END YOUR CODE
}
}