计算超大阶乘位数的有效方法

Question

假设我们有一个非常大的阶乘，如（10^7）！，有没有一种有效的方法来计算它的精确数字？（Wolfram alpha结果表示（10^7）！有657060位）

当然，我不能通过将值一个接一个地相乘来使用朴素的实现，因为它太慢了，无法评估结果。

我认为这个问题的解决方案最终可能是

1. 如何在不计算阶乘的情况下找到阶乘的位数
2. 如何更有效地计算阶乘（最好是BigInteger或BigDecimal）

我更喜欢1。而不是2。因为我只想知道阶乘的位数。有什么建议吗？

Answer 1

@OldCurmudgeon的解决方案很好，但你可以尝试使用Kamentsky的公式：

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);
    }
}

连接到阶乘中的计数位数-性能问题

Answer 2

将您要乘以的所有数字的日志相加应该可以做到这一点：

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);
}

指纹

Digits in 1.0E7! = 65657060

这里的逻辑是，当你在计算阶乘时乘以x，你实际上是在加log10（x），所以这里我只是把它们加起来。