public class Poly{ private String variableName; private long [] coeffs; private long denominator;// Constructorspublic Poly ( String polyVariableName, long [] polyCoeffs, long polyDenominator ) { variableName = polyVariableName; coeffs = polyCoeffs; denominator = polyDenominator; }// Debug quality printing. Takes a polynomial and displays its coefficents.public String debugPrint () { String returnValue = "("; returnValue = returnValue + coeffs [0] + "*" + variableName + "^0"; for (int i = 1; i < coeffs.length; i++) { returnValue = returnValue + " + " + coeffs [i] + "*" + variableName + "^" + i; }; returnValue = returnValue + ")/"; returnValue = returnValue + denominator; return returnValue; }// Special-case multiplication. Multiplication by a coefficient.public static Poly mulByCoeff(Poly in, long mulBy) { Poly returnValue = new Poly ( in.variableName, new long [in.coeffs.length], in.denominator ); for (int i = 0; i < in.coeffs.length; i++) { returnValue.coeffs[i] = mulBy * in.coeffs [i]; }; returnValue = reduce(returnValue); returnValue = truncate(returnValue); return returnValue; }// Special-case multiplication. Division by a coefficient.public static Poly divByCoeff(Poly in, long divBy) { Poly returnValue = new Poly ( in.variableName, new long [in.coeffs.length], in.denominator ); for (int i = 0; i < in.coeffs.length; i++) { returnValue.coeffs[i] = in.coeffs [i] / divBy; }; returnValue = reduce(returnValue); returnValue = truncate(returnValue); return returnValue; }// Special-case multiplication. Multiplication by "x", variableNamepublic static Poly mulByx(Poly in) { Poly returnValue = new Poly ( in.variableName, new long [in.coeffs.length + 1], in.denominator); returnValue.coeffs[0] = 0; for (int i = 0; i < in.coeffs.length; i++) { returnValue.coeffs[i+1] = in.coeffs[i]; }; returnValue = reduce(returnValue); returnValue = truncate(returnValue); return returnValue; }// Addition of two polynomialspublic static Poly polyAdd (Poly A, Poly B) { // Determine length of coefficient array int lengthC = 0; if ( A.coeffs.length == B.coeffs.length ) { lengthC = A.coeffs.length; } else if ( A.coeffs.length > B.coeffs.length) { lengthC = A.coeffs.length; } else { lengthC = B.coeffs.length; }; // Determine common denominator long denomC = A.denominator * B.denominator; // Create return value Poly C = new Poly ( A.variableName, new long [lengthC], denomC); // Set all coefficients to 0 for (int i = 0; i < C.coeffs.length; i++) { C.coeffs[i] = 0; }; for (int i = 0; i < A.coeffs.length; i++) { C.coeffs[i] = C.coeffs[i] + B.denominator * A.coeffs[i]; }; for (int i = 0; i < B.coeffs.length; i++) { C.coeffs[i] = C.coeffs[i] + A.denominator * B.coeffs[i]; }; // Tidy up return value. C = reduce(C); C = truncate(C); return C; }// Subtraction of two polynomialspublic static Poly polyMinus (Poly A, Poly B) { return polyAdd(A, mulByCoeff(B,-1)); }// Multiplication of two polynomialspublic static Poly polyTimes (Poly A, Poly B) { // Determine length of coefficient array int lengthC = A.coeffs.length * B.coeffs.length; // Determine common denominator long denomC = A.denominator * B.denominator; // Create return value Poly C = new Poly ( A.variableName, new long [lengthC], denomC); // Set all coefficients to 0 for (int i = 0; i < C.coeffs.length; i++) { C.coeffs[i] = 0; }; for ( int i=0; i<A.coeffs.length; i++) { for ( int j=0; j<B.coeffs.length; j++) { C.coeffs[i+j] = C.coeffs[i+j] + A.coeffs[i]*B.coeffs[j]; }; }; // Tidy up return value. C = reduce(C); C = truncate(C); return C; }// Differentiation of a polynomialpublic static Poly polyDiff (Poly in) { Poly returnValue = new Poly ( in.variableName, new long [in.coeffs.length - 1], in.denominator); for (int i=0; i< in.coeffs.length-1 ; i++) { returnValue.coeffs[i] = (i+1) * in.coeffs [i+1]; }; returnValue = reduce(returnValue); returnValue = truncate(returnValue); return returnValue; }//// Start of utility functions called by tickable functions.//// Function to calculate the Highest Common Factor (Greatest Common Divisor) of 2 integers.public static long hcf(long m, long n) { if (m == 0) return n; if (n == 0) return m; return hcf(n,m%n); }// Function to reduce a polynomial to its simplest terms.public static Poly reduce(Poly in) { Poly returnValue = new Poly ( in.variableName, new long [in.coeffs.length], in.denominator ); long divisor = in.denominator; for (int i = 0; i < in.coeffs.length; i++) { divisor = hcf(in.coeffs[i],divisor); }; for (int i = 0; i < in.coeffs.length; i++) { returnValue.coeffs[i] = in.coeffs [i] / divisor; }; returnValue.denominator = in.denominator / divisor; return returnValue; }// Function to truncate 0 elements from the end of the arraypublic static Poly truncate(Poly in) { int top = 0; for ( int i = 0; i < in.coeffs.length; i++ ) { if (in.coeffs[i] != 0) { top = i; } else continue; }; Poly returnValue = new Poly ( in.variableName, new long [top+1], in.denominator ); for ( int i = 0; i < top+1; i++ ) { returnValue.coeffs[i] = in.coeffs[i]; }; return returnValue; }// Start of Main methodpublic static void main(String[] args) { // Proof of pudding part 1: System.out.println("Proof of pudding part 1:"); Poly [] P = new Poly[12]; P[0]= new Poly("x", new long[] {1L}, 1L); P[1]= new Poly("x", new long[] {0L, 1L}, 1L); for (int n = 2; n <= 12; n++) { P[n] = (P[n-1].polyMinus( (P[n-1].mulByx()).mulByCoeff(2*n-1), P[n-2].mulByCoeff(n-1) )).divByCoeff(n); System.out.printf("P%d ",n); P[n].debugPrint(); } }}