2

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?

Truthseeker Rangwan
  • 231
  • 3
  • 10
  • 1
    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: http://mathforum.org/library/drmath/view/68245.html – forgivenson Jul 31 '14 at 15:26
  • possible duplicate of [How to work out how many bits the result of a factorial should take up as a number?](http://stackoverflow.com/questions/13583169/how-to-work-out-how-many-bits-the-result-of-a-factorial-should-take-up-as-a-numb) – mbeckish Jul 31 '14 at 15:27

2 Answers2

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.

OldCurmudgeon
  • 64,482
  • 16
  • 119
  • 213
  • At least it doesn't need BigInteger memory hogging. – Artjom B. Jul 31 '14 at 15:32
  • This is only as accurate as your log calculations are – Kevin L Jul 31 '14 at 15:36
  • @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. – OldCurmudgeon Jul 31 '14 at 15:39
  • 2
    @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 – Kevin L Jul 31 '14 at 15:43
  • 1
    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` – king_nak Aug 01 '14 at 07:55
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

Michu93
  • 5,058
  • 7
  • 47
  • 80