Is there a fast algorithm for calculating binomial coefficients and leaving the results binary. For example, (10 choose 8) = 101101. I do not need to convert my results to base 10, instead I want to store my results as binary strings. I was asking this question before reinventing the wheel.

CodePudding user response：

I found the most efficient way. It's performing a prime factorization of the binomial coefficient, then converting to binary. I've added really fast code for finding the prime factorization of a binomial coefficient. It's called Kummer's theorem and you can use this online calculator to verify your results. The factorization algorithm is from this Jstor paper. This is a Haskell version if you're into that kind of stuff. Note you need to first generate a list of primes on your own. Then test individual primes. Also, the fundamental theorem of arithmetic is at work.

//Note primeNumber is always less than n
//Inputs n,k,primeNumber 
//Output: e (the exponent of prime number)
//Note: 0 means primeNumber is not a factor of this binomial coefficient
//Example: (n=10,k=3,primeNumber=3), e = 1
//So if you had a list of primes 2,3,5 then for each you get e=3,e=1,e=1. (10,3) = 2^3 *3^1 * 5 ^1 
int BinomialFactorization(int n, int k, int primeNumber)
{
    int a = 0;
    int b = 0;
    int exponent = 0;
    int r = 0;
    
    //Finds smaller value between n and n-k since (n choose k) == (n choose n-k)
    //Algorithm only works when k < n/2 
    if(k > (n/2))
    {   
        k = n - k; 
    }
    //Speeds up according to paper
    if(primeNumber > n - k)
    {
        return 1;
    }
    //Speeds up according to paper
    if(primeNumber > n/2)
    {
        printf("%d", 0);
        return 0;
    }
    if(primeNumber * primeNumber > n)
    {
        if(n % primeNumber < k % primeNumber)
        {   
            return 1;
        }
        else
        {   //Saw this on online calculator
            return 0;
        }
    }
    //Changing base algorithm 
    while(n > 0)
    {
        a = n % primeNumber;
        n = n / primeNumber;
        b = k % primeNumber   r;
        k = k / primeNumber;
        if(a < b)
        {
            exponent = exponent   1;
            r = 1;
        }
        else
        {
            r = 0;
        }
    }
    return exponent;    
}