Comparing different binomial computation implementations.

FastBigIntegerBinomial.java

package io.github.coderodde.math;

import java.math.BigInteger;

/**
 * This class provides some facilities for computing binomials with arbitrary 
 * precision.
 */
public final class FastBigIntegerBinomial {

    private FastBigIntegerBinomial() {
        
    }
    
    public static BigInteger binomial(BigInteger n, BigInteger k) {
        BigInteger cornerCase = checkParameters(n, k);
        
        if (cornerCase != null) {
            return cornerCase;
        }
        
        return factorial(n).divide(
            factorial(k).multiply(factorial(n.subtract(k))));
    }
    
    public static BigInteger fastBinomial(BigInteger n, BigInteger k) {
        BigInteger cornerCase = checkParameters(n, k);
        
        if (cornerCase != null) {
            return cornerCase;
        }
        
        BigInteger nMinusk = n.subtract(k);
        // 5! / (3! 2!) = n! / (k! nMinusk!)
        if (k.compareTo(nMinusk) > 0) {
            // Here, k > n - k
            return boundedFactorial(k.add(BigInteger.ONE), n)
                .divide(factorial(nMinusk));
        } else {
            // Here, k <= n - k
            return boundedFactorial(nMinusk.add(BigInteger.ONE), n)
                .divide(factorial(k));
        }
    }
    
    public static BigInteger fastBinomialV2(BigInteger n, BigInteger k) {
        BigInteger cornerCase = checkParameters(n, k);
        
        if (cornerCase != null) {
            return cornerCase;
        }
        
        k = k.min(n.subtract(k));
        
        BigInteger result = BigInteger.ONE;
        
        for (BigInteger i = BigInteger.ONE;
                i.compareTo(k) <= 0;
                i = i.add(BigInteger.ONE)) {
            
            result = result.multiply(n.subtract(k).add(i)).divide(i);
        }
        
        return result;
    }
    
    public static BigInteger factorial(BigInteger n) {
        if (n.signum() < 0) {
            throw new IllegalArgumentException(
                "The input integer is negative: " + n);
        }
        
        BigInteger result = BigInteger.ONE;
        
        for (BigInteger i = BigInteger.TWO; 
                i.compareTo(n) <= 0;
                i = i.add(BigInteger.ONE)) {
            
            result = result.multiply(i);
        }
        
        return result;
    }
    
    public static BigInteger boundedFactorial(BigInteger lo, BigInteger hi) {
        BigInteger result = BigInteger.ONE;
        
        for (BigInteger i = lo; 
                i.compareTo(hi) <= 0; 
                i = i.add(BigInteger.ONE)) {
            
            result = result.multiply(i);
        }
        
        return result;
    }
    
    private static BigInteger checkParameters(BigInteger n, BigInteger k) {
        if (n.compareTo(BigInteger.ZERO) < 0) {
            throw new IllegalArgumentException(String.format("n (%s) < 0", n));
        }
        
        if (k.compareTo(BigInteger.ZERO) < 0) {
            return BigInteger.ZERO;
        }
        
        if (k.compareTo(n) > 0) {
            return BigInteger.ZERO;
        }
        
        return null;
    }
    
    private static final class Demo {
        private static final int N = 200;
        
        public static void main(String[] args) {
            long t = System.currentTimeMillis();
            runBinomialBenchmark();
            System.out.printf("binomial() in %d ms.%n", 
                              System.currentTimeMillis() - t);
            
            t = System.currentTimeMillis();
            runFastBinomialBenchmark();
            System.out.printf("fastBinomial() in %d ms.%n", 
                              System.currentTimeMillis() - t);
            
            t = System.currentTimeMillis();
            runFastBinomialV2Benchmark();
            System.out.printf("fastBinomialV2() in %d ms.%n", 
                              System.currentTimeMillis() - t);
        }
        
        private static void runBinomialBenchmark() {
            for (int a = 0; a < N; ++a) {
                BigInteger bia = BigInteger.valueOf(a);
                
                for (int b = 0; b < N; ++b) {
                    BigInteger bib = BigInteger.valueOf(a);
                    binomial(bia, bib);
                }
            }
        }
        
