Finding the number of digits in N!

A quick bit of code to find the number of digits in N!

We can use this in a couple of ways:

1. Given a target number of decimal places, we can, in a loop starting at N=1, compute the size of N!, and stop the loop at the first value who's factorial size meets or exceeds our target size, or
2. Given a target number, we can compute the size of that single factorial.

Computing a factorial for a given magnitude

The first option is to find the lowest value of N for which the size of N! meets or exceeds by the lowest amount the target magnitude.

Here, we use a feature of the last equation, and see that the number of digits in (N+1)! is equal to the number of digits in N! plus log(N+1).

Starting at 1, we loop through a computation that adds the log() of the value to a counter. We stop looping when the counter is no longer lower than the target magnitude. This gives us the magnitude of the factorial that meets our requirement. And, the loop counter will be our factorial.

/* ComputeSize.c */

#include <math.h>
#include <stdlib.h>
#include <stdio.h>

int main(int argc, char *argv[])
{
    unsigned int    minDigits;
    long            factorial = 0,
                    digits    = 0,
                    bytes     = 0;

    long            term;
    double          magnitude= 0;

    switch (argc)
    {
      case 2:
        minDigits = atoi(argv[1]);
        break;

      default:
        fprintf(stderr,"Usage: %s #_digits\n",argv[0]);
        return EXIT_FAILURE;
        break;
    }

    /* Compute factorial with lowest # digits equaling or
    ** exceeding target number of digits
    **
    ** Accepts: minDigits  - minimum number of digits that the 
    **                       target factorial must have
    ** Results: factorial  - the smallest factorial that
    **                       satisfies the specified minimum 
    **                       minimum number of digits
    **          digits     - the number of digits in the
    **                       result factorial
    **          bytes      - the number of bytes necessary to
    **                       store those digits as a binary
    **                       integer
    ** Temps:   term       - integer term for the Sigma
    **                       function
    **          magnitude  - real number of digits in target
    **                       factorial (including fractional
    **                       digits)
    **
    ** Notes:
    **   If X is value of N!, then log(X) is # digits in N!
    **   Given: N! = 1 * 2 * ... * (N-1) * N
    **    Thus: log(N!) = log(1 * 2 * ... * (N-1) * N)
    **                  = log(1) + log(2) + ... + log(N-1) + log(N)
    */

    for (term = 1; magnitude < minDigits; ++term)
       magnitude += log10((double) term); /* digits including fractionals */
    digits = ceil(magnitude);             /* round up fractional digits   */
    bytes = ceil(digits / log10(256.));   /* 8-bit bytes for binary value */
    factorial = term - 1;                 /* term that gave us digits     */

    printf("%ld! is %ld digits (%ld bytes) long\n", factorial,digits,bytes);
    return EXIT_SUCCESS;
}

This looks like...

$ ComputeSize 5000
1776! is 5002 digits (2078 bytes) long
$ 

Computing the magnitude of a given factorial

The second option is to find the the size of N! for a specified value of N, and look, scatter-gun fashion, for a size that matches our requirements.

/* FactorialSize.c */

#include <math.h>
#include <stdlib.h>
#include <stdio.h>

int main(int argc, char **argv)
{
    while (--argc)
    {
        long   l, index;
        double sum;

        if ((l = atol(*++argv)) > 0)
        {
            /* log(1) + ... + log(N-1) + log(N) */
            for (sum = 0, index = 1; index <= l; index++)
                sum += log10((double) index);

            /* CEILING[(log(1) + ... + log(N-1) + log(N))] */
            sum = ceil(sum);

            printf("%ld! is %.0f digits long\n",l,sum);
        }
        else printf("\"%s\" is not a valid value\n",*argv);
    }

    return EXIT_SUCCESS;
}

and an example execution:

$ FactorialSize 1775 1776 1777                           
1775! is 4999 digits long
1776! is 5002 digits long
1777! is 5005 digits long
$