問題タブ [integer-overflow]

そのため、私は最近、ミラーラビン素数性テストの実装に取り​​組んでいます。これは、c ++に慣れるために行っている楽しいプロジェクトであり、64ビットで作業する必要がないため、すべての32ビット数値のスコープに制限しています。しばらく。追加のボーナスは、アルゴリズムがすべての32ビット数に対して決定論的であるということです。したがって、テストする監視対象を正確に知っているので、効率を大幅に向上させることができます。

したがって、数値が小さい場合、アルゴリズムは非常にうまく機能します。ただし、プロセスの一部はべき乗剰余、つまり（num ^ pow）％modに依存しています。したがって、たとえば、

これが、このべき乗剰余に使用しているコードです。

すでにお察しのとおり、引数がすべて非常に大きい場合に問題が発生します。たとえば、番号673109の素数性をテストする場合、ある時点で次のことを見つける必要があります。

（2 ^ 168277）％673109

現在、2 ^ 168277は非常に大きな数であり、プロセスのどこかでテストがオーバーフローし、誤った評価になります。

逆に、次のような議論

4000111222 ^ 3％1608

また、ほとんど同じ理由で、正しく評価されません。

このオーバーフローを防止したり、正しい結果を生成するように操作したりできる方法で、べき乗剰余の提案がある人はいますか？（私の見方では、オーバーフローはモジュロの別の形式、つまりnum％（UINT_MAX + 1）です）

まず、私が説明している問題がどのように、そしてなぜ起こるかを理解していると言わせてください。私はコンピュータ サイエンスを専攻しており、オーバーフロー/アンダーフローと符号付き/符号なしの算術演算を理解しています。(このトピックに慣れていない人のために、Apple のセキュア コーディング ガイドでは、整数オーバーフローについて簡単に説明しています。)

私の質問は、そのようなエラーが検出された後の報告と回復についてです。より具体的には、Objective-C フレームワークの場合です。(私はCHDataStructuresを作成して維持しています。) オブジェクトを格納するためのメモリを割り当て、必要に応じて動的に拡張するコレクション クラスがいくつかあります。オーバーフローに関連するクラッシュはまだ見たことがありません。これはおそらく、私のテスト ケースでほとんど正常なデータが使用されているためです。ただし、検証されていない値が与えられると、物事はかなり急速に爆発する可能性があり、それを防ぎたい.

これが発生する一般的なケースを少なくとも2 つ特定しました。

1. 呼び出し元が、非常に大きな符号なし値 (または負の符号付き値) を に渡します-initWithCapacity:。
2. 容量を動的に拡張するのに十分な数のオブジェクトが追加され、容量がオーバーフローを引き起こすほど大きくなりました。

簡単な部分は、オーバーフローが発生するかどうかを検出することです。(たとえば、length * sizeof(void*)バイトを割り当てようとする前にlength <= UINT_MAX / sizeof(void*)、このテストに失敗すると、製品がオーバーフローし、必要なよりもはるかに小さいメモリ領域が割り当てられる可能性があることを意味するため、チェックすることができます。それをサポートするプラットフォームでは、checkint.h APIは別の選択肢があります。) より難しい部分は、それを適切に処理する方法を決定することです。最初のシナリオでは、発信者の方が障害に対処するための準備が整っている (または少なくとも考え方が整っている) 可能性があります。2 番目のシナリオは、オブジェクトがコレクションに追加されるコード内の任意の場所で発生する可能性があり、これはまったく決定論的ではない可能性があります。

