11

次の機能を備えた環境でアプリケーションを作成しています

  • 36 ビットの 1 の補数の整数
  • +、-、*、/および剰余に限定された算術
  • ANDまたはのようなビット操作はありませんOR。しかし、1 の補数であるため、減算と否定にXOR相当します。NOT
  • 数値のオーバーフローは致命的であるため、サイレント トランケーションには使用できません
  • はい、条件があります: IF/THEN/ELSEIF/ELSE/IF.

理想的には、35 ビットまたは 36 ビットのランダムな整数が必要ですが、25 ビットでも十分です。

線形合同法ジェネレーターの単純な実装は、十分に大きな数値に基づいている場合にオーバーフローに陥り、小さい数値を使用すると少数のビットしか生成しません。

したがって、制約内の最大ビット数を生成する数値a、c、mのセット、または 2 つ以上の数値を結合するための LCG の賢明な適応のいずれかを探しています。

出発点として、これまでに私が使用しているものは次のとおりです。

*DEFINE NextRandom . min,max resultVar
* . This is a very shitty RNG. The numbers were never checked
* . for suitability for a long-period linear congruential generator.
* . But it yields numbers that look vaguely random.
*CLEAR rq
*CLEAR rr
*SET RandZ = RandZ * 169687 + 347011      . RandZ is a global var.
*DIVIDE RandZ BY 131072 GIVING rq, RandZ  . Division yields a remainder
*DIVIDE RandZ BY 4 GIVING rq
*SET r0 = +[#,[#],1,1]                    . r0 = argument 'min'
*SET r9 = +[#,[#],1,2]                    . r9 = 'max'
*SET rd = r9 - r0 + 1
*DIVIDE rq BY rd GIVING rq, rr
*SET [#,[#],2,1] TO r0 + rr               . return in 'resultVar'
*ENDDEFINE

スクリプト言語は、EXEC 8 と呼ばれる UNISYS 2200 メインフレーム オペレーティング システムの SSG (Symbolic Stream Generator) です。

重要度: この RNG が動作するアプリは、テスト データを生成します。国家機密や核ミサイルコードを暗号化しているわけではありません。つまり、「ミッション クリティカル」ではなく、「あったらいいな」と「ベスト エフォート」について話しているのです。私は改善に満足していますが、究極の解決策を探しているわけではありません.

4

2 に答える 2

6

Stephen K. Park と Keith W. Millerが論文Random Number Generators: Good Ones Are Hard To Findで示しているように、決してオーバーフローしない線形合同乱数ジェネレータを作成することが可能です。

function  Random  :  real; 
                  (*  Integer  Version  2  *) 
const 
  a  =  16807; 
  m  =  2147483647; 
  q  =  127773;  (*  m  div  a  *) 
  r  =  2836;  (*  m  mod  a  *) 
var 
  lo,  hi,  test  :  integer; 
begin 
  hi  :=  seed  div  q; 
  lo  :=  seed  mod  q; 
  test  :=  a  *  lo  -  r  *  hi; 
  if  test  >  0  then 
    seed  :=  test 
  else 
    seed  :=  test  +  m; 
  Random  :=  seed  /  m 
end;

ここでmは 2^31-1 ですが、これを変更して 36 ビットの数値にすることもできます。秘訣は、シードがhiとloの部分に分割され、それらの部分を合計することによって最終的な乱数が生成されることです。

それが気に入らない場合は、私のブログに乱数ジェネレーターがたくさんあります。たぶん、そのうちの1人があなたが望むことをするでしょう。

于 2013-02-14T14:55:03.040 に答える
1

単純なアイデアですが、それが本当に最高かどうかはわかりません。再帰を使用して、12ビットで3つのLCGを使用できます。

x_i（n）= a x_i（n-1）+ p_i（mod 2 ^ {12}）

素数p_iが異なります。aが大きすぎない場合（たとえば12ビット）、これはオーバーフローしません。次に、3つの12ビット乱数を使用して、36ビットのランダム整数を作成できます。

z（n）= x_0（n）+ 2 ^ {12} x_1（n）+ 2 ^ {24} x_2（n）

p_iが素数で比較的大きい場合、3つのランダムジェネレーターは完全に独立している必要があるため、戦略は非常に適切であることに注意してください。

難しいのは、のための良い選択をすることです。

とにかく、それを使う前に、私はそれがいくつかのテストをするほうがよいと思います。

于 2013-02-14T14:22:35.307 に答える