implement the divide-and-conquer recursive method in java using arity (branching
ID: 3752255 • Letter: I
Question
implement the divide-and-conquer recursive method in java using arity (branching factor) of 3. You should not assume the number of bits is always even. You will need to take care of this carefully in implementing the algorithm outlined in the book.
A divide-and-conquer algorithm for integer multiplication.
function multiply(x, y)
Input: n-bit positive integers x and y
Output: Their product
if n = 1: return xy xL,
xR = leftmost n/2, rightmost n/2 bits of x
yL, yR = leftmost n/2, rightmost n/2 bits of y
P1 =multiply(xL,yL)
P2 =multiply(xR,yR)
P3 =multiply(xL +xR,yL +yR)
return P1 ×2n +(P3 P1 P2)×2n/2 + P2
Explanation / Answer
Please find the code below with detailed inline comments.
CODE
================
import java.util.Arrays;
public class Karatsuba {
public static void main(String[] args) {
System.out.println(multiply("10011", "10001", 2));
}
/**
* Converts a numeric string into an array of int, preserving right-left order and ignoring radix
*/
private static int[] toIntArray(String num, boolean hasRadix){
int[] arr = (hasRadix)? new int[num.length()-1]: new int[num.length()];
int index = 0;
for (int i=0; i<num.length(); i++){
char character = num.charAt(i);
// if radix
if (character == '.') continue; // skip
arr[index] = parseDigit(character);
index++;
}
return arr;
}
/**
* Converts a int array to numeric string
*/
private static String intArrayToString(int[] arr){
StringBuffer sb = new StringBuffer();
for (int i: arr){
sb.append(toDigit(i));
}
if (sb.charAt(0) == '0') sb.deleteCharAt(0);
return sb.toString();
}
/**
* Driver function for KaratsubaMultiply
* Formats input parameters and output
*/
private static String multiply(String x, String y, int base){
int radix_x_Index = x.indexOf('.');
int radix_y_Index = y.indexOf('.');
// reversed (numeric) index of radix points
int radix_x_pos = (radix_x_Index == -1)? 0: x.length() - x.indexOf('.') - 1;
int radix_y_pos = (radix_y_Index == -1)? 0: y.length() - y.indexOf('.') - 1;
// convert to int arrays (ignores radixes)
int[] x_arr = (radix_x_Index == -1)? toIntArray(x, false): toIntArray(x, true);
int[] y_arr = (radix_y_Index == -1)? toIntArray(y, false): toIntArray(y, true);
// compute multiplication
int[] ans_arr = karatsubaMultiply(x_arr, y_arr, base); // by karatsuba
StringBuffer sb = new StringBuffer(intArrayToString(ans_arr));
// incorporating back the radix point
if (radix_x_pos + radix_y_pos != 0){
int radix_pos = radix_x_pos + radix_y_pos;
if (radix_pos > ans_arr.length){
char[] shiftZeros = new char[radix_pos - ans_arr.length];
Arrays.fill(shiftZeros, '0'); // string of amount number of '0's
sb.insert(0, shiftZeros);
}
sb.insert(ans_arr.length - radix_pos - 1, '.');
}
return trimZeros(sb.toString());
}
/**
* Karatsuba's multiplication algorithm (recursive)
*/
private static int[] karatsubaMultiply(int[] x, int[] y, int base){
// equalize string lengths by prepending '0's to shorter string
if (x.length > y.length)
y = shift("right", y, x.length - y.length);
else if (y.length > x.length)
x = shift("right", x, y.length - x.length);
// base case: less than or equal to 61 digits
// Reason: Karatsuba works best for multiplicands above 320 bits ~ 186 digits for decimal
if (x.length <= 141 && y.length <= 141){
return longMultiplication(x, y, base);
}
int n = x.length;
int nHalf = x.length - n/2;
int[] x1 = copyOfRange(x, 0, n/2);
int[] x0 = copyOfRange(x, n/2, x.length);
int[] y1 = copyOfRange(y, 0, n/2);
int[] y0 = copyOfRange(y, n/2, y.length);
// 3 recursive calls
int[] x1y1 = karatsubaMultiply(x1, y1, base); // x1 * y1
int[] x1x0y1y0 = karatsubaMultiply(addition(x1, x0, base), addition(y1 , y0, base), base); // (x1 + x0)*(y1 * y0)
int[] x0y0 = karatsubaMultiply(x0, y0, base); // x0 * y0
// System.out.println("x = " + x + ", y = " + y + ", n/2 = " + n/2); // check
// System.out.println("x1 = " + x1 + ", x0 = " + x0 + ", y1 = " + y1 + ", y0 = " + y0); // check
// System.out.println("x1y1 = " + x1y1 + ", x1x0y1y0 = " + x1x0y1y0 + ", x0y0 = " + x0y0); // check
// System.out.println("------------------------------"); // check
int[] part1 = shift("left", x1y1, 2*nHalf);
int[] part2 = shift("left", subtraction(subtraction(x1x0y1y0, x1y1, base), x0y0, base), nHalf);
return addition(addition(part1, part2, base), x0y0, base);
}
/**
* Long multiplication algorithm
*/
private static int[] longMultiplication(int[] x, int[] y, int base){
int[] top, bot; // top and bottom operands in long multiplication
if (x.length >= y.length){
top = x;
bot = y;
}
else{
top = y;
bot = x;
}
int[] ans = new int[x.length + y.length];
int offset = 0; // right offset when adding the rows
// for each digit in bot string from right to left
for (int i=bot.length-1; i>=0; i--){
int carryOver_product = 0; // carryover due to multiplication
int carryOver_add = 0; // carryover due to addition
// for each digit in top string from right to left
for (int j=top.length-1; j>=0; j--){
/* derive product of 2 digits */
int product = bot[i] * top[j] + carryOver_product; // multiply top digit with bottom digit and add with carryover
// System.out.println("top[j] = " + top[j] + ", bot[i] = " + bot[i] + ", carryOver = " + carryOver + ", product = " + product); // check
carryOver_product = product/base; // carry over from product
product %= base; // product after forwarding carryover
/* add product to ans[] */
int ans_index = ans.length - (top.length - j) - offset; // corresponding index in ans[]
ans[ans_index] += product + carryOver_add;
carryOver_add = ans[ans_index]/base;
ans[ans_index] = ans[ans_index]%base;
}
// handle final carryovers
if (carryOver_product != 0 || carryOver_add != 0){
// NOTE: ans[ans_index] is definitely == 0, mathematically (carryOver_product + carryOver_add < base) is guaranteed
int ans_index = ans.length - (top.length + 1) - offset;
ans[ans_index] += carryOver_product + carryOver_add;
}
offset++; // update: pad one more '0' to the right of next row
}
return ans;
}
/**
* Shifts array by amount given and in the direction stated
*/
private static int[] shift(String direction, int[] arr, int amount){
// System.out.println("[shift] numericString,amount: " + numericString + "," + amount); // check
int[] shiftedArr = new int[arr.length + amount];
// if pad right
if (direction == "left"){
for (int i=0; i<arr.length; i++){
shiftedArr[i] = arr[i];
}
}
// else if pad left
else if (direction == "right"){
for (int i=0; i<arr.length; i++){
shiftedArr[i + amount] = arr[i];
}
}
return shiftedArr;
}
/**
* Adds two int arrays of the given base
*/
private static int[] addition(int[] a, int[] b, int base){
int[] ans = new int[Math.max(a.length, b.length) + 1];
int carryOver = 0; // 0 or 1
// scans from right to left
for (int i=ans.length-1; i>=0; i--){
int sum = carryOver;
int numericPos = ans.length - i; // numeric position of ans
// if within region of a
if (numericPos <= a.length){
sum += a[a.length - numericPos];
}
// if within region of b
if (numericPos <= b.length){
sum += b[b.length - numericPos];
}
ans[i] = sum%base; // update ans
carryOver = sum/base; // update carry over
}
return ans;
}
/**
* Subtracts 'smaller' from 'greater' int arrays of the given base
* will not produce negative numbers since greater and smaller are guaranteed by caller
*/
//
private static int[] subtraction(int[] greater, int[] smaller, int base){
int borrowOver = 0; // 0 or 1
for (int i=smaller.length-1; i>=0; i--){
int index_greater = greater.length - (smaller.length - i); // corresponding index in greater
greater[index_greater] = greater[index_greater] - smaller[i] - borrowOver;
// if need to borrow over, borrowOver = 1
if (greater[index_greater] < 0){
greater[index_greater] += base;
borrowOver = 1;
}
// else if no need to borrow over, borrowOver = 0
else borrowOver = 0;
}
// handle final borrowOver
if (borrowOver != 0) greater[greater.length - smaller.length - 1] -= borrowOver;
return greater;
}
/**
* Creates subarray from the given range
*/
private static int[] copyOfRange(int[] src, int start, int end){
int[] dest = new int[end - start];
System.arraycopy(src, start, dest, 0, end - start);
return dest;
}
/**
* Use to trim leading and trailing zeros on a result string.
*/
private static String trimZeros(String input) {
int left = 0;
int right = input.length()-1;
int fp = input.indexOf('.');
if (fp == -1) {
fp = input.length();
}
while(left < fp-1) {
if (input.charAt(left) != '0')
break;
left++;
}
while (right >= fp) {
if (input.charAt(right) != '0') {
if (input.charAt(right) == '.')
right--;
break;
}
right--;
}
if (left >= fp)
return "0" + input.substring(left,right+1);
return input.substring(left,right+1);
}
/**
* Convert digit to int (for reading)
*/
private static int parseDigit(char c) {
if (c <= '9') {
return c - '0';
}
return c - 'A' + 10;
}
/**
* Convert int to digit. (for printing)
*/
private static char toDigit(int digit) {
if (digit <= 9) {
return (char)(digit + '0');
}
return (char)(digit - 10 + 'A');
}
/**
* For checking: prints out the int array
*/
@SuppressWarnings("unused")
private static void printIntArray(int[] arr){
System.out.print("[printIntArray]: ");
for (int i: arr)
System.out.print(i);
System.out.println();
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.