こんな条件を満たす乱数生成関数教えてください

質問

１．任意の周期を指定できる
２．種を指定できる(直前の生成値を引数にとる)
３．逆関数が定義できる
４．生成された乱数 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; }

よろしくご教授お願いします。

回答No.5

Tacosan · ベストアンサー

私も符号理論については全くの不案内なので具体的に「こうすればできる」と述べることができません. なので「理屈からいえばこうなるような気がする」レベルであることはご了解ください.

「3ビット誤り訂正可能な符号」において, 各符号語は 7 (= 2×3+1) ビット以上異なっていなければなりません. これは, 「各符号語からたかだか 3ビットだけ異なる語」を各符号語が共有しないことからわかります.

そして, 「3ビット誤り訂正可能な 31ビット符号」に対してパリティビットを付加すると「どの符号語も 8ビット以上異なっているような 32ビット符号」が生成できます. 問題になるのは「7ビット異なる符号語」の関係だけですが, そのような符号語はパリティが異なります (7ビット異なるから). したがって, パリティビットを付加すれば「異なるビット」の数をさらに 1 だけ増やすことが可能です.

ということなんですけど, ちょっと調べるとそもそも「3ビット誤り訂正可能な 31ビット符号」における符号語の数もそんなに多くないなぁ. 多くてもざっと 40万個くらい?

一応, 必要な周期 (p) がわかれば「どれだけの冗長ビットを増やせばいいか」も分かるはずですが, 最初にも書いたようにこの世界は不案内なもので....

お礼

回答ありがとうございます。

何度も読み返して、ようやく仕組みが理解できました。

正しい符号語２つを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度も回答していただき、本当にありがとうございました。
おかげさまで、ずいぶん理解が深まりました。

回答No.4

Tacosan

「可能な全ての値を作りたい」というのでなければ, 誤り訂正符号を流用するという裏技もありえますね.
「符号長 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

回答No.3

Tacosan

たぶん, たいていの場合に「定数時間で距離を求める」というのは不可能だと思います. 線形合同法の中でもあほな「乗算合同法」
y = ax mod p
を考えても「距離を求める」のは「離散対数問題」という問題であり, 一般には非常に難しい問題です.

もちろん「p はたかだか 128ビット」とかいう前提を付けていいなら必ず定数時間になるんだけど, おそらく「だからどうした」ということにしかならないと思う. 例えば「必ず 1日以内で求まる」というのは計算量理論的には「定数時間」なんだけど, あんまりうれしくないでしょ?

お礼

回答ありがとうございます。

合同法だと距離を求めるのが難しそうに感じていたのですが、離散対数問題という難問だったんですね。
そうなると、合同法ベースの関数は難しいですね。

求めている乱数について、あいまいなことしか書いていなかったので、補足させていただきます。
関数が生成するp個のユニークな数についての条件なのですが、「数ビットの反転で互いに一致しないこと」が条件です。
（例　{0000, 1100, 1010, 1001, 0110, 0101, 0011, 1111} は1ビットの反転では互いに一致しない）

「数ビット」については具体的に決めてませんが、例えば32bitの数に対して8bitくらいです。
（このため、周期pは 2^32 >> p の範囲で十分大きければいいです。）
逆にいえば、生成された数列が人間から見て規則的でも、これを満たすならOKです。
むしろ、規則的であることを利用して、距離を定数時間で求めたいと思っています。

何となく、この条件であれば、場合の数を用いて数を列挙する関数が作れそうな気がするのですが・・・
（よく考えたら、これも最初から書いておくべきでした。すみません。）

回答No.2

kmee

修正された条件だと

重複の無い乱数を周期個並べた「乱数表」を用意する

というのが確実な気がします。

周期が任意でなければ、合同法で対応できそうですが(未検証)

お礼

回答ありがとうございます。

＞重複の無い乱数を周期個並べた「乱数表」を用意する
これも検討したのですが、長周期の場合に大規模な乱数表が必要になってしまうのであきらめました。
小規模な乱数表を組み合わせた関数で、条件をみたせればいいのですが・・・

＞周期が任意でなければ、合同法で対応できそうですが(未検証)
合同法のとき、生成された数の距離を、定数時間で求めるにはどうしたらいいのでしょうか？

回答No.1

chie65536（@chie65535）

乱数である限り「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)」でない関数、ということになりますね。

よろしくお願いします。