C言語で余りがマイナスになる場合

質問

表題の通り、以下の計算をすると場合によってはcがマイナスになります。

　c = a % b

ただし、aもbも正の整数
具体的にどんな時にこの現象が起こるのかわかる方いらっしゃいますか？
また、回避策などわかりましたら教えていただきたいのですが。
よろしくお願いします。

回答No.8

rentahero · ベストアンサー

> long PowerMod_C(long a, long n, long m)
> {
> 　　unsigned long pw;
> 　　pw = 1;
(中略)
> 　　return pw;
> }

関数の引数と戻り値の型がlongなのに、pwだけunsigned longにしてもだめです。

実際に変数の値をループ1回ごとに表示させてみると

a=412, n=1423, m=64543, pw=1
a=40658, n=711, m=64543, pw=412
a=62191, n=355, m=64543, pw=34459
a=-36698, n=177, m=64543, pw=18440
a=53509, n=88, m=64543, pw=40139
a=-61389, n=44, m=64543, pw=40139
a=-9810, n=22, m=64543, pw=40139
a=2487, n=11, m=64543, pw=40139
a=53584, n=5, m=64543, pw=42215
a=-32746, n=2, m=64543, pw=10039
a=47657, n=1, m=64543, pw=10039
a=-31882, n=0, m=64543, pw=35907

この中で複数回aがマイナスになっています。

ちなみにすべての変数を、long long int (64bit int)にしてみると

a=412, n=1423, m=64543, pw=1
a=40658, n=711, m=64543, pw=412
a=62191, n=355, m=64543, pw=34459
a=45749, n=177, m=64543, pw=18440
a=35140, n=88, m=64543, pw=34550
a=47467, n=44, m=64543, pw=34550
a=49045, n=22, m=64543, pw=34550
a=23501, n=11, m=64543, pw=34550
a=2550, n=5, m=64543, pw=8610
a=48200, n=2, m=64543, pw=10880
a=14715, n=1, m=64543, pw=10880
a=54003, n=0, m=64543, pw=32560

となりました。
こちらが求めている解なのではありませんか？

ということで、途中でオーバーフローが発生しています。

回答No.7

jacta

> pw = a * pw % m の部分も　a = (a * a ) % m　の部分もすべて正の整数であるべきなのにマイナスがでて来て理解できなくなしました。

おそらく、a * a のところでオーバーフローが発生して負になっているのかと思います。

回答No.6

haniue

＞　c = a % b
の手前で、デバックを出力してみてはどうでしょうか。

printf("a=%d\nb=%d\n",a, b);
c = a % b
printf("c=%d\n",c);

で出力した結果を見せてください。
※ a, b, c はすべて int だと仮定しています。

回答No.5

jacta

例えば、次のような場合です。

int c;
unsigned int a = UINT_MAX-1, b = UINT_MAX;

a < bなので、cにはaの値がそのまま格納されますが、cの表現範囲を超えているので、処理系定義のシグナルが発生するか、処理系定義の値になります。ここで、負の値になるように処理系が定めていれば（多くはそうなります）、cは負になります。

あるいは、cもunsigned intに宣言したとしても、結果を出力するときに間違った場合、例えば

printf("%d\n", c);

のようにした場合は、やはり負になる可能性があります。

または、bが0の場合、動作が未定義になりますので、その結果としてcが負になることはあり得ます。

> また、回避策などわかりましたら教えていただきたいのですが。

まずは原因を特定しなければ、回避策はありません。

補足

longをunsigned longにしたところ正常動作しました。お騒がせしました。

ただ、ひとつ疑問に残るところがあります。はずかしながら、ソースをupしますと、

long PowerMod_C(long a, long n, long m)
{
　　unsigned long pw;
　　pw = 1;
　　while (n >= 1)
　　{
　　　　if ((n % 2) == 1)
　　　　{
　　　　　　pw = a * pw % m;
　　　　}
　　　　a = (a * a ) % m;
　　　　n = n / 2;
　　}
　　return pw;
}

これは a^n mod mを求めるプログラムですが、例えばa=412, n=1423, m=64543の時 pw=-52279となります。
pw = a * pw % m の部分も　a = (a * a ) % m　の部分もすべて正の整数であるべきなのにマイナスがでて来て理解できなくなしました。

回答No.4

chirubou

もし本当に「aもbも正の整数」ならば、余は b よりも小さい正の整数になるハズです。
No.1 さんのおっしゃるとおり、変数の型あるいは値の代入に問題があって、a か b が負の値になっている、あるいは c の出力時に負の値に見えている、のではないでしょうか。

補足

回答ありがとうございます。当方Cは初心者ですのでわからないところもあるのですが、long を unsigned long　に宣言すると解決できるかもしれません。ちょっとやってみます。

回答No.3

K_3113

おそらく、オーバーフローを起こしてるんだと思いますよ

回答No.2

Trick--o--

その「場合」をあげてくれんか。

a,b,cはintになってるか？

補足

ええと、a,b,cは共にlongで宣言しています。

回答No.1

ArukuMail

Ｃの変数の宣言の仕方がわるいとか？