Download

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 Z_m[x] of total degree n. To avoid complexity, simplertimes requires that n < 2²⁷ and fixes m = 2013265921 = 2³¹ - 2²⁷ + 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);
}

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 = 2³¹ - 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²⁷). Powers of one such element take on the role of the complex roots of unity.

© 2014 David Eisenstat