        private static void runFastBinomialBenchmark() {
            for (int a = 0; a < N; ++a) {
                BigInteger bia = BigInteger.valueOf(a);
                
                for (int b = 0; b < N; ++b) {
                    BigInteger bib = BigInteger.valueOf(a);
                    fastBinomial(bia, bib);
                }
            }
        }
        
        private static void runFastBinomialV2Benchmark() {
            for (int a = 0; a < N; ++a) {
                BigInteger bia = BigInteger.valueOf(a);
                
                for (int b = 0; b < N; ++b) {
                    BigInteger bib = BigInteger.valueOf(a);
                    fastBinomialV2(bia, bib);
                }
            }
        }
    }
}

FastBigIntegerBinomialTest.java

package io.github.coderodde.math;

import java.math.BigInteger;
import org.junit.Test;
import static org.junit.Assert.*;

public final class FastBigIntegerBinomialTest {
    
    @Test
    public void stressTest() {
        for (int a = 0; a <= 10; a++) {
            BigInteger ai = BigInteger.valueOf(a);
            
            for (int b = 0; b <= 10; b++) {
                BigInteger bi = BigInteger.valueOf(b);
                BigInteger binomial1 = FastBigIntegerBinomial.binomial(ai, bi);
                BigInteger binomial2 = FastBigIntegerBinomial.fastBinomial(ai, 
                                                                           bi);
                BigInteger binomial3 =
                        FastBigIntegerBinomial.fastBinomialV2(ai, bi);
                
                assertEquals(binomial1, binomial2);
                assertEquals(binomial1, binomial3);
            }
        }
    }
    
    @Test(expected = IllegalArgumentException.class)
    public void throwsOnNegativeN() {
        FastBigIntegerBinomial.binomial(BigInteger.valueOf(-1L), 
                                        BigInteger.ONE);
    }
    
    @Test
    public void kOutOfBounds() {
        assertEquals(BigInteger.ZERO,
                     FastBigIntegerBinomial.binomial(BigInteger.ONE, 
                                                     BigInteger.valueOf(-1L)));
        assertEquals(BigInteger.ZERO,
                     FastBigIntegerBinomial.binomial(BigInteger.ONE, 
                                                     BigInteger.valueOf(2L)));
    }
    
    @Test
    public void partialFactorial() {
        assertEquals(
            BigInteger.ONE,
            FastBigIntegerBinomial.boundedFactorial(
                BigInteger.valueOf(3),
                BigInteger.valueOf(2)));
        
        assertEquals(
            BigInteger.valueOf(3),
            FastBigIntegerBinomial.boundedFactorial(
                BigInteger.valueOf(3),
                BigInteger.valueOf(3)));
        
        assertEquals(
            BigInteger.valueOf(12),
            FastBigIntegerBinomial.boundedFactorial(
                BigInteger.valueOf(3),
                BigInteger.valueOf(4)));
    }
}

pom.xml

<?xml version="1.0" encoding="UTF-8"?>
<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
    <modelVersion>4.0.0</modelVersion>
    <groupId>io.github.coderodde.math</groupId>
    <artifactId>FastBigIntegerBinomial.java</artifactId>
    <version>1.0.0</version>
    <packaging>jar</packaging>
    <properties>
        <project.build.sourceEncoding>UTF-8</project.build.sourceEncoding>
        <maven.compiler.release>21</maven.compiler.release>
        <exec.mainClass>io.github.coderodde.math.FastBigIntegerBinomial$Demo</exec.mainClass>
    </properties>
    <name>FastBigIntegerBinomial.java</name>
    <dependencies>
        <dependency>
            <groupId>junit</groupId>
            <artifactId>junit</artifactId>
            <version>4.13.2</version>
            <scope>test</scope>
        </dependency>
        <dependency>
            <groupId>org.hamcrest</groupId>
            <artifactId>hamcrest-core</artifactId>
            <version>1.3</version>
            <scope>test</scope>
        </dependency>
    </dependencies>
</project>