アセンブリ言語の擬似乱数生成器

StackOverflow https://stackoverflow.com/questions/90184

  •  01-07-2019
  •  | 
  •  

質問

コースで割り当てられたアセンブラー プログラム用の擬似乱数生成アルゴリズムが必要ですが、単純なアルゴリズムを希望します。ただし、外部ライブラリは使用できません。

アセンブリ用の優れたシンプルな擬似乱数生成アルゴリズムは何ですか?

役に立ちましたか？

解決

簡単なのは、2 つの大きな相対素数 a と b を選択し、乱数に a を掛けて b を加算し続けることです。モジュロ演算子を使用して、下位ビットを乱数として保持し、次の反復で完全な値を保持します。

このアルゴリズムはとして知られています。 線形合同生成器.

他のヒント

の第 2 巻 コンピュータープログラミングの芸術 には、擬似乱数の生成に関する多くの情報が含まれています。アルゴリズムはアセンブラでデモンストレーションされているため、どれがアセンブラで最も単純であるかを自分の目で確認できます。

ただし、外部ライブラリまたはオブジェクト ファイルにリンクできる場合は、それが最善の策です。次に、たとえば、次のようにリンクできます。 メルセンヌ・ツイスター.

ほとんどの擬似乱数ジェネレーターは次のようなものであることに注意してください。 ない 暗号化に対して安全であるため、安全な乱数生成が必要な場合は、基本的なアルゴリズム以外にも目を向ける必要があります (おそらく、OS 固有の暗号化 API を活用する必要があります)。

テスト用の単純なコード。Crypto では使用しないでください。

コンピュータ ソフトウェアのテストより (138 ページ)

32ビット演算なので演算は必要ありません MOD 2^32

RNG = (69069*RNG + 69069) MOD 2^32

そうですね - 古き良きリニア フィードバック シフト レジスタへの参照を見たことがなかったので、SSE 組み込みベースの C コードを投稿します。コンプリート用です。SSE スキルをもう一度磨くために、数か月前にこれを書きました。

#include <emmintrin.h>

static __m128i LFSR;

void InitRandom (int Seed)
{
  LFSR = _mm_cvtsi32_si128 (Seed);
}

int GetRandom (int NumBits)
{
  __m128i seed = LFSR;
  __m128i one  = _mm_cvtsi32_si128(1);
  __m128i mask; 
  int i;

  for (i=0; i<NumBits; i++)
  {

    // generate xor of adjecting bits
    __m128i temp = _mm_xor_si128(seed, _mm_srli_epi64(seed,1));

    // generate xor of feedback bits 5,6 and 62,61
    __m128i NewBit = _mm_xor_si128( _mm_srli_epi64(temp,5),
                                    _mm_srli_epi64(temp,61));

    // Mask out single bit: 
    NewBit = _mm_and_si128 (NewBit, one);

    // Shift & insert new result bit:
    seed = _mm_or_si128 (NewBit, _mm_add_epi64 (seed,seed));
  }

  // Write back seed...
  LFSR = seed;

  // generate mask of NumBit ones.
  mask = _mm_srli_epi64 (_mm_cmpeq_epi8(seed, seed), 64-NumBits);

  // return random number:
  return _mm_cvtsi128_si32 (_mm_and_si128(seed,mask));
}

このコードをアセンブラに変換するのは簡単です。組み込み関数を実際の SSE 命令に置き換えて、その周りにループを追加するだけです。

ところで、このコードが生成するシーケンスは、4.61169E+18 の数字の後に繰り返されます。これは、プライム メソッドと 32 ビット演算で得られる値よりもはるかに多くの値です。展開した場合も高速になります。

@jjrv
あなたが説明しているのは、実際には線形一致ジェネレーターです。最もランダムなビットが最上位ビットです。0..N-1 から数値を取得するには、完全な値を N で乗算し (32 ビット x 32 ビットで 64 ビット)、上位 32 ビットを使用します。

単に任意の数字を使用するべきではありません ある (ある完全な値から次の完全な値に進むための乗数)、Knuth (表 1 セクション 3.3.4 TAOCP vol 2 1981) で推奨されている数値は、1812433253、1566083941、69069、および 1664525 です。

任意の奇数を選択できます b. 。（追加）。

なぜ外部ライブラリを使用しないのでしょうか？その車輪は数百回も発明されてきたのに、なぜまた同じことをするのでしょうか?

RNG を自分で実装する必要がある場合、オンデマンドで数値を生成する必要がありますか?rand() 関数を実装していますか -- それとも乱数のストリームを生成する必要がありますか -- 例:記憶力テスト用？

暗号強度に優れた RNG が必要ですか?繰り返されるまでどれくらい時間がかかりますか?すべてのビットの均一な分散を絶対的に確実に保証する必要がありますか?

これは私が数年前に使用した簡単なハックです。私は組み込みで作業していて、電源投入時に RAM をテストする必要があり、非常に小さく高速なコードと非常に小さな状態が必要だったので、これを実行しました。

  • シードの任意の 4 バイト定数から始めます。
  • これらの 4 バイトの 32 ビット CRC を計算します。これで次の 4 バイトが得られます
  • これらの 4 バイトを、あたかも追加されたかのように CRC32 アルゴリズムにフィードバックします。これら 8 バイトの CRC32 が次の値です。
  • 好きなだけ繰り返してください。

これに必要なコードは非常に少なく (ただし、crc32 関数用のテーブルが必要)、状態もほとんどありませんが、擬似ランダム出力ストリームが繰り返されるまでのサイクル タイムが非常に長くなります。また、プロセッサに SSE は必要ありません。CRC32 関数が手元にあると仮定すると、実装するのは簡単です。

コンパイラにmasm615を使用:

delay_function macro
    mov cx,0ffffh
.repeat
    push cx
    mov cx,0f00h
    .repeat
        dec  cx
        .until cx==0
    pop cx
    dec cx
    .until cx==0
endm

random_num macro
   mov  cx,64    ;assum we want to get 64 random numbers
   mov  si,0

get_num:    
   push cx
   delay_function    ;since cpu clock is fast,so we use delay_function
   mov  ah,2ch  
   int  21h
   mov  ax,dx     ;get clock 1/100 sec
   div  num       ;assume we want to get a number from 0~num-1
   mov  arry[si],ah   ;save to array you set
   inc  si
   pop  cx
   loop get_num   ;here we finish the get_random number

また、別々のビット間の合計要素の XOR を使用してシフト レジスタをエミュレートすることもできるでしょう。これにより、擬似ランダムな数値シーケンスが得られます。

線形合同 (X = AX+C mod M) PRNG は、学生が 2^31 上の中間 AX 結果のキャリー ビットと法を計算する必要があるため、アセンブラ コースに割り当てるのに適しています。あなたが学生であれば、これらはアセンブラで実装するのが非常に簡単であり、講師が念頭に置いていたものである可能性があります。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top