n!/k! with long input only works for small numbers, how does it work for eg. n=20 k=19

Question

Hey the method works for a few numbers, but often it just randomly gives out some huge numbers, i am a bit confused about the datatypes used, the result should fit in long, anyone can help? The formula is n!/k!.

I try to get the right result which fits in long

public static long penguPermutation(long n, long k) {
    long fact1 = 1;
    long fact2 = 1;
    for(long i = 2; i <= n; i++){
        fact1 = fact1 * i;
    }
    System.out.println(fact1);
    for(long i = 2; i <= k; i++){
        fact2 = fact2 * i;
    }
    System.out.println(fact2);
    long division = fact1/fact2;
    return division;
    }

Answer 1

A long can only store numbers up to Long.MAX_VALUE, which is 9223372036854775808. 21! is 51090942171709440000, which is approximately 5.5 times larger. Consequently, the value stored in the long variables overflows and wraps around to negative numbers.

But you don't need to compute the full factorials, if you apply a little math:

Let's assume n=5 and k=3, this will give you the formula (1*2*3*4*5)/(1*2*3). This can be reduced by omitting the common factors 1, 2, and 3: (4*5)/1. This is the product of all numbers from (n-k+1) up to n.

The largest factorial that can fit into 63 bits (a long value) is 20!. Your problem is not numbers larger than 10, but numbers larger than 20.

So don't compute the full factorial, but only the product of what is really needed.

If you really must handle such large numbers, consider using BigInteger, but be aware of the performance penalty.