simplertimes: fast polynomial multiplication for programming contests (Java)

David Eisenstat

August 2014


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


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);


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