Java Long类型，阶乘计算

Question

问题描述：

n! <= 2^63-1 , 求最大的n.

问题：

1. 如果不用java自带的 Long.MAX_VALUE,这个值，如何表示Long类型的最大值，我的表示方法为啥不对？

2. 我的代码如何修改才能得到正确的值呢？（因为我观察到factorial这个变量从某一刻开始变成0，可能那个时刻就已经求到了最大的n? long类型的factorial范围不够用了？）

3. 有什么优化的算法呢？

    /**
     * calculate the max value of n that n! < maxValueOf(Long)
     * long 8 bytes
     * @return max n
     */
    private static int findMax() {
        long maxLongValue = Long.MAX_VALUE;//(2<<(8*8-1))-1;
        System.out.println(maxLongValue);
        // n! <= 2^63-1, we recommend algorithm
        int n = 5;


        while(true){
            long factorial =n; //watch out here long
            int origin = n;
            while(n>1){
                factorial *= (n-1);
                n--;
            }
            System.out.println("--------" + factorial);
            n = origin;
            if((factorial+1) <= maxLongValue){
                n++;
                System.out.println("n="+ n +" factorial="+factorial);
            }else{
                n--;
                return n;
            }
        }
    }

----------下面是结果

    /**
     * calculate the max value of n that n! < maxValueOf(Long)
     * long 8 bytes
     * @return max n
     */
    private static int findMax() {
        long maxLongValue = (1L<<(8*8-1))-1;
        System.out.println(maxLongValue);
        // n! <= 2^63-1, we recommend algorithm
        int n = 5;

        long lastFactorial = n;
        
        while(true) {
            if (n == 5) {
                long firstFactorial = n;//watch out here long
                int origin = n;
                while (n > 1) {
                    firstFactorial = firstFactorial * (n - 1);
                    n--;
                }
                lastFactorial = firstFactorial;
                n = origin + 1;
            } else {
                //we do worry about currentFactorial*(n-1) cus we never let a variable store it
                //in fact we have to worry about currentFactorial*(n-1)
                if (lastFactorial <= (maxLongValue/n)) {
                    if(n==17){
                        System.out.println("here---for debug only");
                    }
                    lastFactorial = lastFactorial * n;
                    n++;
                } else {
                    return n - 1;
                }
            }
        }
    }

结果n=20;

----------此外还暴露一个问题，我以为，只要我计算factorialn不存储在某个变凉中就不会又问题，实际上，我太native了，看看下面这个图就知道啦。factorialn不存储，也溢出。。。

Answer 1

The factorial result uses BigInteger type.
---edited dividing line---
There is an obvious double calculation, because
n! = n * (n-1)!
So the result of each step can be reused for the result of the next number , it is enough to multiply the last factorial value incrementally, and there is no need to multiply each number in descending order.
There is a crude way to determine overflow, but it seems feasible:
After each n factorial, determine whether MAX_VALUE / (n-1) is less than the current factorial value. If so, the multiplication must have overflowed.

Answer 2

1. (1L << 63)-1 Note that you must write 1L (long literal), not 1 (int literal)(1L << 63)-1 注意必须写1L(long字面量), 不能写1(int字面量)

2. 每个long都一定不大于maxLongValue的, 所以不能用这个来判断溢出. 在已知n!没溢出时可以用(n+1)! / (n+1) == n!

3. Each long must not be larger than maxLongValue, so you cannot use this to determine overflow. When n! is known to have no overflow, you can use (n+1)! / (n+1) == n!< /code> to judge.

If you only need n (not the exact value of the factorial), you can use Stirling's formula to find the approximation of n!. But because this search range is too small... it may not be faster than counting one by one starting from 1.🎜🎜 🎜

Answer 3

1. As far as I know, you can only write the value directly without using Long.MAX_VALUE.

2. The reason why your results are wrong is because you think fatorial is thread-increasing, and you think it will slowly increase directly to maxLongValue-1, but the reality is that it will reach maxLongValue-1 at some point (n-1)! < maxLongValue-1, n! >maxLongValue, due to overflow, so n! <0, so it continues to be less than maxLongValue and enters the content of the if statement, so the program will endlessly loop. The improvement method is very simple, because 0! =1>0, so you only need to detect when factorial mutates to a negative number.

3. Maybe it can be optimized, but I won’t...

Answer 4

After carefully looking through the book:
I came to the conclusion of the first overflow and underflow rules in Java (possible loop overflow or underflow) (please criticize and correct if there is anything wrong)

Overflow: x-2(max+1);
Underflow: x+2(max+1);

You can judge overflow according to the overflow rules. .