問題タブ [prng]

RC4 (RC4_PRNG+XOR) と同様に、RC4 の代わりに別の CSPRNG (Cryptographically secure pseudorandom number generator) [Isaac、BlumBlumShub など) を使用し、結果のキーストリームでデータを XOR することは安全ですか?

状態を隠すことなく、前の出力から純粋関数のように計算できる、優れた疑似乱数ジェネレーターが必要です。「良い」とは、次のことを意味します。

1. 2^n任意のパラメーター（またはそれらの大きなサブセット）を使用して反復でジェネレーターを実行する0と、との間のすべてまたはほぼすべての値をカバーするようにジェネレーターをパラメーター化できる必要があります。2^n - 1ここnで、は出力値のビット数です。

2. ビットの結合されたジェネレーター出力は、そのパラメーターのすべての可能な組み合わせに対して反復で実行する場合、n + pすべてまたはほぼすべての値をカバーする必要があり0ます。ここで、はパラメーターのビット数です。2^(n + p) - 12^np

たとえば、LCGは純粋関数のように計算でき、最初の条件を満たすことはできますが、2番目の条件を満たすことはできません。たとえば、32ビットLCGがm = 2^32あり、それは一定であるためp = 64（2つの32ビットパラメーターaとc）n + p = 96、、 2番目の条件を満たすには、出力から3intずつデータをピークする必要があります。残念ながら、出力の奇数と偶数のintのシーケンスが厳密に交互になっているため、条件を満たせません。これを克服するには、隠された状態を導入する必要がありますが、それは機能を純粋ではなく、最初の条件（長い隠された期間）を壊します。

編集：厳密に言えば、ビットによってパラメーター化され、pビットの完全な状態を備えた関数ファミリーが必要です。各関数は、 -bit intを連続的にインクリメントするだけでなく、一意の「ランダムな」方法nでビットのすべての可能なバイナリ文字列を生成します。そのユニークな方法を選択するために必要なパラメータ化。p + n(p + n)

欲しすぎですか？

ある種の方法で、かなり長い乱数のシーケンスを作成して、前後に反転できるようにしたいと思います。「次へ」と「前へ」のボタンがあるマシンのように、それはあなたに乱数を与えるでしょう。

10ビットの解像度（つまり、0〜1023の範囲の正の整数）のようなもので十分であり、10万を超える数値のシーケンスです。シンプルなゲームタイプのアプリ用で、暗号化強度のランダム性などは必要ありませんが、かなりランダムに感じてもらいたいです。ただし、使用できるメモリの量には限りがあるため、ランダムデータのチャンクを生成してそれを処理することはできません。「インタラクティブな時間」で数値を取得する必要があります。次の数値について考えるのに数ミリ秒を簡単に費やすことができますが、それ以上の快適さはありません。最終的には、ある種のマイクロコントローラー、おそらくArduinoで実行されるようになります。

単純な線形合同法（LCG）でそれを行うことができました。前進するのは簡単です。後退するには、最新の数値をキャッシュし、そこからシーケンスを再作成できるように、間隔を置いていくつかのポイントを格納する必要があります。

しかし、おそらく、前進と前進の両方を可能にする疑似ランダムジェネレーターがありますか？2つの線形フィードバックシフトレジスタ（LFSR）を接続して、異なる方向に回転させることは可能であるはずです。

それとも、ある種のハッシュ関数を使用してインデックス番号を文字化けさせるだけでうまくいくでしょうか？最初に試してみます。

他のアイデアはありますか？

反対のことが何度も尋ねられたと思いますが、悪い乱数を生成する方法についての答えが見つかりませんでした。

クラスター分析用の小さなプログラムを作成し、テスト用にランダムなポイントを生成したいと考えています。ランダムな座標で 1000 ポイントを挿入すると、それらはフィールド全体に散らばり、クラスター分析の価値がなくなります。

クラスターを構築する乱数を生成する簡単な方法はありますか?

私はすでに使用していないrandom()が、random()*random()正規分布の数値を生成することを考えていました (スタック オーバーフローのどこかでこれを読んだと思います)。

2 番目のアプローチは、ランダムにいくつかのエリアを選択し、このエリアでポイント生成を再度実行することです。これにより、もちろんこのエリアにクラスターが生成されます。

もっと良いアイデアはありますか？

最近、64 ビットinteger(またはlong) 用の MersenneTwister を実装しました。私の実装が十分な解決策であるかどうかを知ることができるように、PRNGをテストする方法のガイドまたは例はありますか? 私の実装が十分に均一な分布を持っているかどうかを確認する方法に特に興味があります。

具体的には、これが MersenneTwister に結び付けられているほど良いです。

100 件のレコードがあり、日付をモックアウトしてcreated_at曲線に合わせたいとします。それを行うためのライブラリはありますか、またはどの式を使用できますか? これは同じ道に沿っていると思います：

確率分布による乱数の生成

それらが数学でどのように分類されているかについてはよくわかりませんが、次のようなものを見ています。

• 釣鐘曲線
• 対数 (典型的な生物学/進化) 曲線? ...

