Fast computation of large binomial coefficients "binomial(n, k)" based on Goetgheluck's algorithm [1] combined with binary splitting while multiplying a series of factors, and a multiplication tree for speeding up multiplication of consecutive primes. The multiplication tree may become inefficient in terms of memory requirements for very large n, e.g., when n > 100_000_000. Therefore incorporating multiplication tree is optional in this implementation. See Demo1.java for an example case including the multiplication tree and Demo2.java for a case that excludes it. The algorithm first computes all the primes up to n, then constructs the multiplication tree of consecutive primes (optional). These operations must be executed once if a series of binomial coefficients are to be calculated. After, Goetgheluck's algorithm is applied to extract prime factors of binomial(n, k). These factors are multiplied by binary splitting in order to have a balanced multiplication in terms of representational length. If the multiplication tree is used, consecutive primes are multiplied using the tree. The tree is particularly effective in computing central binomial coefficients in terms of execution speed. However, it comes at a cost of storing it in main memory.
This implementation does not require any 3rd party libraries. It returns a BigInteger object, which is Java's native arbitrary-length integer arithmetic library. It uses fast multiplication algorithms such as Karatsuba's method, Toom-Cook multiplication, Schönhage–Strassen algorithm, etc.
[1] Goetgheluck, P. (1987). Computing binomial coefficients. The American Mathematical Monthly, 94(4), 360-365.