5バイトのシードの検索PRNG

Question

古いアイデアですが、それ以来、問題を解決するために合理的に良い方法を見つけることができませんでした。だから私は非常にコンパクトで、私の意見では、PRNGを合理的に実行していますが、大きなビット深度で適切なシード値を作成するアルゴリズムを見つけることはできません。私の現在の解決策は単にブルートフォースであり、実行時間はO（n^3）です。

発電

私の考えはXORタップ（基本的にLFSRs）音の生成のために使用されるいくつかの古い8ビットマシンから来ました。私はX64をベースにしてC64を操作し、オペコードをまとめようとしましたが、その結果を経験しました。

asl 
adC#num1 
eor #num2 

これはうまく選択NUM1とNUM2で6502上の5バイトであり、アキュムレータにそれは、それである、一見ランダムな順序ですべての256個の値を反復処理：最終作業溶液は、このように見えました画面を埋めるために使用するとかなりランダムに見えます（私はこの後、少し256bのデモを書いています）。これには、適切なnum1 & num2のペアが40個あり、まるでまったく違った順序を示しています。 （シーケンスのビット深度であるBITS）

純粋なCで発現場合にうまく一般化することができる概念は、それがこのようになります。

r = (((r >> (BITS-1)) & 1U) + (r << 1) + num1)^num2; 
r = r & ((1U<<BITS)-1U); 

それが一般化されるので、このCコードが長くなります、符号なし整数の完全な深さを使用するとしても、Cはシフトの上位ビットを加算演算に転送するために必要なキャリ論理を持たないであろう。

いくつかのパフォーマンス分析と比較については、質問の後に以下を参照してください。

問題/問題（S）

ジェネレータとコアの問題は、それが与えられたビット深度の全体の可能なシーケンスを反復するであろう適切なNUM1とNUM2を見つけることです。このセクションの最後で、私は自分のコードを添付して、それを無理やりに強制します。それは12ビットまでの妥当な時間で終了し、16ビットすべてを待つかもしれません（その間に5736個の可能なペアがありますが、一晩中フルサーチで取得されます）。そして、20ビットあなたが患者であれば。しかし、O（N^3）...

本当に厄介である（誰が最初の完全な32ビットのシーケンスを見つけるようになるだろう？）が生じる

その他の興味深い質問：両方NUM1については

• num2のみ奇数の値は完全なシーケンスを生成することができます。どうして？これは難しいことではないかもしれませんが（私は推測します）、合理的にそれを証明したことはありません。

• num1（加算値）に沿ってミラーリングプロパティがあります。つまり、 'a'が与えられた 'b' num2で完全なシーケンスが得られた場合、 'a'の2の補数同じnum2の深さ）も完全なシーケンスです。私は計算したすべての世代でこのことが確実に起こることを観察しました。

• 第3の興味深い特性は、すべてのnum1 & num2のペアに対して、結果のシーケンスが適切な円を形成するように見えることです。つまり、少なくとも数字の0は常に円の一部であるようです。このプロパティがなければ、私のブルートフォース検索は無限ループで消滅するでしょう。

• ボーナス：このPRNGはこれまでに知られていましたか？ （と私はちょうどそれを発明した）？

  #define BITS 16 
  
  #include "stdio.h" 
  #include "stdlib.h" 
  
  int main(void) 
  { 
  unsigned int r; 
  unsigned int c; 
  unsigned int num1; 
  unsigned int num2; 
  unsigned int mc=0U; 
  
  num1=1U; /* Only odd add values produce useful results */ 
  do{ 
      num2=1U; /* Only odd eor values produce useful results */ 
      do{ 
      r= 0U; 
      c=~0U; 
      do{ 
      r=(((r>>(BITS-1)) & 1U)+r+r+num1)^num2; 
      r&=(1U<<(BITS-1)) | ((1U<<(BITS-1))-1U); /* 32bit safe */ 
      c++; 
      }while (r); 
      if (c>=mc){ 
      mc=c; 
      printf("Count-1: %08X, Num1(adc): %08X, Num2(eor): %08X\n", c, num1, num2); 
      } 
      num2+=2U; 
      num2&=(1U<<(BITS-1)) | ((1U<<(BITS-1))-1U); 
      }while(num2!=1U); 
      num1+=2U; 
      num1&=((1U<<(BITS-1))-1U); /* Do not check complements */ 
  }while(num1!=1U); 
  
  return 0; 
  } 
  

  これ、各反復の後に出力がペアには、配列の長さが等しい以上であるかどう見つけるだろう、努めて表示する：

そしてここでは、力まかせ探索のコード（C）であります前のよりも。他の深度のシーケンスに対してはBITS定数を変更してください。私は、種子に関連するいくつかのグラフをした

シード狩猟

。ここで、すべての9ビットシーケンスの長さを示すいいイメージである：

白丸

は、全長配列では、X軸はNUM1（追加）するためのものであり、Y軸はNUM2（XOR）するためのものである、明るくドットは、シーケンスが長くなります。他のビット深度はパターンが非常によく似ています。それらはすべて、ミラーリングで繰り返される2つのパターンで16の主要タイルに分割されているようです。タイルの類似性は完全ではありません。たとえば、左上隅から右下にかけての対角線の上をはっきりと見ることができますが、反対側は見えませんが、完全長シーケンスの場合、このプロパティは信頼できると思われます。この頼っ

