6

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

アセンブリ用の優れた単純な疑似乱数ジェネレータアルゴリズムとは何ですか？

4

9 に答える 9

8

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

このアルゴリズムは、線形合同ジェネレーターとして知られています。

于 2008-09-18T05:12:15.543 に答える
3

The Art of Computer Programming のVolume 2 には、疑似乱数の生成に関する多くの情報があります。アルゴリズムはアセンブラーで示されているため、アセンブラーで最も単純なものを自分で確認できます。

ただし、外部ライブラリまたはオブジェクト ファイルにリンクできる場合は、それが最善の策です。次に、たとえばMersenne Twisterにリンクできます。

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

于 2008-09-18T05:23:20.570 に答える
3

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

コンピューターソフトウェアのテスト、138ページから

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

RNG = (69069*RNG + 69069) MOD 2^32
于 2008-09-18T13:32:49.177 に答える
2

そうですね - 古き良きリニア フィードバック シフト レジスタへの参照を見ていないので、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 ビット演算で得られるよりもはるかに多くなります。展開した場合も同様に高速です。

于 2008-09-19T18:47:50.463 に答える
1

@jjrv
あなたが説明しているのは、実際には線形合同ジェネレータです。最もランダムなビットは最上位ビットです。0..N-1から数値を取得するには、完全な値にNを掛け（32ビット×32ビットで64ビットになります）、上位32ビットを使用します。

a （ある完全な値から次の値に進むための乗数）に 任意の数値を使用するのではなく、Knuth（表1セクション3.3.4 TAOCP vol 2 1981）で推奨される数値は1812433253、1566083941、69069、および1664525です。

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

于 2008-09-18T20:21:31.800 に答える
1

外部ライブラリを使ってみませんか？その車輪は数百回発明されました、それでなぜそれを再びするのですか？

RNGを自分で実装する必要がある場合、オンデマンドで数値を生成する必要がありますか（つまり、rand（）関数を実装していますか）、または乱数のストリームを生成する必要がありますか（メモリテストなど）？

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

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

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

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

于 2008-11-25T21:25:47.493 に答える
1

コンパイラに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
于 2011-11-17T06:53:54.583 に答える
0

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

于 2008-09-18T05:22:40.760 に答える
0

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

于 2008-09-18T16:51:10.667 に答える