動的Javaの整数オーバーフローチェックとパフォーマンスの比較

Question

これはむしろ理論的な質問です。その言語は特にJavaですが、一般的な解決策で十分です。

long factorial(int n) 
{ 
    //handle special cases like negatives, etc. 

    long p = 1; 
    for(int i = 1; i <= n; i++) 
    { 
     p = p * n; 
    } 
    return p; 
} 

しかし、今、私はまた、（単にハードMAX_FACTORIAL_PARAMETERなどの何かをコーディングなし）階乗オーバーフローかどうかを確認したい：

は、私は些細な階乗関数を書きたかったとします。一般に、乗算中のオーバーフローのチェックは、元の入力に対して結果をチェックするのと同じくらい簡単ですが、この場合、オーバーフローはどのポイントでも発生するため、単一のループごとにより多くの除算と比較を実行するのはむしろ高価になります。

質問は、その後、二つです - すべての段階で乗算オーバーフローのチェックやハード最大許容パラメータをコーディングすることなく、オーバーフローの階乗問題を解決する方法はありますか？

そして一般的には、どのように私は黙って、それぞれに高価な検査を導入することにより、パフォーマンスを犠牲にすることなく、すべての段階で失敗する可能性があり、反復/再帰の多くの段階を伴う問題にアプローチすべきか？

Answer 1

Javaはこれを助けませんが、確かにオーバーフローを助ける言語があります。たとえば、C＃はchecked keywordを提供します。この機能の下には、おそらくoverflow flagの形式のハードウェアサポートが使用されています。最も簡単な方法は、最大「n」の値をハードコーディングです。この特定の場合には

Answer 2

特定の問題によって異なります。カーブスケッチやその他の数学的解析を行うことができます。

自分の与えられた例では、それだけですべてのループでチェックするのがベストでしょう。 O（n）= O（n + n）= O（2n）= O（n）のため複雑さのクラスを変更することさえないので、時間がかかりません。ほとんどの場合、シンプルなチェックを行うのが最善の方法です。コードをきれいにして保守しやすくするためです。

Answer 3

各ステップで乗算オーバフローをチェックしたり、最大許容パラメータをハードコーディングすることなく、オーバーフローの階乗問題を解決する方法はありますか？

号

そして一般的には、どのように私は黙って、それぞれに高価な検査を導入することにより、パフォーマンスを犠牲にすることなく、すべての段階で失敗する可能性があり、反復/再帰の多くの段階を伴う問題にアプローチすべきか？

私はあなたがJavaでできるとは思いません。

いくつかの以前の整数演算がオーバーフローした場合に「oveflow」ビットを設定し、マシン命令セットが、ほとんどのプログラミング言語は、それを利用する方法を提供していません。 C＃は（IIRC）Adaと同様に例外です。

Answer 4

。スピードが重要だった場合は、可能なすべての値を配列に格納し（多くはない）、何も計算しません。 ;）

long結果を改善するには（それほど優れていませんが単純な変更）、またはオーバーフローの問題がないBigIntegerを使用してください。;あなたはおそらく使用できるようにする）Javaでは

Answer 5

は、オーバーフローがあなたに否定的な結果を与えるべきであることを確認してくださいなど：

long factorial(int n) 
{ 
    //handle special cases like negatives, etc. 

    long p = 1; 
    for(int i = 1; i <= n; i++) 
    { 
     p = p * n; 
    } 

    if (p < 0) 
    { 
     throw new ArithmeticException("factorial: Overflow"); 
    } 

    return p; 
} 

また、nは正以来のオーバーフローを持つ言語のために！ >（n-1）！試してみることができます：

long factorial(int n) 
{ 
    //handle special cases like negatives, etc. 

    if (n == 1 || n == 2) { return n; } 

    // Calculate (n-1)! 
    long p = 2; 
    for(int i = 3; i < n; i++) // Note changes to loop start and end. 
    { 
     p = p * n; 
    } 

    long previous = p; // (n-1)! 

    p = p * n; // Calculate n! 

    if (p < previous) 
    { 
     throw new ArithmeticException("factorial: Overflow"); 
    } 
    return p; 
} 

これらの方法では、1つの要因ごとに1つの小切手が必要です。

Answer 6

Java 8以降、JavaにはMath.multiplyExact()メソッドがあります。これは内部的にオーバーフローをチェックします。このメソッドは「組み込み関数」（see here for a list）なので、Java実装は可能であれば専用の低レベルのマシン命令に置き換えられ、おそらくCPUオーバーフローフラグをチェックするだけで、チェックが非常に高速になります。

Btw（JDK 1.8.0_40ではJDK 1.0.8_05よりもはるかに高速です）