Q&A
> なぜなのでしょうか？
他の手段として何が思いつきますか？
初歩的な質問ですみません。
参考書のじゃんけんゲームのプログラムでコンピューター側の手を乱数で
rand()%3;
と表現しているのですが、
ある特定の範囲の乱数を使うために、剰余を用いるのはなぜなのでしょうか？
いまいち理解できず、質問させていただきました。
どなたか分かりやすく教えてくださると助かります。
よろしくお願いいたします。
https://detail.chiebukuro.yahoo.co.jp/qa/question_detail/q14225065439
https://teratail.com/help#posted-otherservice
「質問内容にマルチポストをする理由を書き、他のサイトの投稿へのリンクを貼ってください。また、解決した際には必ずteratail及びすべての投稿に解決した旨と、どのように解決したかを記載してください」
回答がこれだけ付いているのに何の反応もなく、別のサイトに聞きに行くのはなぜでしょうか？
回答の方向性が思ったものと違うなら修正するのは質問者の役目です。
何がどこまでわかっているかわからない以上、適切な回答をつけるのは難しいと言わざるを得ません。
私がいうのもナンですが、ツッコミを入れたのが私ですので。
この質問が2020/05/16 22:31、回答がついたのが22:33に2件。
知恵袋の質問が2020/5/16 22:34:31で確かに最初の回答がついた後ではありますが、この僅差ですから、最初からバラ撒きを予定していたということであって「回答がついているのに別のサイトに聞きに行った」わけではないでしょう。
余計にたちが悪いですね。ログインはしているようなので、自分の意見を書いてください。
ご返信遅くなり申し訳ございません。
わざわざ他のサイトで質問したページを貼って頂きありがとうございます。
マルチポストはダメだったのですね。こちらの注意不足でした。不快な思いにさせてしまい申し訳ございませんでした。注意してくださりありがとうございます。
いろんな方の意見が聞ければと思って、複数のサイトで質問させて頂いていました。
> 「質問内容にマルチポストをする理由を書き、他のサイトの投稿へのリンクを貼ってください。また、解決した際には必ずteratail及びすべての投稿に解決した旨と、どのように解決したかを記載してください」
と書いてあります。この通りにしてください。
また、この質問がいまだ解決しない理由がわかりません。その理由も合わせて書いてください。質問の下に「編集」というボタンがあるはずです。
回答9件
0
そもそもMudulo biasという問題によって、生成確率が一様にならないため、乱数の範囲調整に剰余を用いることが誤りです。また偏りなく範囲を調整するのは全く容易ではないので、C++11のuniform_int_distributionを利用するべきです。
- いつからその方法で偏りのない乱数が得られると錯覚していた？ - アスペ日記
- Cのrand()よりmt19937の方が速いことがあるという話 - Educational NLP blog
- random_shuffle - cpprefjp C++日本語リファレンス
- uniform_int_distribution - cpprefjp C++日本語リファレンス
まあせっかくなので、rand()の性能が悪いことで有名なMSVCでもcateyeさんのコードを実験してみました。
cpp
1#include <iostream> 2#include <cstdlib> 3#include <random> 4// 5using std::cout; 6using std::endl; 7// 8const int R_MAX = 1000000; 9 10int main(void) 11{ 12 int rr[4] = { 0 }; 13 int mr[4] = { 0 }; 14 15 for (int i = 0; i < R_MAX; ++i) { 16 rr[(rand() >> 7) % 3]++; 17 } 18 // 19 std::mt19937 mt(std::random_device{ }()); 20 std::uniform_int_distribution<int> dist(0, 2); 21 22 for (int i = 0; i < R_MAX; ++i) { 23 mr[dist(mt)]++; 24 } 25 // 26 for (int i = 0; i < 4; ++i) { 27 cout << i << ": " << rr[i] << " " << mr[i] << endl; 28 } 29 return 0; 30}
0: 335654 333673 1: 332437 333180 2: 331909 333147 3: 0 0
まあじゃんけんゲームには影響ないですよね。それはそう。
投稿2020/05/16 13:43
編集2020/05/17 01:39
総合スコア5850
この質問に対する回答としては難解すぎます。また、C++11の環境という情報もありません。
“なぜ剰余を使うのか？"ということなので、意味の説明だと思いますが？
また、Cですから（ライブラリやソースを引っ張ってくれば）mtは使えますがuniform_int_distributionは使えません。
剰余がなぜ使えるかは他の回答者さんが回答済ですからあとはそもそも剰余を使うなと指摘すれば十分ではありませんかね？
というかそもそもですね、質問が「なぜ剰余を使うのか？」だから回答は「間違っているから」。でFAでしょ
「じゃんけんゲーム」という前提を忘れるべきではないでしょう。
じゃんけんゲームになにを求めるか、です。
学術的正確さがなくても、用途に対して十分に有用な結果が得られるのは「間違い」ではないと思います。
線形合同法のrand()の場合、下の桁ほど周期的になるので、なおのことやるべきではないですね。
（MTなどまともな乱数を生成してくれるなら心配ないですが）
間違いではなく偏りを知った上での意図的ということはありますね。cateye さんの検証の通り、この場合誤差は全く問題になりません。(1000 回も繰り返すほど面白い遊びではないと思います)
それに、違う言語の解決法を持ってこられても絵に描いた餅でしょう。質問者が学んでいるのは C++ ではなく C です。
それも恐らくはその言語特性が必要なのではなく、単にプログラムの基本を学んでいるだけだと思います。そこで rand を使うのが誤りだと言うなら、そもそも C 言語を学ぶことが誤りで、C++ を学ぶべきだと言っているに等しいでしょう。
従ってこの回答は、回答の補足として書くなら価値のあるものとは思いますが、回答そのものとしてはどうかと思います。私なら他の回答者の回答のコメントにでも書きます。その回答を高評価して。
なお
https://ja.m.wikipedia.org/wiki/%E6%93%AC%E4%BC%BC%E4%B9%B1%E6%95%B0
> ある擬似乱数列を、真の乱数列とみなして良いかを確実に決定することはできない。
つまり、どの乱数生成器を使うかは、その用途によって決めるものだと思います。
まあ確かに本当に一様乱数が求められていたかまでは頭が回ってませんでした。自分がかつて「じゃんけんゲーム」を作ったときはどうやったら一様になるのか一生懸命探したので、そっちに思考が流れてしまったようです。
yumetodoさん、検証ありがとうございます。・・・あとは乱数の出現率ですかねぇ・・・明日から仕事再開なので・・・時間が有ったらやってみます・・・いつのことやらｗ
横道にそれますが
> rand()の性能が悪いことで有名なMSVC
for (int i = 0; i < 0x7fff; i++){
srand(i);
printf("%d %d\n", i, rand());
}
の結果をみると結構げんなり。これはrand()に期待すべきことではないと言うことかも知れませんが。
えっと、横道の横道ｗ・・・ですが・・・srand()のseedを毎回与えているのは何故でしょう?
srand()で与えたseedと一発目のrand()が強い相関を持っているんですよ。
で、よくあるtime()をsrand()にあたえるようなプログラムだと、短い間隔で起動すると一発目がほとんどバラツキを持たないようなことになって。同じseedなら同じ乱数系列になるのは知っていても、seedに対してこういう傾向があると気付くまでちょっとハマったことがあって。
なるほど、勉強に成りました。有難うございます m(_"_)m
>つまり、どの乱数生成器を使うかは、その用途によって決めるものだと思います。
今回乱数生成器の性能の話はべつにしてなくて、範囲調節の話をしているのですが。乱数生成器が一様な乱数を吐いていることは議論の前提でそれを加工するときに一様性を保てているか、いや保てていない、再抽選なしに一様性は担保できない、という話です。
>あとは乱数の出現率ですかねぇ・・・
私も今大学のレポート課題が積まれてるのでちょっと。
>srand()で与えたseedと一発目のrand()が強い相関を持っているんですよ。
へぇ・・・そういえば何回かrand()の生成結果を捨ててから使えなんていうことを見た気もしてきた。
0
rand()%3;
の場合は、rand()の発生する乱数を3で割ったあまり（つまり、０〜２）を使いたいからでしょう。
例えば、rand()%10とすれば０〜９が得られます。
試しに、通常のrand()関数とmt19937を使ったテストをしてみました。
cpp
1#include <iostream> 2#include <cstdlib> 3#include <random> 4// 5using std::cout; 6using std::endl; 7// 8const int R_MAX = 1000; 9 10int main(void) 11{ 12 int rr[4] = {0}; 13 int mr[4] = {0}; 14 15 for(int i = 0; i < R_MAX; ++i) { 16 rr[rand( ) % 3]++; 17 } 18 // 19 std::mt19937 mt(std::random_device{ }( )); 20 std::uniform_int_distribution<int> dist(0, 2); 21 22 for(int i = 0; i < R_MAX; ++i) { 23 mr[dist(mt)]++; 24 } 25 // 26 for(int i = 0; i < 4; ++i) { 27 cout << i << ": " << rr[i] << " " << mr[i] << endl; 28 } 29 return 0; 30}
結果は。以下のように成りました。（同一数値が連続する等の）発生状況は未検証ですが、1000回の試行での数値の発生件数に付いては、ほとんど差異はないように思います。
text
1usr ~/Project/test % ./a.out 20: 354 319 31: 305 345 42: 341 336 53: 0 0
環境は以下
usr /Project/test % uname -a18.04.2-Ubuntu SMP Thu Apr 23 14:27:18 UTC 2020 x86_64 x86_64 x86_64 GNU/Linux
Linux usr.Mint193 5.3.0-51-generic #44
usr ~/Project/test % c++ --version
clang version 10.0.0 (trunk 375507)
Target: x86_64-unknown-linux-gnu
Thread model: posix
InstalledDir: /usr/local/bin
参考：なぜ乱数ジェネレーターを使用しているときにモジュロバイアスがあると人々が言うのですか？
投稿2020/05/16 13:36
編集2020/05/16 17:43総合スコア6851
rand()%3+1;とすれば１〜３が得られます。
RAND_MAXは最低でも32767ですので、1000回程度の試行では差が見えないのは当たり前だと思います。
あと、回数だけでなく周期性の問題も考えられます。
まぁ、じゃんけんですからねぇ＾＾；・・・同じ手を続けて出してもいいかと・・・
一応10万回↓
RAND_MAX:2147483647
0: 33283 33222
1: 33304 33453
2: 33413 33325
3: 0 0
添え字算出変えてみました・・・＞rr[(rand( ) >> 7) % 3]++;
出現数情報ありがとうございます。ただ、これを提示するならばRAND_MAX値があるとなお良いと思います。
RAND_MAX 追記しました。
0
直接の回答ではないですが、rand() % N方式の問題が見えるようにしてみました。
下記のコードをWindows上でcl(Visual Studioのコンパイラ)、clang、gcc(MinGW版を使うこと)のいずれかでコンパイルしてみてください。(Windows標準のC標準ライブラリが使われるようにすると言うこと)
C
1#include <stdio.h> 2#include <stdlib.h> 3 4#define TRIAL_NUMS 100000000 5#define N 100 6 7int main(void) 8{ 9 srand(0); 10 long long count[N] = { 0 }; 11 for (long long i = 0; i < TRIAL_NUMS; i++) { 12 count[rand() % N]++; 13 } 14 printf("RAND_MAX: %d\n", RAND_MAX); 15 for (int i = 0; i < N; i++) { 16 printf("%d: %lld\n", i, count[i]); 17 } 18 return 0; 19}
シードが固定なので、どのWindowsであっても次のようになるはずです。(もしかしたら、Windowsのバージョンによって異なる可能性はあります。下記はWindows 10 1909での結果です。)
RAND_MAX: 32767 0: 1000317 1: 1000941 2: 1001425 3: 1000824 4: 1000320 5: 1002156 6: 1000743 7: 1000490 8: 1002694 9: 1000754 10: 1000407 11: 999649 12: 1000486 13: 999705 14: 1001300 15: 1000246 16: 1001420 17: 1000176 18: 1000844 19: 999160 20: 1000688 21: 1001457 22: 1001543 23: 1000631 24: 999740 25: 1000769 26: 1001653 27: 1000206 28: 1000585 29: 1000811 30: 1000454 31: 1003263 32: 1001180 33: 1002142 34: 1002162 35: 1000753 36: 1000572 37: 1001244 38: 1000235 39: 1001291 40: 1001121 41: 1001745 42: 1001757 43: 1002708 44: 1000194 45: 1001196 46: 1001448 47: 1000214 48: 1002378 49: 1001071 50: 999699 51: 1000265 52: 1001959 53: 999487 54: 999405 55: 1003237 56: 1001845 57: 999192 58: 1000057 59: 999976 60: 1000253 61: 1001000 62: 999549 63: 999874 64: 1002895 65: 1000536 66: 999611 67: 1001572 68: 998691 69: 998146 70: 998725 71: 999580 72: 997056 73: 997362 74: 998375 75: 999660 76: 998156 77: 1000324 78: 997447 79: 997027 80: 998391 81: 996694 82: 999624 83: 997891 84: 996303 85: 998304 86: 997201 87: 997868 88: 996585 89: 998111 90: 998279 91: 997415 92: 997874 93: 999119 94: 997966 95: 997747 96: 998160 97: 997556 98: 1000191 99: 998492
67を境に1000000を越えている数と越えてない数の頻度にかなりの差が見られるかと思います。
Nが3程度ではそれほど違いは見えないでしょう(乱数の周期を越えるぐらいの試行回数を重ねないと、ランダム性から出る誤差の方が大きすぎて、有意義な結果が見えない)。ですが、「0から99までの数を乱数で取得(1D100をふるイメージ)し、50未満なら成功」みたいなゲームのプログラムを組んだとき、成功確率はわずかに50%を越えます(低い数値のほうが出やすいので、SANチェックもきっと乗り越えられるぜ！)。乱数の取り方とその利用方法によっては僅かな差がちょっとの差としてあられる可能性があると言うことです。といっても、その差は変わらずちょっとなのでゲーム程度では些細な問題です。しかし、数学的な厳密さが必要とされる統計やシミュレーション等では問題になる可能性があります。(そもそも、rand()の実装は環境依存であり、良い乱数ではないことが多いので、厳密さが求められるものに使用するのは避けるべきではありますが。)
【おまけ】
rand() % Nはそれぞれが現れる確率が等しいとは言えないという話でした。では、どうすれば良いのかというと、はみ出てしまっている部分を切ればいいと言うことです。たとえば、RAND_MAXが32767の場合、0から順番に0,1,2と入れておくと、最後の方は、32766が0、32767が1となって、2にいれるものが一つだけ足りません。なので、乱数が32766や32767の場合は結果を切り捨てて、乱数取得からやり直しすれば、いいとなります。
では、早速、GCCのlibstc++を参考にしながら、100の場合のコードを書き換えて見ましょう。
C
1#include <stdio.h> 2#include <stdlib.h> 3 4#define TRIAL_NUMS 100000000 5#define N 100 6#define N_SCALING (RAND_MAX / N) 7#define N_PAST (N * N_SCALING) 8 9int main(void) 10{ 11 srand(0); 12 long long count[N] = {0}; 13 for (long long i = 0; i < TRIAL_NUMS; i++) { 14 int r; 15 do { 16 r = rand(); 17 } while (r >= N_PAST); 18 count[r / N_SCALING]++; 19 } 20 printf("RAND_MAX: %d\n", RAND_MAX); 21 for (int i = 0; i < N; i++) { 22 printf("%d: %lld\n", i, count[i]); 23 } 24 return 0; 25}
今度は少ない数の方に1000000越えが偏るということは起きなかったと思います。
さて、上のコードを見てみましょう。do ～ while (...);の部分は最初に言った切り捨て部分です。最後の切れ端みたいな乱数になった場合(N_PAST以上になった場合)はやり直ししています。そうして得られた乱数に対して、N_SCALINGを割っています。そう、剰余ではなく商を使っています。
なぜ、剰余ではなく商なのか？r % Nでもいいのでは無いのか？という疑問はありますが、GCCの実装がそうだったので、今回はそうしました。では、なぜ、GCCがそのようにしているのかについては、すいませんが、もっと詳しい人に聞いていただくようお願いします。
投稿2020/05/17 04:30
編集2020/05/17 12:01総合スコア21735
> なぜ、剰余ではなく商なのか？
線形合同法を使った場合、下の桁は周期的に出てしまう…ということはありますが、C++でそこまで品質の悪い乱数を動員することもない気はしますね。
> 線形合同法を使った場合、下の桁は周期的に出てしまう
実は最初そうなんじゃないかなという回答を書いていたのですが、書いていると根拠がだんだんわからなくなってやめました。C++の仕様なのか、GCCが下の桁の周期を回避するためにやっているのかわからないんです。linear_congruential_engineが使われている場合とかを想定しているのかなと想像したりもしたんですが、これと言った資料が見つからなくて…。
0
整数を３で割った余りは３通りだからです。石、ハサミ、紙の３通りに当たるのでしょう。
他にも３通りの値を作り出す方法はありますが、これが一番ラクな方法ではあります。
投稿2020/05/16 13:33
総合スコア4830
個人的に，この質問に対する回答はこれで十分だと思う．
非常にどうでもいい話だけども……
何故かやたらと「均等なる1/3を目指すことこそが正義であり至高！」みたいな雰囲気を感じるけれども，
そういう方向を追い求めることが題材たる「じゃんけんゲーム」の目指す方向なのかどうか，疑問である．
例えば，この「乱数でどうのこうのなプログラム」が「対戦相手としての人間の代替」を目指すものであるならば，確率を完璧なる1/3に近づけることが本当に目指す方向性なのか？
剰余を取ることに関して「問題がある」とか「間違っている」とか言うのは，話の前提を無視して全く他の議論を披露しているだけに見える．
（そのことに有用性が無いとは言わないけれども，ここでやることか？）
> 剰余を用いるのはなぜ
に回答するならば，
【”疑似乱数の周期性がどうの"とか，"剰余だと確率の均等性がどうの"とかいう話はあるかもだが，用途に関して「んなことはどうでもいいから」簡便な方法を用いた（のだと推測します）】
かな．
0
詳しい回答は既についているので、もう少し根本的な話を。
なぜ、剰余を使うのか？というと、
剰余には直線的な数値を循環する数値に変換する特性があるから、です。
x % 3
の場合で考えてみます。
まずは、xを0から順に増やしてゆきます。
0,1,2,3,4,5,6,7,8,9,10,11...
これを、% 3 で剰余を取ると
0,1,2,0,1,2,0,1,2,0,1,2...
と延々と0〜2をひたすら循環する形に変換できます。
xの値がどれだけ大きくとも必ず0〜2の範囲内に収まり、なおかつ循環なので基本的には出現数がほぼ等しくなる。
そういう特性が、出目を等しく分配するのに便利な為、剰余が使われているのです。
(それが完全ではない事はすでに他で書かれているとおりです)
数を3分割すれば良いのですから、例えば0〜8を分割するのに
0〜2、3〜5、6〜8という分け方も可能ですが、この方法は全体の数を把握している必要があり、少々面倒です。
イメージとしては、トランプを最初にプレイヤーに分配する時に、
52枚を参加人数で割って一人当たり何枚だから……なんて方法では配らずに
全員に順番に1枚ずつ配っていくことで、大体等しい枚数を配るのと同じ感じです。
(端数が誤差になるのも同じ)
剰余のこの連続した数値を循環する数値に変換するという特性は便利で、他の場所でも使われています。
x % 8 とすれば、0から順に増えた数値は7まで続き、8になった途端に0に戻ります。
この特性は8進数の一桁を表すのに実に好都合です。
同様に8をnに変えればn進数の計算に使えます。
ここらへんが、乱数の分配に剰余が使われる理由です。
投稿2020/05/17 21:45
編集2020/05/18 10:53
総合スコア1218
0
整数演算で剰余を取れば、0～除数-1 のどれかしか出てこないから、お手軽に範囲内のそこそこバラバラの数が得られるから、です。
しかし、「乱数」として考えると、0～10の乱数があったとして、3の剰余を取れば
0,3,6,9 ->0
1,4,7,10 ->1
2,5,8 ->2
が得られることになり、明らかに偏りがあります。でも、実際にはrand()の範囲は32767とか20億とかだし、目的が「じゃんけんゲーム」なんでしょ...それくらい問題ナシ、ということで剰余でやっちゃえ、ということです。
真面目にやるなら、rand()が返す最大値をRAND_MAXとして0～N-1の整数が欲しいなら
(int)((double)N*rand()/(RAND_MAX+1))
とでもすれば均等になります。
投稿2020/05/16 13:59
総合スコア7639
実のところそれですら一様ではありません。私の回答に貼ったリンクの記事でまさに解説されている話ですが。
同じ個数の数を同じ個数の組に分けるのですから、どう分けようが剰余と同様に最大1個差の偏りが出ますね。
0
だって rand() はすっごく大きい値返すかもしんないもん。
0,1,2のどれかが返ってくるまで rand() 呼び続けるつもり?
んなことするより 3で割った余りをとればいいじゃない。
投稿2020/05/16 13:36
総合スコア16614
0
皆さんたくさんコメントありがとうございました。
全て目を通させて頂きました。
ですが個人的に専門的と感じる意見が多く、私にはちょっと難しかったです...。
また、規約について細かく注意するのがお好きな方もいらっしゃったので、登録しはじめたばかりですが、teratailが嫌になってしまいました。
回答してくださった方々、お時間いただきありがとうございました。
投稿2020/05/18 10:07
退会済みユーザー
総合スコア0
いくらなんでも自分勝手が過ぎるでしょう...
なぜ被害者面？
0
rand関数はどういう値を返し、あなたはどういう値を欲してるのか、を考えよう。
欲しい値以外の値が帰ってきた場合になにをどうするか。ですね
投稿2020/05/16 13:33
総合スコア87774
あなたの回答
tips
プレビュー