コードでいくつかの数式を探しているので、これを言うことができます:

• 100 レコード、1.week期間 、間隔 が与えられた場合12.hours
• created_atおおまかに収まるように各レコードに設定しますcurve

本当にありがとう！

アップデート

ruby アルゴリズムに関するこのフォーラムの投稿を見つけて、R/Ruby ブリッジであるrsrubyにたどり着きましたが、それは多すぎるように思えます。

更新 2

gslライブラリを試して、そこにたどり着くために、この小さなスニペットを書きました...

created_at が統計分布に沿っている Rails でテスト データを生成する

仮想 B ツリーを解析し、アイテムに到達すると停止するデータを取得できるときに、可変長エンコーディングで提示されたデータがあるとします (ハフマン エンコーディングと同様)。アイテムの数は不明です (最高の場合、上限のみがわかっています)。一様に分布した数値を生成するアルゴリズムはありますか? 問題は、この場合、コインベースのアルゴリズムが不均一な結果をもたらすことです。たとえば、101 としてエンコードされた数値があり、10010101 としてエンコードされた数値がある場合、後者は前者と比較してほとんど表示されません。

更新: 言い換えると、すべての要素を任意のビット数でアドレス指定できる場合 (および情報理論に従って、1 つが 101 でエンコードされている場合、他の要素は同じプレフィックスでエンコードされます)。したがって、ビットに応じて左または右に移動し、ある時点でデータ項目に到達すると、B-Tree に似ています。この手法で対処される一連の乱数を取得したいのですが、それらの分布は均一である必要があります (左右のランダムな選択がうまくいかない理由の例は、上記の数字 101 と 10010101 です)。

ありがとう

マックス

たとえば、プレーヤーの次のトラックやブラウザの次のページをランダムに選択する場合、時間を「自然現象」として使用できる可能性があると思いました。たとえば、まともなRPNGは、プログラムの要求なしに次の乱数を継続的に取得できます（たとえば、スレッドでは数ミリ秒ごと、またはイベントがより頻繁に発生します）、その時が来ると（ユーザーの決定に基づいて）、選択はこのユーザーの遅延の影響を自然に受けます。

このアプローチは十分に優れており、どのようにテストできますか？手動でテストする場合の問題は、実際の世界では、いくつかのテストプログラムにそれらを供給するのに十分な乱数を保存するのにそれほど長く待つことができないということです。これを人為的に高速化しようとすると、メソッド自体が無効になります。

ありがとう

使用した (疑似) 乱数の品質が原因で問題が発生したシミュレーションやランダム化アルゴリズムを作成したことがありますか?

何が起こっていたのですか？

prng が問題であることをどのように検出/認識しましたか?

PRNG を切り替えるだけで問題は解決しましたか?それとも真のランダム性のソースに切り替える必要がありましたか?

私は、ランダム性のソースの品質について心配する必要があるアプリケーションの種類と、これが問題になったときにどのように気付くかを理解しようとしています。

実際、私はいくつかの織り交ぜる質問があります。（重要な場合はC＃を使用します。）

初め。0からUInt32.MaxまでのUInt32範囲の乱数を生成するprngがあります。できるだけ均一性を保ちたいです。[a、b]、（a、b）の二重範囲（[0,1]、[0,1）、（0,1）、[-2,4]、（-など）を取得するための主なアイデアは何ですか10,10））？

次のことが気になります。4 294 967296prngの結果があります。[0,1] double範囲の数値よりも小さい— 2^53。そこで、2桁から4 294 967 296-ary番号を作成します。これは、[0、4294967295 * 4294967296+4294967295]でランダムで均一です。この最大値は1の2^53より大きいため、1つ取得した場合は破棄し、再計算してmod 2 ^ 53を使用し、たとえば[0,1]で背番号を取得します。ここでは、最大値をdoubleとして表す必要があります（Int64タイプがないと仮定します）—これには欠点がありますか？

ここで、[0,1）を取得したい場合、結果の数は（2 ^ 53）-1であると考えます。最後の結果に1 /（2 ^ 53）を追加すると、（0,1]にランダムなdoubleが生成されます。 。（0,1）を取得するには、（2 ^ 53）-2つの新しい結果を検討し、0ベースの結果に1 /（2 ^ 53）を追加します。それはすべて正しいですか。

しかし、ダブルレンジ全体に近いか等しいダブルレンジを取得するにはどうすればよいですか？上記のようにn-ary数を作成しても、Double.Maxより大きくなる場合があります。いくつかのビットシフト/ビットマスクアプローチが可能でしょうか？

2番。これで、結果が[0,1）のdouble prngがあり、[Double.Min、Double.Max]の範囲を取得することは可能ですか？ダブルナンバーはいくつありますか？フルダブルレンジprngがある場合、UIntレンジを取得するための最良の方法は何ですか？「直接」マップするか、前に[0,1]にスケーリングしますか？

第3。このコードを見つけました（http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/MT2002/CODES/mt19937ar.c）：

なぜaとbが5と6にシフトし、その後a * 67108864.0 + bが均一になるのですか？

ありがとうございました。