CODEWITHSUNDEEP
javafactorial
Truthseeker Rangwan
Truthseeker Rangwan

Reputation: 231

Efficient way to count the digits of very big factorials

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

  1. How to find the digit of the factorial without calculating the factorial
  2. 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?

Upvotes: 2

Views: 1094

Answers (2)

Michu93
Michu93

Reputation: 5689

@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

Upvotes: 0

OldCurmudgeon
OldCurmudgeon

Reputation: 65813

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.

Upvotes: 4

Related Questions