- ベストアンサー
こんな条件を満たす乱数生成関数教えてください
１．任意の周期を指定できる ２．種を指定できる(直前の生成値を引数にとる) ３．逆関数が定義できる ４．生成された乱数 x、y の距離を（定数時間で）求められる つまり y = f(x) ならxとｙの距離は１、 y = f( f( f(x) ) ) なら距離３、というように 乱数としての質（均等に分布していること）はあまり重視しません。 ビット幅は32～128bitくらい（任意ならベスト）であればいいと思っています。 以下のような感じにしたいです。 int rand(x, p); // 戻り値 y = f(x)、pは周期、xは直前の乱数値 int inv(y, p); // 戻り値 x = f^-1(y) int distance(x, y) // y = f(f(x)) のとき、distance(x, y) = 2 で distance(y, x) = -2 一応以下の関数が条件１～４を満たすのですが、残念ながら乱数としての性質が皆無なので使えないです。 int rand(x, p) { return (x+1) % p; } int inv(y, p) { return y ? y - 1 : p-1; } int distance(x, y) { return y - x; } よろしくご教授お願いします。
- minimax2005
- お礼率97% (227/233)
- C・C++・C#
- 回答数5
- ありがとう数5
- みんなの回答 （5）
- 専門家の回答
質問者が選んだベストアンサー
私も符号理論については全くの不案内なので具体的に「こうすればできる」と述べることができません. なので「理屈からいえばこうなるような気がする」レベルであることはご了解ください. 「3ビット誤り訂正可能な符号」において, 各符号語は 7 (= 2×3+1) ビット以上異なっていなければなりません. これは, 「各符号語からたかだか 3ビットだけ異なる語」を各符号語が共有しないことからわかります. そして, 「3ビット誤り訂正可能な 31ビット符号」に対してパリティビットを付加すると「どの符号語も 8ビット以上異なっているような 32ビット符号」が生成できます. 問題になるのは「7ビット異なる符号語」の関係だけですが, そのような符号語はパリティが異なります (7ビット異なるから). したがって, パリティビットを付加すれば「異なるビット」の数をさらに 1 だけ増やすことが可能です. ということなんですけど, ちょっと調べるとそもそも「3ビット誤り訂正可能な 31ビット符号」における符号語の数もそんなに多くないなぁ. 多くてもざっと 40万個くらい? 一応, 必要な周期 (p) がわかれば「どれだけの冗長ビットを増やせばいいか」も分かるはずですが, 最初にも書いたようにこの世界は不案内なもので....
その他の回答 (4)
- Tacosan
- ベストアンサー率23% (3656/15482)
「可能な全ての値を作りたい」というのでなければ, 誤り訂正符号を流用するという裏技もありえますね. 「符号長 31ビットで 3ビット誤りの訂正可能」な符号を作れば, 「32ビットで全ての符号語が 8ビット以上異なる」ようにできそうです... が, どのくらいできるかは知りません.
お礼
回答ありがとうございます。 勉強不足であまり理解できていないのですが、以下の理解であっていますでしょうか？ 「符号長32ビットで3ビット誤りの訂正可能」な訂正符号は、互いに8ビット以上異なっている。 （nビット訂正できるなら、互いに2^nビット以上異なっている？） よって、引数で与えられたデータから符号生成する関数f(x)を利用すると、 f(1), f(2), f(3), .... f(p) は互いに8ビット以上異なっている。（pは周期） この場合疑問なのですが、引数xのビット幅に関わらず32ビットの訂正符号を生成できるのでしょうか？ もしそうであるなら、まさに求めていた関数かもしれませんね。 ちなみに、プログラムを書いて調べてみました。 20bit,24bit,28bitの数で互いに8bit以上異なる数を求めてみたところ、それぞれ32個、128個、1024個ありました。（ずいぶん少ないようです。） エラトステネスのふるいのように、8bit以下の反転で一致する数をふるい落としていくプログラムを書きました。（28bitで実行に10分かかり、これ以上調べられませんでした。） 一応、20bitのときの32数を載せておきます。 縦にみたとき規則性のあるビット列もあるのですが、そうでないビット列もあってよくわかりませんでした。うーん。 0000 00000000 00000000 0000 00000001 11111111 0000 00111110 00001111 0000 00111111 11110000 0001 11000110 00110011 0001 11000111 11001100 0001 11111000 00111100 0001 11111001 11000011 0110 01001010 01010101 0110 01001011 10101010 0110 01110100 01011010 0110 01110101 10100101 0111 10001100 01100110 0111 10001101 10011001 0111 10110010 01101001 0111 10110011 10010110 1010 10010100 10101010 1010 10010101 01010101 1010 10101010 10100101 1010 10101011 01011010 1011 01010010 10011001 1011 01010011 01100110 1011 01101100 10010110 1011 01101101 01101001 1100 11011110 11111111 1100 11011111 00000000 1100 11100000 11110000 1100 11100001 00001111 1101 00011000 11001100 1101 00011001 00110011 1101 00100110 11000011 1101 00100111 00111100
- Tacosan
- ベストアンサー率23% (3656/15482)
たぶん, たいていの場合に「定数時間で距離を求める」というのは不可能だと思います. 線形合同法の中でもあほな「乗算合同法」 y = ax mod p を考えても「距離を求める」のは「離散対数問題」という問題であり, 一般には非常に難しい問題です. もちろん「p はたかだか 128ビット」とかいう前提を付けていいなら必ず定数時間になるんだけど, おそらく「だからどうした」ということにしかならないと思う. 例えば「必ず 1日以内で求まる」というのは計算量理論的には「定数時間」なんだけど, あんまりうれしくないでしょ?
お礼
回答ありがとうございます。 合同法だと距離を求めるのが難しそうに感じていたのですが、離散対数問題という難問だったんですね。 そうなると、合同法ベースの関数は難しいですね。 求めている乱数について、あいまいなことしか書いていなかったので、補足させていただきます。 関数が生成するp個のユニークな数についての条件なのですが、「数ビットの反転で互いに一致しないこと」が条件です。 （例 {0000, 1100, 1010, 1001, 0110, 0101, 0011, 1111} は1ビットの反転では互いに一致しない） 「数ビット」については具体的に決めてませんが、例えば32bitの数に対して8bitくらいです。 （このため、周期pは 2^32 >> p の範囲で十分大きければいいです。） 逆にいえば、生成された数列が人間から見て規則的でも、これを満たすならOKです。 むしろ、規則的であることを利用して、距離を定数時間で求めたいと思っています。 何となく、この条件であれば、場合の数を用いて数を列挙する関数が作れそうな気がするのですが・・・ （よく考えたら、これも最初から書いておくべきでした。すみません。）
- kmee
- ベストアンサー率55% (1857/3366)
修正された条件だと 重複の無い乱数を周期個並べた「乱数表」を用意する というのが確実な気がします。 周期が任意でなければ、合同法で対応できそうですが(未検証)
お礼
回答ありがとうございます。 ＞重複の無い乱数を周期個並べた「乱数表」を用意する これも検討したのですが、長周期の場合に大規模な乱数表が必要になってしまうのであきらめました。 小規模な乱数表を組み合わせた関数で、条件をみたせればいいのですが・・・ ＞周期が任意でなければ、合同法で対応できそうですが(未検証) 合同法のとき、生成された数の距離を、定数時間で求めるにはどうしたらいいのでしょうか？
- chie65535
- ベストアンサー率43% (8522/19371)
乱数である限り「x = f(x)」である瞬間が起きます。 すると ＞３．逆関数が定義できる ＞４．生成された乱数 x、y の距離を（定数時間で）求められる は「論理的に不可能」である事が判ります。 ３と４を成立させる為には「x = f(x)」が起きてはいけません。また ＞１．任意の周期を指定できる であれば「y=f(x)の、xとyの距離を求めようとしたとき、x=yなら、距離は周期pの倍数以外の値になってはいけない」でしょう。 例えば、周期５で「1,4,1,2,5」の繰り返しの場合「1と1の距離」は求められるでしょうか？ 数列は「1,4,1,2,5,1,4,1,2,5,1,4,1,2,5…」になるので「1と1の距離」は２かも知れないし、５かも知れません。 つまり、周期性があると、３と４が破綻します。 なので「理論的に、条件１、３、４を同時に満たす乱数関数は存在できない」と言う結論になります。
お礼
非常に的確なご指摘ありがとうございます。 おかげさまで、重大な条件の不備を見つけました。 改めて条件を定義しなおさせていただきます。 １．関数fは任意の周期pを持つ数列を生成する ２．1周期の中には、重複する数字がない ３．逆関数が定義できる ４．生成された数どうしの距離を求められる ５．直前の生成値を引数にとる ６．１周期分の数が、十分に不規則であること ＞＞ 乱数である限り「x = f(x)」である瞬間が起きます。 条件１、２から、「x = f(x)」でない関数、ということになりますね。 よろしくお願いします。
関連するQ&A
- 毎回違う乱数を生成するにはどうしたらいいでしょうか
C言語の初心者です。よろしくお願いいたします！ 乱数に関する質問：毎回違う乱数を生成するにはどうすればいいでしょうか。 学校の講義の中に ＞＞time() は1970 年1 月1 日0 時0 分（標準時）からの経過秒数を返 すため，1 秒以内に何度も実行すると，同じ数字で乱数を初期化す ることになり，結果も同じになってしまう． という記述がありますが、時間を置いてから、実行しても同じ結果となりました。 その一 #include <stdio.h> #include <stdlib.h> #include <math.h> #include <time.h> int main(void) { double x,y; int i,index=0; double a,n; printf("How many trials?..."); scanf("%lf",&n); for (i=0;i<n;i++) { x=rand()/(RAND_MAX+1.0); y=rand()/(RAND_MAX+1.0); if((x*x+y*y)<1) index++;} a=4*index/n; printf("Result is %.2f(%.2f)",a,sin(-a)); return 0; } その二 #include <stdio.h> #include <stdlib.h> #include <time.h> int main(void) { int a; srand((unsigned)time(NULL)); a=(int)(rand()/(RAND_MAX+1.0)*10); printf("%d\n",a); return 0; } お忙しい中、教えていただけたらうれしいです。
- ベストアンサー
- その他([技術者向] コンピューター)
- MATLABの乱数生成関数 rand( ) について
一様乱数を生成する関数rand()について ・Y = rand(n); ・rand('state',sum(100*clock)); Y = rand(n); という２つのやり方があるようなのですが，以下のmatlabの関数の説明 のページをみても２つの違いが理解できません． http://infoshako.sk.tsukuba.ac.jp/ShakoDoc/MATLAB5/jhelp/techdoc/ref/rand.html どういう違いがあるのでしょうか？ また，この関数は[0,1]の一様乱数としていますが，[-a,a]みたいに範囲指定はできないのでしょうか？ 回答よろしくお願いします．
- ベストアンサー
- その他（プログラミング・開発）
- データベースに存在するデータと重複しない乱数を生成する関数、再帰を使用。
データベースに存在するデータと重複しない乱数を生成したいです。 再帰を使用して書いてみたのですが、考え方、書き方は正しいでしょうか？ 手順としては、 1．乱数を生成 2．DBに接続(select ～ from テーブル名 where like 生成した乱数、で戻り値があるか確認) 3．重複していたら自分自身を呼び出し、再度乱数を生成。 function Func_CreateUniqueID(){ $temp_rand=mt_rand(); //乱数を作る。 echo "生成された乱数: $temp_rand<br>"; try{ $pdo=new PDO("mysql:host=localhost;dbname=データベース名","ユーザ名","パスワード"); $res=$pdo->query("select ランダムID from テーブル名 where ランダムID like '$temp_rand'"); while($row=$res->fetch(PDO::FETCH_ASSOC)){ //while実行,IDが重複しているケース Func_CreateUniqueID(); //重複データが存在していたら自分自身を呼び出す。 } unset($pdo); }catch(PDOException $e){ var_dump($e->getMessage()); } return $temp_rand; } こんな感じで書いたのですが、どうでしょうか？ アドバイスをお願いします。
- ベストアンサー
- PHP
- 乱数発生
#include <stdio.h> #include <stdlib.h> #include <time.h> int main(void) {int y, m, l; srand( (unsigned)time( NULL ) ); y=rand() % 2500 + 1600; m=rand() % 12 + 1; l=rand() % 29 + 1; printf("西暦%d年%d月%d日",y,m,l); return(0); }今回は乱数発生でランダムにだされた西暦年月日をつくりましたが、y=rand() % 2500 + 1600; というのがありこれはｙという乱数が2500以下1600以上という意味なのですがなぜかプログラムを実行しても3000いくつとか4000いくつなんてのもでてきます。m=rand() % 12 + 1;はちゃんと12以下1以上でできるのですがなぜですか？本当にわかりません。是非だれか教えてください。
- ベストアンサー
- C・C++・C#
- 乱数について
乱数の分布を見るために以下のようなプログラムを書きました。 #include <stdio.h> #include <stdlib.h> #include <math.h> int main() { int i,imax, S[RAND_MAX], r; double x,y; FILE *output1; output1=fopen("random2.data","w"); imax=100000; for(i=0;i<=imax;i++){ r = rand(); S[r] += 1; } for(i=0;i<=RAND_MAX;i++){ fprintf(output1,"%d %d \n",i,S[i]); } return 0; } するとコンパイルできて実行もできるのですが、なぜか乱数が30000を 超えるくらいのところでおかしな値になりました。 原因がわからないのでどなたか教えてください。
- ベストアンサー
- C・C++・C#
- 関数の戻り値に関数のアドレスを返すできませんか？
戻り値に関数のアドレスを与える方法が良く分かりません． ひとまず，以下のように動くプログラムを作りたいと思っています． f2(1,2)(1); //このように引数の()を二種類に分けたいのですが 無理でしょうか？？ プログラムは下のように作って実験しているのですが良く分かりません・・ どなたか分かる方居たら教えてください． int f1(int x , int y){ return 0; } ????? int ff(int x){ return f; };
- ベストアンサー
- C・C++・C#
- メルセンヌツイスターを使った2次元乱数
Mersenne Twisterを使って2次元の乱数を下記のように 生成しています。 1. 乱数を取得. x座標の値とする。 2. 1)で用いた乱数生成を利用して乱数を取得. y座標の値とする。 こうした作成したx,y座標のデータを見ますと、一様性が あまりないように見えます。 これは、2次元の乱数の扱いが間違っているのでしょうか? あるいは、周期が非常に長い乱数でも、2次元的に一様性を 保つためには、凖乱数を使うのがいいのでしょうか。
- ベストアンサー
- 数学・算数
- メルセンヌツイスターによる乱数の使い方
メルセンヌツイスターによる乱数を生成したいのですが、下記コードにすると、mt_rand関数を呼ぶたびにシードが初期化され他乱数が生成されます。 やりたいことは、main関数で一度シード１０１で初期化した後は、mt_rand関数内では、初期化することなく継続した乱数を生成したいのです。 そのためa_mt_rand関数のようにすると、mtが定義されていないとなるエラーとなります。 namespaceの問題と思うのですが、色々試してみましたが、できませんでした。 どのようにすればできるでしょうか。 vc++11、windows11 使用 参考サイト C++ 乱数ライブラリ std::random の使い方 リンクはうまく貼れませんでした。 #pragma hdrstop #include <iostream> #include <stdio.h> #include <random> using namespace std; void mt_rand(void); int main(int argc, char *argv[]) { int ptr; std::mt19937 mt(101); // メルセンヌツイスターの32ビット版、引数は初期シード std::uniform_int_distribution <> rand100(0, 100); // [0, 99] 範囲の一様乱数 ptr = rand100(mt); printf("ptr=%d\n",ptr); mt_rand(); } void mt_rand(void) { int ptr=0; std::mt19937 mt(101); // メルセンヌツイスターの32ビット版、引数は初期シード std::uniform_int_distribution <> rand100(0, 100); // [0, 99] 範囲の一様乱数 ptr = rand100(mt); printf("%d\n",ptr); } void a_mt_rand(void) { int ptr=0; ptr = rand100(mt); printf("%d\n",ptr); }
- ベストアンサー
- C・C++・C#
- 正規分布の乱数生成
C言語で正規分布の乱数を発生させたいのですがどうすればいいのでしょうか？ 自分なりにネットで検索して調べたのですが void gaussrand() { static double V1, V2, S; static int phase = 0; double X; if(phase == 0) { do { double U1 = (double)rand() / RAND_MAX; double U2 = (double)rand() / RAND_MAX; V1 = 2 * U1 - 1; V2 = 2 * U2 - 1; S = V1 * V1 + V2 * V2; } while(S >= 1 || S == 0); X = V1 * sqrt(-2 * log(S) / S); } else X = V2 * sqrt(-2 * log(S) / S); phase = 1 - phase; } こうありました。 例えば平均50の分散9の正規分布の乱数を1000個発生させて、配列seiki[1000]に代入したいときは、このプログラミングをどのようにすればいいのでしょうか？ もちろん、このソースではなく、他のもので説明していただけても全然構いません。 また、もしよろしければ、正規分布の他に、二項分布など他の分布でのデータの生成方法もお教えいただけたら幸いです。 よろしくお願いいたします。
- 締切済み
- C・C++・C#
- 乱数に関する質問
（使ってる開発環境はBCCDeveloperです） 乱数に関する質問なんですが 構造体の中の変数に乱数を代入しようとすると 代入したい乱数が、その前後にある構造体に入れようよした数が乱数の値になってしまいます それはどうしてなのでしょうか またどうやって解決すればいいでしょうか 文章の説明だけではわかりずらいと思うので ↓にコメント入りでその詳細を書きました #include<stdio.h> #include <stdlib.h> struct hop{ int kougeki; int gard; int hit; }; struct kio{ int atock; int bougyo; int lis; }; int tekiw(); int sare(); void main(){ int i=8; struct kio teki; struct hop player; player.kougeki= 40 player.gard =50 player.hit= 60 int p; srand((unsigned)time( NULL )); if(i=8){ teki.atock=rand()%60; //ここら変の乱数の値が上の構造体変数に代入した どれかの数になっている teki.bougyo= rand()%50; //ここも同じ teki.lis =rand()%40; //ここも同じ }; p=8; tekiw(); }; int tekiw(struct kio teki){ printf("%d",teki.lis); return teki.lis; };
- 締切済み
- C・C++・C#
お礼
回答ありがとうございます。 何度も読み返して、ようやく仕組みが理解できました。 正しい符号語２つをA、Bとしたとき、3bit誤ったA'、B'について、もしA'=B'となってしまうと、正しい符号語がAなのかBなのか判別できない。 よって「3ビット誤り訂正可能な符号」は互いに７bit以上異なる。 さらに「3ビット誤り訂正可能な 31ビット符号」にパリティを1bitつけると、 １．8bit以上異なる31bitの符号語に1bitパリティついた語 ２．7bit異なる31bitの符号語に1bitパリティがついた語 の2種類ができて、1はOK、問題の２も31bitの符号語が異なれば1bitのパリティが異なるのでOK。 こういうことですね。 いやー、実に巧みな論理ですね。 これはすごい。 3度も回答していただき、本当にありがとうございました。 おかげさまで、ずいぶん理解が深まりました。