# simplertimes: fast polynomial multiplication for programming contests (Java)

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.

# Synopsis

`simplertimes` provides an O(n log n)-time method, `Polynomial.multiply`, to multiply two polynomials in Zm[x] of total degree n. To avoid complexity, `simplertimes` requires that n < 227 and fixes m = 2013265921 = 231 - 227 + 1, a prime. Polynomials are encoded as nonempty arrays where the value at index k is the coefficient of xk. 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);
}``````

# Design

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` = 231 - 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 Zm* has elements whose multiplicative order is a large power of 2 (227). Powers of one such element take on the role of the complex roots of unity.

© 2014 David Eisenstat