Get the factorial of a number without using multiplication

Question

I need to compute the factorial of a number without using the multiplication operator. Because of this restriction, I directly tried to use repeated addition. It kind of works. However, my program is struggling to get the factorial of larger numbers. Is there a better way to solve the problem?

Here is my code:

void main(){
     unsigned long num = 0, ans = 1, temp = 1;

    printf("Enter a number: ");
    scanf("%lu", &num);

    while (temp <= num){
        int temp2 = 0, ctr = 0;
        while (ctr != temp){
            temp2 += ans;
            ctr ++;
        }
        ans = temp2;
        temp ++;
    }

    printf("%lu! is %lu\n", num, ans);
}

Answer 1

You can implement a faster (than repeated addition) multiply function using bit shifts and addition to perform "long multiplication" in binary.

unsigned long long mul_ull(unsigned long long a, unsigned long long b)
{
    unsigned long long product = 0;
    unsigned int shift = 0;

    while (b)
    {
        if (b & 1)
        {
            product += a << shift;
        }
        shift++;
        b >>= 1;
    }
    return product;
}

EDIT: Alternative implementation of the above using single bit shifts and addition:

unsigned long long mul_ull(unsigned long long a, unsigned long long b)
{
    unsigned long long product = 0;

    while (b)
    {
        if (b & 1)
        {
            product += a;
        }
        a <<= 1;
        b >>= 1;
    }
    return product;
}

In practice, whether or not this is faster than repeated addition depends on any optimizations done by the compiler. An optimizing compiler could analyze the repeated addition and replace it with a multiplication. An optimizing compiler could also analyze the code of the mul_ull function above and replace it with a multiplication, but that may be harder for the optimizer to spot. So in practice, it is perfectly reasonable for the repeated addition algorithm to end up faster than the bit-shift and addition algorithm after optimization!

Also, the above implementations of the mul_ull functions will tend to perform better if the second parameter b is the smaller of the numbers being multiplied when the one of the numbers is much larger than the other (as is typical for a factorial calculation). The execution time is roughly proportional to the log of b (when b is non-zero) but also depends on the number of 1-bits in the binary value of b. So for the factorial calculation, put the old running product in the first parameter a and the new factor in the second parameter b.

A factorial function using the above multiplication function:

unsigned long long factorial(unsigned int n)
{
    unsigned long long fac = 1;
    unsigned int i;

    for (i = 2; i <= n; i++)
    {
        fac = mul_ull(fac, i);
    }
    return fac;
}

The above factorial function is likely to produce an incorrect result for n > 20 due to arithmetic overflow. 66 bits are required to represent 21! but unsigned long long is only required to be 64 bits wide (and that is typically the actual width for most implementations).

EDIT 2023-06-07

A slightly longer factorial() function with the same restrictions on the value of n can use less than half the number of multiplications. This method is based on that shown in https://scicomp.stackexchange.com/q/42510 after the edit of March 21, 2023.

unsigned long long factorial(unsigned int n)
{
    unsigned long long fac;
    unsigned int m;
    unsigned int i;

    if (n <= 1)
    {
        fac = 1;
    }
    else
    {
        if ((n & 1) == 0)
        {
            m = n;
            n -= 2;
        }
        else
        {
            m = n + n;
            n -= 3;
        }
        fac = m;
        while (n > 0)
        {
            m += n;
            fac = mul_ull(fac, m);
            n -= 2;
        }
    }
    return fac;
}

For example, it calculates 9! = 18·24·28·30 = 362880, 10! = 10·18·24·28·30 = 3628800.