CS计算机代考程序代写 algorithm /*

/*
* 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 } }