import java.util.Arrays;

/**
* Robert Sedgewick Algorithms in C++<br>
* Chapter 36 Arithmetic<br>
* Problem1<br>
* 多項式はr[0](x-r[1])(x-r[2])...(x-r[n])と表すことも出来る。このような場合乗算はどうなるか?
*/
public class Chapter36ArithmeticProblem1 {
public static void main(String[] args) {
Chapter36ArithmeticProblem1 o = new Chapter36ArithmeticProblem1();
o.run();
}

private void run() {
// 2 * x * x + 4 * x + 2 = 2 * (x - -1) * (x - -1)
double[] a = new double[] { 2, 4, 2, };
double[] r = new double[] { 2, -1, -1, };
for (int x = -100; x < 100; x++) {
double y = x * x * a[0] + x * a[1] + a[2];
double y2 = r[0] * (x - r[1]) * (x - r[2]);
if (y != y2) {
throw new AssertionError();
}
}

double[] mult = mult(a, a);
debug("mult", mult);
double[] mult2 = mult2(r, r);
debug("mult2", mult2);
for (int x = -100; x < 100; x++) {
double y = 0;
for (int i = 0; i < mult.length; i++) {
y = x * y + mult[i];
}
double y2 = mult2[0];
for (int i = 1; i < mult2.length; i++) {
y2 *= (x - mult2[i]);
}
if (y != y2) {
throw new AssertionError();
}
}
}

private double[] mult2(double[] a, double[] b) {
double[] res = new double[a.length + b.length - 1];
int ri = 0;
res[ri++] = a[0] * b[0];
for (int i = 1; i < a.length; i++) {
res[ri++] = a[i];
}
for (int i = 1; i < b.length; i++) {
res[ri++] = b[i];
}
return res;
}

private double[] mult(double[] a, double[] b) {
double[] res = new double[a.length + b.length - 1];
for (int ai = 0; ai < a.length; ai++) {
for (int bi = 0; bi < b.length; bi++) {
res[ai + bi] += a[ai] * b[bi];
}
}
return res;
}

private static final boolean DEBUG = true;

private static final void debug(Object... o) {
if (DEBUG)
System.err.println(Arrays.deepToString(o));
}

private static final void message(Object... o) {
System.err.println(Arrays.deepToString(o));
}

}