c言語 永遠ループしない理由がわからない

Question

前提・実現したいこと

このプログラムが有限時間で終了する理由を証明したいのですが、なぜ終了するのかわからないです。
■には32ビットの符号なし整数で何らかの奇数が入ります。

ヒントとして以下の性質を使っていいとのことですが本当にわかりません。
• a と b が互いに素 (最大公約数が 1) の自然数であるならば、ma − nb = 1 を満たす自然数 m, n が存在する
(「中国剰余定理」の特別な場合)
• 任意の整数 x1, x2, x3, y1, y2, z に対し、
⋆ x1 ≡ x1 (mod z) (z が 0 でなければ)
⋆ x1 ≡ x2 (mod z) ならば x2 ≡ x1 (mod z)
⋆ x1 ≡ x2 (mod z), x2 ≡ x3 (mod z) ならば x1 ≡ x3 (mod z)
⋆ x1 ≡ x2 (mod z), y1 ≡ y2 (mod z) ならば x1 + x2 ≡ y1 + y2 (mod z)

該当のソースコード

#include <stdio.h>
int main(void)
{
unsigned int n = ■ , t = 0;
while(t != 1) t += n;
return 0;
}

Answer 1

32bit unsigned intの最大値は2の32乗-1=4294967295である。Cで符号無し整数の演算が最大値を超えた場合、最大値に1足した数(4294967296)の剰余になる(ラップアラウンド)。

※数式はCのコードと言うことではなく、Cのコード風の演算子になっている純粋な数式です。オペレーターの意味はCと同じですが、各式の計算でオーバーフローやラップアラウンドしないと考えてください。

あるi回まで足していったとき、tはi*nだが、これが4294967296を越えていないとする。次のi+1回、つまり、(i+1)*nで越えてしまうとすると、その値は((i+1)*n)%4294967296であり、次の(i+2)*nは((i+1)*n)%4294967296+n=((i+1)*n)%4294967296+n%4294967296であるが、剰余の定理により((i+1)*n+n)%4294967296=((i+2)*n)%4294967296になる(nは4294967296より小さい)。これは、4294967296を越える度に同じ計算となるので、ある回数xについて、

t = (x * n) % 4294967296

と言う等式が成り立つ。これが1になるxがもし存在するなら、

1 = (x * n) % 4294967296

となる。(x * n) / 4294967296をqとすると、次の式が成り立つ。

4294967296 * q + 1 = x * n

つまり

x * n - q * 4294967296 = 1

nは4294967295以下の奇数であり、4294967296は2の32乗であるから、互いに素である。「中国剰余定理」の特別な場合により、上の式が成り立つ、xとqの組合せは必ず存在する。

よって、どのようなnであってもxは存在し、その回数分でループが停止する。

---

途中の説明であやしいところがありますが、筋書きはあっていると思います。

Answer 2

既に指摘があるように、オーバーフローでしょうね。
そして、奇数を加算がポイントでしょう。 (偶数だと、絶対に止まりません)

途中の経過を出力すれば、分かるとか。
半端な出力では無いと思いますが、、、と始めてみたら、まだ終わらない。(数分以上)
最大、2の32乗 + 1 の出力だった。(最少は n=1)

Answer 3

ｔがオーバーフローするだけのはなしですね。
そして、たまたま１になった時に終了

Comments

[terataillll]

返信ありがとうございます！！オーバーフローするということは理解しました！
たまたま１になるということについて詳しく聞きたいです。
ヒントの使い道もまだわからないので最終絶対１になるようになっているのかなと考えています。

[y_waiwai]

３２ビットの数値から、１回オーバーフローするとどの数値から始まるのか算出できるでしょ。
そこから、２回め、３回目のオーバーフローでどこから始まるか算出していくと、１になるには何回目のオーバーフローかってのはわかりますよ

[thkana]

日常的にはオーバーフローと言ってしまうことが多い現象(?)ですけれど、Cの規格書に「符号無しオペランドを含む計算は，決してオーバフローしない」とあるので証明問題として答える場合にはオーバーフローという言葉は適切でないかも知れませんね。