August 2014

The latest release is August 2014. The source file Polynomial.java is the whole library. The source file TestPolynomial.java is a test program. Both are MIT-licensed.

`simplertimes`

provides an *O*(*n* log *n*)-time method, `Polynomial.multiply`

, to multiply two polynomials in **Z**_{m}[*x*] of total degree *n*. To avoid complexity, `simplertimes`

requires that *n* < 2^{27} and fixes *m* = 2013265921 = 2^{31} - 2^{27} + 1, a prime. Polynomials are encoded as **nonempty** arrays where the value at index *k* is the coefficient of *x*^{k}. Each coefficient must belong to the range [0, *m*). **Negative coefficients are disallowed!**

```
public final class Polynomial {
public static final int LOG_MAX_LENGTH = 27;
public static final int MODULUS = 2013265921;
public static int[] multiply(int[] a, int[] b);
}
```

The primary design goals were simplicity and comprehensibility, since contest rules may prohibit direct use of the code. `simplertimes`

uses a radix-2 decimation-in-time Cooley–Tukey number-theoretic transform, similar to the basic fast Fourier transform described in many textbooks. In a concession to efficiency, the implemented transform is iterative, not recursive, and in-place. The needed bit-reversal permutation is applied with the help of a Bit Twiddling Hack due to Edwin Freed.

To simplify the modular arithmetic, the prime modulus *m* was chosen to be less than `Integer.MAX_VALUE`

= 2^{31} - 1. To ensure a large range of possible coefficients, *m* was chosen to be only slightly less. To accommodate a strictly radix-2 transform, *m* was chosen so that **Z**_{m}^{*} has elements whose multiplicative order is a large power of 2 (2^{27}). Powers of one such element take on the role of the complex roots of unity.

© 2014 David Eisenstat