7

私はglibcソースコードで C標準ライブラリrand()関数の実装を読んでいます。stdlib/random_r.c、359 行目

int
__random_r (buf, result)
            struct random_data *buf;
            int32_t *result;
{
  int32_t *state;

  if (buf == NULL || result == NULL)
    goto fail;

  state = buf->state;

  if (buf->rand_type == TYPE_0)
    {
      int32_t val = state[0];
      val = ((state[0] * 1103515245) + 12345) & 0x7fffffff;
      state[0] = val;
      *result = val;
    }
  else
    {
      int32_t *fptr = buf->fptr;
      int32_t *rptr = buf->rptr;
      int32_t *end_ptr = buf->end_ptr;
      int32_t val;

      val = *fptr += *rptr;
      /* Chucking least random bit.  */
      *result = (val >> 1) & 0x7fffffff;
      ++fptr;
      if (fptr >= end_ptr)
        {
          fptr = state;
          ++rptr;
        }
      else
        {
          ++rptr;
          if (rptr >= end_ptr)
            rptr = state;
        }
      buf->fptr = fptr;
      buf->rptr = rptr;
    }
  return 0;

 fail:
  __set_errno (EINVAL);
  return -1;
}

のときに random_r が乱数を生成する方法がわかりません(buf->rand_type != TYPE_0)。誰か説明してください。ありがとう。

4

2 に答える 2

23

glibc rand()には 2 つの異なるジェネレーター実装があります。

  1. 次の式で定義される単純な線形合同ジェネレーター (LCG)。

    val = ((state * 1103515245) + 12345) & 0x7fffffff

    (& 0x7fffffff最も乱数の少ない最上位ビットを破棄します)

    これは非常に単純な単一状態の LCG です。それにはいくつかの欠点があります。rand()最も重要なことは、これは単一の状態ジェネレーターであるため、個別の呼び出しごとに完全な疑似乱数を生成しないことです。実際には、範囲全体 (2^31) を疑似ランダムな順序でトラバースします。これには意味があります。ある数値を取得すると、現在の期間にその数値を再び取得することはありません。次の 2^31rand()呼び出しで、遅かれ早かれ正確にその番号を再度取得します。

    このジェネレーターはTYPE_0、glibcソースでは と呼ばれます。

  2. 少し高度な、加法的フィードバック ジェネレーターです。そのジェネレーターには多くの状態があります。つまり、上記の「トラバース プロパティ」がありません。同一期間内に同じ枚数を2回（またはそれ以上）獲得できます。

    そのアルゴリズムの優れた説明は、ここにあります。

    このジェネレーターは、ソース内でTYPE_1、TYPE_2、TYPE_3またはと呼ばれます。TYPE_4glibc

    あなたの質問に戻ると、それが値を生成する方法です：

    seeding_stage() // (code omitted here, see the description from above link)

for (i=344; i<MAX; i++)
{
    r[i] = r[i-31] + r[i-3];
    val = ((unsigned int) r[i]) >> 1;
}

    質問の の後のコードelseは、単に上記のコードですが、別の方法で記述されています (以前の値を含む配列へのポインターを使用)。

どの発生器が使用されるかは、関数で設定された初期状態のサイズによって異なりinitstate()ます。最初の (LCG) ジェネレーターは、状態サイズが 8 バイトの場合にのみ使用されます。大きい場合は、2 番目のジェネレーターが使用されます。状態のサイズを使用してシードを設定するsrand()と、デフォルトで 128 バイトになるため、2 番目のジェネレーターが使用されます。すべてはglibc、質問で参照されているソース ファイルのコメントに書かれています。

于 2014-09-13T02:26:02.073 に答える