Efficient way to count the digits of very big factorials

Question

Suppose that we have a very large factorial such as (10^7)!, Is there an efficient way to count its exact digits? (Wolfram alpha result says (10^7)! has 65,657060 digits)

Of course, I can't use the naive implementation by successively multiplying the value one by one since it will be too slow to evaluate the result.

I think the solution to this question might ended up in either

How to find the digit of the factorial without calculating the factorial
How to compute the factorial more efficiently (BigInteger or BigDecimal is preferable)

I would prefer 1. rather than 2. since I just want to know how many digits of the factorial. Any suggestion?

I think this is more of a math question than a programming question. I haven't tried it, but a quick google search found this: mathforum.org/library/drmath/view/68245.html — forgivenson
– forgivenson, Commented Jul 31, 2014 at 15:26
possible duplicate of How to work out how many bits the result of a factorial should take up as a number? — mbeckish
– mbeckish, Commented Jul 31, 2014 at 15:27

OldCurmudgeon · Accepted Answer · 2014-08-01 14:39:21Z

4

Adding up the logs of all the numbers you would multiply by should do the trick:

public long facDigits(long n) {
    double logFacN = 0;
    for (long i = 2; i <= n; i++) {
        logFacN += Math.log10(i);
    }
    return (long) logFacN + 1;
}

public void test() {
    double tenToThe7th = Math.pow(10, 7);
    long digits = facDigits((long) tenToThe7th);
    System.out.println("Digits in " + tenToThe7th + "! = " + digits);
}

prints

Digits in 1.0E7! = 65657060

The logic here is that as you multiply by x while calculating the factorial you are actually adding log10(x) digits so here I just add those up.

edited Aug 1, 2014 at 14:39

answered Jul 31, 2014 at 15:29

OldCurmudgeon

66k18 gold badges126 silver badges220 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

Artjom B. Over a year ago

At least it doesn't need BigInteger memory hogging.

Kevin L Over a year ago

This is only as accurate as your log calculations are

OldCurmudgeon Over a year ago

@KevinL - You are correct - but it does seem to perform effectively up to 10^7! which I was surprised at. It is certainly quicker than calculating log10(10^7!). It gets the answer in 1.356s on my rig.

Kevin L Over a year ago

@OldCurmudgeon a double gives you 15 digits precision, which once you convert to log calculations, since your answer is 8 digits, you have about 7 digits to use for rounding, which apparently is close enough

king_nak Over a year ago

This is almost 100% correct. You should 1 to the result, since # of digits is calculated by floor(log(N))+1. The floor is done by the cast to long, and the log of a product equals the sum of the logs of the summands, which you calculate in your loop. You're just short of the +1

Michu93 · Accepted Answer · 2021-05-19 06:43:22Z

0

@OldCurmudgeon's solution is good but you can try to use Kamentsky's formula:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int numOfTests = Integer.parseInt(in.readLine());

        in.lines()
                .limit(numOfTests)
                .map(n -> Integer.parseInt(n))
                .forEach(n -> System.out.println(KamenetskyFormula(n)));
    }

    private static long KamenetskyFormula(int n) {
        if (n < 2) {
            return 1;
        }
        double x = n * Math.log10(n / Math.E) + Math.log10(2 * Math.PI * n) / 2.0;
        return (long) (Math.floor(x) + 1);
    }
}

connected to Count number of digits in factorial - performance issue

edited May 19, 2021 at 6:43

answered May 19, 2021 at 6:18

Michu93

5,8578 gold badges61 silver badges97 bronze badges

1 Comment

Nikolai Shevchenko Over a year ago

Nice and fast, but Kamenetsky formula gives approximate result and can fail for some numbers

Collectives™ on Stack Overflow

Efficient way to count the digits of very big factorials

2 Answers 2

5 Comments

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

5 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related