Search code examples
javaalgorithmmathfactorial

Fast algorithm to calculate n! / (q!)^r

What is the fastest algorithm and the code implementation to calculate the value of the following expression?

n! / (q!)r

My code

public static double timesbyf(int n,int q,int qt,int qp1,int qp1t)
{
    int totaltimes=qt+qp1t;
    double ans=1.0d;
    for(int i=1;i<=totaltimes;i++)
    {
        if(i<=qt)
        {
            for(int j=q;j>0;j--)
            {
                ans=ans*((double)n/(double)j);
                n--;
            }
        }
        else
        {
            for(int j=qp1;j>0;j--)
            {
                ans=ans*((double)n/(double)j);
                n--;
            }

        }
    }
    while(n>0)
    {
        ans=(ans*n)%3046201;
        n--;
    }
    return ans;
}

That is, n! divided by q! r times.

I'm given that n ≤ 3 × 106 and that q < n, and it is guaranteed that (q!)r will cleanly divide n!.

Solution

  • I think it's a very bad idea to calculate two very large numbers and hope that the quotient comes out as something sensible.

    Start by taking the natural log:

    ln(n!/(q!)^r) = ln(n!) - r*ln(q!)

    You can use gammaln() for the two function values, simplify, then take exp() to get the result you want:

    value = exp(gammln(n+1) -r*gammln(q+1))

    Numerical Recipes has a nice chapter on how to implement functions like gammln().