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.

Answer 2

For large values of n, a big format is needed.
As you cannot use multiplications, it seems logical that you must implement it yourself.
In practice, as only additions are needed, it is not so difficult to implement, if we are not looking for a high efficiency.

A little difficulty anyway : you have to convert the input integer in an array of digits. As modulo is not allowed I guess, I implemented it with the help of snprintf function.

Result:

100! is 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

Note: this result is provided about instantaneously.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define NDIGITS     1000        // maximum number of digits

struct MyBig {
    int digits[NDIGITS + 2];        // "+2" to ease overflow control
    int degree;
};

void reset (struct MyBig *big) {
    big->degree = 0;
    for (int i = 0; i <= NDIGITS; ++i) big->digits[i] = 0;
}

void create_with_div (struct MyBig *big, int n) {  // not used here
    reset (big);
    while (n != 0) {
        big->digits[big->degree++] = n%10;
        n /= 10;
    }
    if (big->degree != 0) big->degree--;
}

void create (struct MyBig *big, int n) {
    const int ND = 21;
    char dig[ND];
    snprintf (dig, ND, "%d", n);
    int length = strlen (dig);
    
    reset (big);
    big->degree = length - 1;
    for (int i = 0; i < length; i++) {
        big->digits[i] = dig[length - 1 - i] - '0';
    }
}

void print (struct MyBig *big) {
    for (int i = big->degree; i >= 0; --i) {
        printf ("%d", big->digits[i]);
    }
}

void accumul (struct MyBig *a, struct MyBig *b) {
    int carry_out = 0;
    for (int i = 0; i <= b->degree; ++i) {
        int sum = carry_out + a->digits[i] + b->digits[i];
        if (sum >= 10) {
            carry_out = 1;
            a->digits[i] = sum - 10;
        } else {
            carry_out = 0;
            a->digits[i] = sum;
        }
    }
    int degree = b->degree;
    while (carry_out != 0) {
        degree++;
        int sum = carry_out + a->digits[degree];
        carry_out = sum/10;
        a->digits[degree] = sum % 10;
    }
    if (a->degree < degree) a->degree = degree;
    if (degree > NDIGITS) {
        printf ("OVERFLOW!!\n");
        exit (1);
    }
}

void copy (struct MyBig *a, struct MyBig *b) {
    reset (a);
    a->degree = b->degree;
    for (int i = 0; i <= a->degree; ++i) {
        a->digits[i] = b->digits[i];
    }
}

void fact_big (struct MyBig *ans, unsigned int num) {
    create (ans, 1);
    int temp = 1;
    while (temp <= num){
        int ctr = 0;
        struct MyBig temp2;
        reset (&temp2);
        while (ctr != temp){
            accumul (&temp2, ans);
            ctr ++;
        }
        copy (ans, &temp2);
        temp ++;
    }
    return;
}

unsigned long long int fact (unsigned int num) {
    unsigned long long int ans = 1;
    int temp = 1;
    while (temp <= num){
        int ctr = 0;
        unsigned long long int temp2 = 0;
        while (ctr != temp){
            temp2 += ans;
            ctr ++;
        }
        ans = temp2;
        temp ++;
    }
    return ans;
}

void main(){
    unsigned long long int ans;
    unsigned int num;
    
    printf("Enter a number: ");
    scanf("%u", &num);
    
    ans = fact (num);
    printf("%u! is %llu\n", num, ans);
    
    struct MyBig fact;
    fact_big (&fact, num);
    printf("%u! is ", num);
    print (&fact);
    printf ("\n");
}