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

階乘結果用BigInteger型別。
---編輯的分割線---
有個很明顯的重複計算，因為
n! = n * (n-1)!
所以每一步的結果都可以為下個數的結果所復用，遞加乘上次階乘值即可，不必每個數遞減相乘。
判定溢位有個很土的辦法，不過貌似可行：
每次n階乘後判斷MAX_VALUE / (n-1) 是否小於 當前階乘值，是的話相乘必然溢出了。

Answer 2

1. (1L 注意必須寫1L(long字面量), 不能寫1(int字面量)(1L << 63)-1 注意必须写1L(long字面量), 不能写1(int字面量)

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

3. 每個long都一定不大於maxLongValue的, 所以不能用這個來判斷溢出. 在已知n!沒溢出時可以用(n+1)! / (n+1) == n!來判斷.

如果你只需要n (不要階乘的精確值), 可以用斯特林公式求n!的近似. 但是因為這個搜索範圍太小..未必比從1開始逐個算要快.🎜🎜 🎜

Answer 3

1. 據我所知，不用Long.MAX_VALUE你就只能直接寫數值了。

2. 你的結果之所以不對，是因為你以為fatorial是線程遞增的，你認為他會慢慢的遞增直接到達maxLongValue-1，然而現實是它會在某時（n-1）！ maxLongValue,因溢出，故n！ 0,所以你只要偵測factorial何時突變為負數即可。

3. 可能可以優化，然而我不會…

Answer 4

經過仔細翻書查看：
得出java中，第一次上溢和下溢規律（可能循環上溢或下溢）（有不妥的地方請給予批評和指正）

上溢： x-2(max+1);
下溢： x+2(max+1);

可以根據溢出規則來，判斷溢位。 。