現在の時点で、以前の仮定によるよりもさらに多くの作業を軽減することが可能ですが、それはまだはO（n^3）の...

パフォーマンス分析

生成可能な最長シーケンスは24ビットです：私のコンピュータでは、このために完全な24ビットシーケンスをブルートフォースするのに約5時間かかります。これはまだDiehardのような実際のPRNGテストではまだそうですが、今のところ私はむしろ独自のアプローチをとっています。

まず、ジェネレータの役割を理解することが重要です。これは決して簡単ではないため、非常に良いジェネレータになることは決してありません。乗算/除算演算を必要としないこの領域では、Galois LFSRは同様の性能を生み出すことができる。だから私の発電機は、これを上回る能力があれば、どんな用途のものでもあります。

私が行ったテストは、すべて16ビットのジェネレータでした。この深さは便利なシーケンスの長さを与えているので、数字はまだ2つの8ビットの部分で分割されている可能性があるため、ビジュアル解析のためにさまざまなビット精度のグラフを表示できます。

テストのコアは、以前に生成された番号と現在生成されている番号に沿って相関を探していました。このため私は前の世代がYだったX：Yのプロットを使用しました。現在のXは上の2つのグラフのように低/高の両方に分割されています。これらのステップをリアルタイムでプロットできるプログラムを作成し、数字がどのように続くか、グラフがどのようにいっぱいになるかをおおまかに調べることも可能にしました。ここでは、ジェネレータが完全な2^16または2^16-1（ガロア）サイクルを実行した結果、明らかに最終結果のみが表示されます。

フィールドの説明：

• は、画像は、全画像サイズ2048x512を作る8×256×256のグラフを（元のサイズでそれらを確認してください）から成ります。

• 実際に完全なシーケンスがプロットされたことを確認するだけで、それは単にX = r % 256; Y = r/256;プロットです。

• 左下のグラフは、上のグラフと同じ方法でプロットされただけで、数値が合理的にランダムに発生していることを確認しています。

• 2番目のグラフから、上の行は上位バイトの相関グラフです。最初の世代は前の世代を使用し、次の世代は前の世代まで2つ前の世代をスキップします。

• 下から2番目の行は、上記と同様に構成された下位バイト相関グラフです。

ガロアジェネレータは、0xB400タップこれはWikipedia Galois exampleで見つかった発電機である

を設定します。パフォーマンスは最悪ではありませんが、それでも間違いはありません。

ガロアジェネレータは、0xA55Aタップはまともなガロア "シード" の

つを設定し、私が見つかりました。 16ビット数の低い部分は上記よりもかなり良いように見えるが、高位バイトをかすめるガロアの「種」を見つけることができなかったことに注意してください。

私の発電機、0x7F25（ADC）、0x00DB（EOR）シード

これは、EOR値の上位バイトがゼロである私の発電機のベストです。高位バイトを制限することは、8ビットマシンでは有用です。なぜなら、ランダム化パフォーマンスの損失が手頃であれば、この計算は省略でき、実行速度が速くなるためです。

私の発電機、0x778B（ADC）、0x4A8B（EOR）シード

これは私の測定によって非常に良質の種の一つです。

は良好な相関を持つ種を見つけるために、私はある程度、ガロアと私のために同じようにそれらを分析しまう小さなプログラムを構築しました。そのプログラムによって「良い品質」の例が特定され、次にそれらのいくつかをテストし、その中から1つを選択しました。

いくつかの結論：

• ガロアジェネレータは私よりも剛性であるように思われます。すべての相関グラフ上では、線で構成されていなくても、明確な幾何学的パターンが観察可能である（ここでは示されていない "チェッカーボード"パターンを生成する種もある）。私のジェネレータもパターンを表示しますが、世代が増えるにつれてパターンの定義が少なくなります。

  高位バイトのビットを含むガロワ生成器の結果の一部は、本質的に私の生成器に存在しないような剛性のようです。これは弱い仮定ですが、多少の研究が必要になるでしょう（ガロア発電機では常にそうであるかどうか、他のビットの組み合わせではそうでないかどうかを確認する必要があります）。

• ガロア生成器にはゼロがありません（最大周期は2^16-1です）。

• 現在のところ、20ビットを超えるマイ・ジェネレータ用のシードの良いセットを生成することは不可能です。

後、私は頑固で発電機をテストしようとしているより深いこのテーマでは得るかもしれないが、今のようにするために十分な大きさの種を生成する能力の欠如は、それを不可能にします。

Answer 1

これは、何らかの形の非線形シフトフィードバックレジスタです。私はそのように使用されているかどうかはわかりませんが、リニアシフトフィードバックレジスタに多少似ています。このWikipediaページをLSFRsの紹介としてお読みください。それらは擬似乱数生成で頻繁に使用されます。

しかし、擬似乱数ジェネレータは、以前に生成された数値の最上位ビットと次に生成される数値の最下位ビットとの間に線形相関があることが本質的に悪いです。最上位ビットBをシフトした後、新しい数の最下位ビットは、加算定数num1の最下位ビットと排他的論理和定数num2の最下位ビット（XORまたはB）になります。これは、2進加算が等価であるためです排他的または最下位ビットに設定します。ほとんどの場合、PRNGには他の同様の欠点があります。良いPRNGを作成するのは難しいです。

しかし、私はC64コードが喜んでコンパクトであることを認めなければなりません！