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

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

　c = a % b

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

No.8 ベストアンサー 回答者： rentahero 回答日時： 2006/04/13 19:36

> 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 回答日時： 2006/04/13 18:49

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

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

No.6 回答者： haniue 回答日時： 2006/04/13 17:05

＞　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 回答日時： 2006/04/13 17:04

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

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　の部分もすべて正の整数であるべきなのにマイナスがでて来て理解できなくなしました。

補足日時：2006/04/13 17:39

No.4 回答者： chirubou 回答日時： 2006/04/13 17:01

もし本当に「aもbも正の整数」ならば、余は b よりも小さい正の整数になるハズです。

No.1 さんのおっしゃるとおり、変数の型あるいは値の代入に問題があって、a か b が負の値になっている、あるいは c の出力時に負の値に見えている、のではないでしょうか。

この回答への補足

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

補足日時：2006/04/13 17:15

No.3 回答者： K_3113 回答日時： 2006/04/13 17:00

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

No.2 回答者： Trick--o-- 回答日時： 2006/04/13 16:58

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

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

この回答への補足

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

補足日時：2006/04/13 17:13

No.1 回答者： ArukuMail 回答日時： 2006/04/13 16:52

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