以下は、あるオープンソース プロジェクトの rand() からコピーされたもので、LCG を使用しています。
rand_next = rand_next * 1103515245L + 12345L; //unsigned long rand_next
古典的なLCGは次のとおりです。
次 = (次 * a + c) mod M
明らかに、ここで M は 2^32 です。
私を混乱させているのは、rand_next * 1103515245L です。ここで、オーバーフローが発生すると確信しています。いくつかの rand() 実装を見てみましょう。異なる a と c を使用することを除いて、すべてこの方法を取ります。
そのオーバーフローは有害ですか？そうでなければ、なぜですか？
ありがとう
これで問題ありません。C99 仕様によると、符号なしの long 演算の場合、結果は同じですが、モジュロ 2 32 (§6.2.5)に縮小されます。
A computation involving unsigned operands can never overflow, because a result
that cannot be represented by the resulting unsigned integer type is reduced
modulo the number that is one greater than the largest value that can be
represented by the resulting type.
したがって、この動作は実際には「オーバーフロー」ではありませんが、この回答では簡単にするためにそれを呼び出します。剰余算術については、
a1 ≡ b1 (mod m)
a2 ≡ b2 (mod m)
示す
a1 + a2 ≡ b1 + b2 (mod m)
我々は持っています
Next * a ≡ k (mod 2^32)
どこkにNext * a「オーバーフロー」がありますか。だから、以来M = 2^32、
Next * a + c ≡ k + c (mod M)
「オーバーフロー」がある場合の結果は、モジュラ演算で「オーバーフロー」がない場合と同等であるため、式は問題ありません。modulo を減らすM = 2^32と、同じ結果が得られます。
を で乗算signed longしunsigned longます。したがって、 の両方のオペランドの*整数変換ランクは同じです。この場合、以下のルール (C++11、§5/9、項目 5、サブ項目 3) が適用されます。
[...]符号なし整数型を持つオペランドのランクが他のオペランドの型のランク以上の場合、符号付き整数型のオペランドは符号なし整数型のオペランドの型に変換されます。
unsigned longしたがって、乗算が評価される前に、両方のオペランドが暗黙的に変換されます。したがって、符号なしの算術演算と符号なしの結果が得られ、加算演算にも同じ規則が適用されます。
符号なしの整数オーバーフローは明確に定義されているため (これを詳細にカバーするために拡張された Zong Zhen Li の回答を参照してください)、問題はありません。
C に関しては (C++ とは対照的に)、C11 には §6.3.1.8/1 に同じ規則があります。
[...]符号なし整数型を持つオペランドのランクが他のオペランドの型のランク以上の場合、符号付き整数型のオペランドは符号なし整数型のオペランドの型に変換されます。