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 << 63)-1 1 (int リテラル) ではなく、1L (long リテラル) を記述する必要があることに注意してください

2. 各 Long は maxLongValue より大きくてはいけないため、n! にオーバーフローがないことがわかっている場合は、(n+1)! / (n+1) == n!

   を使用して判断できます。
3. n だけが必要な場合 (階乗の正確な値ではない)、スターリングの公式を使用して n! を近似できます。ただし、この検索範囲は小さすぎるため、1 つを数えるよりも高速ではない可能性があります。 1 から順に 1 つずつ。

Answer 3

1. 私の知る限り、Long.MAX_VALUE を使用せずに値を直接書き込むことしかできません。

2. 結果が間違っている理由は、fatorial がスレッド増加であると考えており、ゆっくりと直接 maxLongValue-1 まで増加すると考えているためですが、実際には、ある時点で maxLongValue-1 に達します。 (n-1) ! maxLongValue、オーバーフローのため、n! 0 であるため、階乗が負の数に変化するときのみ検出する必要があります。

3. もしかしたら最適化できるかもしれませんが、それはしません...

Answer 4

この本を注意深く読んだ結果:
Java の最初のオーバーフローとアンダーフローのルール (ループのオーバーフローまたはアンダーフローの可能性) という結論に達しました (不適切な点があれば批判して修正してください)

オーバーフロー: x-2(max+1);
アンダーフロー: x+2(max+1);

オーバーフローは、オーバーフロー ルールに基づいて判断できます。 。