Shoenhage-Strassen performance compared to Karatsuba in Rings 2.x

ShoenhageStrassenPerformance.java

@Test
public void testShoenhageStrassenPerformance() {
    // some test polynomials
    UnivariatePolynomial<BigInteger> a = UnivariatePolynomial.create(1, 2, 1);
    UnivariatePolynomial<BigInteger> b = UnivariatePolynomial.create(1, 1, 1, 2, 1, 1, 1, 3, 1, 1);
    a = a.shiftRight(111814).increment();
    b = b.shiftRight(111001).increment();

    System.out.println("a degree: " + a.degree);
    System.out.println("a max cf: " + a.maxAbsCoefficient());

    System.out.println("b degree: " + b.degree);
    System.out.println("b max cf: " + b.maxAbsCoefficient());

    for (int i = 0; i < 10000; ++i) {
        long start;

        start = System.nanoTime();
        UnivariatePolynomial<BigInteger> cl = a.clone().multiply(b);
        System.out.println("default : " + TimeUnits.nanosecondsToString(System.nanoTime() - start));

        start = System.nanoTime();
        UnivariatePolynomial<BigInteger> kr = multiplySchoenhageStrassen(a, b);
        System.out.println("ss      : " + TimeUnits.nanosecondsToString(System.nanoTime() - start));

        assert kr.equals(cl);
        System.out.println();
    }
}

/** Fast polynomial evaluation at power of two */
public static BigInteger evalAtPowerOf2(UnivariatePolynomial<BigInteger> a, int bitLen) {
    BigInteger res = a.cc();
    for (int i = 1; i <= a.degree; ++i)
        res = res.add(a.get(i).shiftLeft(i * bitLen));
    return res;
}

/** Univariate multiplication with Kronecker substitution using Schoenhage-Strassen multiplication for integers */
public static UnivariatePolynomial<BigInteger>
multiplySchoenhageStrassen(UnivariatePolynomial<BigInteger> a,
                           UnivariatePolynomial<BigInteger> b) {
    // coefficient bound
    BigInteger cfBound =
            a.maxAbsCoefficient()
                    .multiply(b.maxAbsCoefficient())
                    .multiply(BigInteger.valueOf(Math.min(a.degree, b.degree)));
    // point for Kronecker substitution (power of two) is 2^bitLen
    int bitLen = cfBound.bitLength() + 1;

    // evaluate fast of a and b at point
    BigInteger
            aVal = evalAtPowerOf2(a, bitLen),
            bVal = evalAtPowerOf2(b, bitLen);

    // packed result, Schoenhage-Strassen is used internally for multiplication
    // when aVal & bVal bit length > 8720
    BigInteger packedResult = aVal.multiply(bVal);
    // unpacked result
    BigInteger[] unpackedResult = new BigInteger[a.degree + b.degree + 1];
    // unpacking
    for (int i = a.degree + b.degree; i > 0; --i) {
        BigInteger
                div = packedResult.shiftRight(i * bitLen),
                rem = packedResult.subtract(div.shiftLeft(i * bitLen));

        unpackedResult[i] = div;
        packedResult = rem;
    }
    unpackedResult[0] = packedResult;
    return UnivariatePolynomial.create(a.ring, unpackedResult);
}