4

これはかなり理論的な質問なので、言語は特に 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 などをハードコーディングする必要はありません)。一般に、乗算中のオーバーフローのチェックは、元の入力に対して結果をチェックするのと同じくらい簡単ですが、この場合、オーバーフローはどの時点でも発生する可能性があるため、すべてのループでより多くの除算と比較を実行すると、かなりコストがかかります。

問題は 2 つあります。すべてのステップで乗算オーバーフローをチェックしたり、最大許容パラメーターをハードコーディングしたりせずに、オーバーフローの階乗問題を解決する方法はありますか?

そして一般的に、各段階で高価なチェックを導入することでパフォーマンスを損なうことなく、すべての段階で静かに失敗する可能性がある反復/再帰の多くの段階を含む問題にどのようにアプローチすればよいでしょうか?

4

6 に答える 6

1

Javaはこれを支援しませんが、オーバーフローを支援する言語は確かにあります。たとえば、C＃はcheckedキーワードを提供します。その下で、この機能はおそらくオーバーフローフラグの形でハードウェアサポートを使用します。

于 2011-07-17T05:40:27.187 に答える
1

それはあなたの特定の問題に依存します。たぶん、曲線のスケッチやその他の数学的分析を行うことができます。

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

于 2011-07-17T01:47:40.357 に答える
1

この特定のケースで行う最も簡単な方法は、最大の「n」値をハードコーディングすることです。速度が重要な場合は、すべての可能な値を配列に格納し (それほど多くはありません)、何も計算しません。;)

メソッドの使用結果を改善したい場合long(それほど良くはありませんが、単純な変更です)、またはオーバーフローの問題がない BigInteger を使用します。;)

于 2011-07-17T06:46:43.327 に答える
0

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

いいえ。

そして一般的に、各段階で高価なチェックを導入することでパフォーマンスを損なうことなく、すべての段階で静かに失敗する可能性のある反復/再帰の多くの段階を含む問題にどのようにアプローチすればよいでしょうか?

Javaではできないと思います。

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

于 2011-07-17T04:07:06.147 に答える
0

Java 8以降、JavaにはMath.multiplyExact()メソッドがあります。これは、オーバーフローを内部的にチェックします。このメソッドは「組み込み」であるため (リストについては、こちらを参照)、Java 実装は、可能であれば専用の低レベル マシン命令に置き換えられ、CPU オーバーフロー フラグをチェックするだけで、チェックが非常に高速になります。

ところで、これはJDK 1.0.8_05と比較してJDK 1.8.0_40ではるかに高速であるように見えることに注意してください。

于 2016-08-23T14:00:46.440 に答える
-1

Java では、オーバーフローによって負の結果が得られるはずなので、おそらくそれをチェックとして使用できます。

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 つのチェックのみが必要です。

于 2011-07-17T09:48:51.937 に答える