Instructions
Objective
Write a java assignment program to calculate the product of the two polynomials via Karatsuba’s algorithm.
Requirements and Specifications
In class, we learned Karatsuba’s algorithm for multiplying two n-digit integers, where n is a perfect power of 2 in 𝑂(𝑛𝑙𝑜𝑔23) time. This algorithm can be very slightly modified to work for polynomials of degree n, where n is a perfect power of 2 minus 1. For this assignment, you will implement Karatsuba’s algorithm and be required to implement several methods. In addition, your code should process the input given, calling the appropriate method of the required ones and output the result of the computation in the desired output format.
The Problem:
Given two polynomials, calculate the product of the two polynomials via Karatsuba’s algorithm and output the result.
The Input:
The first line of input contains a single integer, n (0 ≤ n ≤ 19), representing that there will be two polynomials of degree 2n – 1 to be multiplied for the input case. The second line of input contains 2n – 1 space separated integers, representing the coefficients of the first polynomial in order from largest to smallest term. For example, the polynomial 5x3 – 7x2 + 8x + 6 would be represented as 5 -7 8 6 The third line of input contains 2n – 1 space separated integers, representing the coefficients of the second polynomial in order from largest to smallest term.
Source Code
import java.util.Arrays; // You may use Arrays.copyOfRange method
import java.util.Scanner;
import java.util.stream.Collectors;
public class poly {
private int length;
private long[] coeff;
poly(String s) {
String[] parts = s.split("\\s+");
length = parts.length;
coeff = new long[length];
for (int i = 0; i < length; i++) {
coeff[i] = Long.parseLong(parts[i]);
}
}
public String toString(int n) {
return Arrays.stream(Arrays.copyOf(coeff, n)).mapToObj(Long::toString).collect(Collectors.joining(System.lineSeparator()));
}
// Creates a polynomial from the coefficients stored in vals.
// The polynomial created must store exactly (1< // for some integer k.
public poly(long[] vals) {
length = vals.length;
coeff = new long[length];
for (int i = 0; i < length; i++) {
coeff[i] = vals[i];
}
}
// Both this and other must be of the same size and the
// corresponding lengths must be powers of 2.
// Returns the sum of this and other in a newly created poly.
public poly add(poly other) {
long[] res = new long[length];
for (int i = 0; i < length; i++) {
res[i] = coeff[i] + other.coeff[i];
}
return new poly(res);
}
// Both this and other must be of the same size and the
// corresponding lengths must be powers of 2.
// Returns the difference of this and other in a new poly.
public poly sub(poly other) {
long[] res = new long[length];
for (int i = 0; i < length; i++) {
res[i] = coeff[i] - other.coeff[i];
}
return new poly(res);
}
// Both this and other must be of the same size and the
// corresponding lengths must be powers of 2.
// Returns the product of this and other in a newly created
// poly, using the regular nested loop algorithm, with the
// length being the next power of 2.
public poly multSlow(poly other) {
int newLen = 2 * length - 1;
poly result = new poly(new long[newLen]);
for (int i = 0; i < length; i++) {
long[] shifted = new long[newLen];
for (int j = 0; j < length; j++) {
shifted[i + j] = other.coeff[i] * coeff[j];
}
result = new poly(shifted).add(result);
}
return result;
}
// Both this and other must be of the same size and the
// corresponding lengths must be powers of 2.
// Returns the product of this and other in a newly created
// poly, using Karatsuba’s algorithm, with the
// length being the next power of 2.
public poly mult(poly other) {
if (length == 1) {
return new poly(new long[]{coeff[0] * other.coeff[0], 0});
}
int newLen = 2 * length;
poly a1 = getLeft();
poly a2 = getRight();
poly b1 = other.getLeft();
poly b2 = other.getRight();
poly c1 = new poly(Arrays.copyOf(a1.mult(b1).coeff, newLen));
long[] c2Arr = new long[newLen];
poly tmp = a1.mult(b2).add(a2.mult(b1));
for (int i = 0; i < length; i++) {
c2Arr[length / 2 + i] = tmp.coeff[i];
}
poly c2 = new poly(c2Arr);
long[] c3Arr = new long[newLen];
poly tmp2 = a2.mult(b2);
for (int i = 0; i < length; i++) {
c3Arr[length + i] = tmp2.coeff[i];
}
poly c3 = new poly(c3Arr);
return c1.add(c2).add(c3);
}
// Returns the left half of this poly in its own poly.
private poly getLeft() {
return new poly(Arrays.copyOf(coeff, length / 2));
}
// Returns the right half of this poly in its own poly.
private poly getRight() {
return new poly(Arrays.copyOfRange(coeff, length / 2, length));
}
public static void main(String[] args) {
try (Scanner scanner = new Scanner(System.in)) {
int n = Integer.parseInt(scanner.nextLine());
poly a = new poly(scanner.nextLine());
poly b = new poly(scanner.nextLine());
System.out.println(a.mult(b).toString(Math.toIntExact(Math.round(Math.pow(2, n + 1))) - 1));
}
}
}