それでは、私の質問は次のとおりです。このような状況で整数オーバーフローが発生した場合、「善良な市民」Objective-C コードはどのように動作すると予想されますか? (理想的には、私のプロジェクトは Cocoa の Foundation と同じ精神のフレームワークであるため、最大の「インピーダンス マッチング」のために動作する方法をモデル化したいと考えています。私が見つけた Apple のドキュメントでは、これについてはすべてです。） いずれにせよ、エラーを報告することは当然のことだと思います。オブジェクトを追加する API (シナリオ 2 を引き起こす可能性があります) はエラー パラメーターを受け入れないため、問題を解決するために実際に何ができるでしょうか? そのような状況で本当に大丈夫と考えられるのは何ですか？もっとうまくやれるなら、故意にクラッシュしやすいコードを書くのは嫌です...

Javaバックエンドで例外をスローする代わりに、HTML入力でフロントエンド検証を実行しようとしています。

C++ で、長いデータ型がオーバーフローするずっと前に、奇妙な問題が発生しています。私が行っていること (これまでのところ成功) は、範囲 [-32767,32767] が [-1.0,1.0] にマップされるように、整数をフロートのように動作させることです。つまずくのは、1.0 より大きい浮動小数点数を表す大きな引数を使用する場合です。

出力として得られるものは次のとおりです。

したがって、times(98301,32767) は 3.0*1.0 に類似しています。このコードは、times の引数が 32767 (1.0) 未満の場合に完全に機能しますが、上記の引数を使用した中間ステップで 64 ビットの long がオーバーフローすることはありません。

何か案は？

Microsoft は、GetTickCount のドキュメントで、ティック カウントを比較して間隔が経過したかどうかを確認することはできないと既に述べています。例えば：

不正解 (疑似コード):

上記のコードは、ティック カウンターのロールオーバーの影響を受けやすいため、不適切です。たとえば、クロックがその範囲の終わりに近づいているとします。

次に、チェックを実行します。

GetTickCount はよりも大きいため、これはすぐに満たされendTimeます。

ソリューション

代わりに、常に 2 つの時間間隔を減算する必要があります。

同じ数学を見ると：

コンパイラが特定の方法で動作する C/C++ では、これはすべてうまくいきます。

しかし、Delphi はどうでしょうか。

しかし、( {Q+}, ) のオーバーフロー チェックを使用して Delphi で同じ計算を実行すると、 TickCountがロールオーバー{$OVERFLOWCHECKS ON}すると、2 つのティック カウントの減算により EIntOverflow 例外が生成されます。

この問題の意図した解決策は何ですか?

編集：一時的にオフにしようとしましたOVERFLOWCHECKS：

しかし、減算は依然としてEIntOverflow例外をスローします。

キャストとより大きな中間変数型を含む、より良い解決策はありますか?

アップデート

私が尋ねた別のSOの質問では、なぜ{$OVERFLOWCHECKS}うまくいかないのかを説明しました。どうやら、行レベルではなく、関数レベルでのみ機能します。したがって、以下は機能しませんが：

以下は機能します：

アンダーフローを引き起こすコードが少しあります：

減算自体はオーバーフロー（アンダーフロー）を生成しますが、DelphiでEIntOverflow例外をスローしたくありません。だから私はオーバーフローチェックを無効にすることによってオーバーフローチェックコードの生成を無効にしてみます：

ただし、OVERFLOWCHECKS OFFオプションを使用しても、例外がスローされます。そして、生成されたコードにはまだチェックが含まれています：

上のドキュメントのリマインダー$Q：

オーバーフローチェック

タイプスイッチ
構文{$Q+}または{$Q-}
{$OVERFLOWCHECKSON}または{$OVERFLOWCHECKSOFF}
デフォルト{$Q-}
{$OVERFLOWCHECKSOFF}
スコープローカル

備考

$ Qディレクティブは、オーバーフローチェックコードの生成を制御します。{$ Q +}状態では、特定の整数算術演算（+、-、*、Abs、Sqr、Succ、Pred、Inc、およびDec）のオーバーフローがチェックされます。これらの整数算術演算のそれぞれのコードの後に​​、結果がサポートされている範囲内にあることを確認する追加のコードが続きます。オーバーフローチェックが失敗すると、EIntOverflow例外が発生します（または、例外処理が有効になっていない場合はプログラムが終了します）。

$ Qスイッチは通常、範囲チェックコードの生成を有効または無効にする$Rスイッチと組み合わせて使用​​されます。オーバーフローチェックを有効にすると、プログラムの速度が低下し、プログラムがいくらか大きくなるため、デバッグにのみ{$Q+}を使用してください。

$OVERFLOWCHECKS OFFオーバーフローチェックコードの生成を無効にするにはどうすればよいですか？

メイソンの答えはうまくいった。改訂されたコードは次のとおりです。

グーグルクローラーの場合、別の質問の言い回し：Delphiでオーバーフローチェックを一時的に無効にする方法は？

MATLAB/Octave でいくつかの VHDL コードの検証ツールに取り組んでいます。したがって、「実際の」オーバーフローを生成するデータ型が必要です。

あとで、変数のビット幅を定義できれば助かりますが、今はそれほど重要ではありません。

C に似た例を作成すると、変数が 0 より小さくなるまで増加し、永久に回転します。

私が試した別のアプローチは、数値が変更されるたびに呼び出されるカスタム「オーバーフロー」ルーチンでした。このアプローチは非常に遅く、実用的ではなく、すべてのケースでまったく機能しませんでした。助言がありますか？

データセットの線形トレンドラインを見つけようとしています。セットには、日付（x値）とスコア（y値）のペアが含まれています。このコードのバージョンをアルゴリズムの基礎として使用しています。

私が得ている結果は、数桁ずれています。ミリ秒数が非常に多いDateのgetTimeメソッドを使用しているため、丸め誤差またはオーバーフローに問題があると思います。エラーを最小限に抑えて正しい結果を計算する方法について誰かが提案を持っていますか？

私はデータベースアプリケーションを実装しており、データベースとしてJavaDBとMySQLの両方を使用します。テーブルに整数型のID列があり、値にデータベースのauto_increment-functionを使用しています。

しかし、20億（または40）億を超える投稿を取得し、整数では不十分な場合はどうなりますか？整数がオーバーフローして続行しますか、それとも処理できる例外がスローされますか？

はい、データ型としてlongに変更できますが、それが必要な場合はどうすれば確認できますか？また、ID列にlong asデータ型を使用すると、last_inserted_id（）関数の取得に問題があると思います。