🎲

xorshift で疑似乱数を生成する in Golang

2023/06/25に公開

random

xorshift

tech

xorshift とは

xorshift は擬似乱数を生成するアルゴリズムのひとつです。

その名の通り、排他的論理和(xor)とシフト演算を用いて疑似乱数を生成します。
ビット演算しか使われないため、高速に疑似乱数を生成することができますし、突然アセンブリで疑似乱数を生成したくなったときに実装もしやすいです。

実装と実験

xorshift 実装

実際に xorshift で疑似乱数を生成してみます。
今回は Go を使って 64 ビットの xorshift を実装してみます。

Go ビギナーなので、もっと良い実装方法があるかもしれません。あったらおしえてね

type XorshiftState[T uint32 | uint64] struct {
  a, b, c, d T
}

// Random number generation with xorshift algorithm.
func xorshiftRand[T uint32 | uint64](state *XorshiftState[T]) T {
  x := state.a
  x ^= x << 13
  x ^= x >> 17
  x ^= x << 5
  state.a = x
  return x
}

a, b, c, d は seed として適当な数字を入れます。

実験

本当に速いのか試してみましょう。
疑似乱数をただ大量に生成するのでも良いですが、本当に疑似乱数として使えそうなのかも同時に確認するため、モンテカルロ法を使って円周率を求めてみます。

モンテカルロ法とは、乱数を使って円周率を求める方法です。
一定の範囲にランダムに点を打ち、そのうち円の中に入った点の数を数えてその割合を計算します。
十分な数の点を打てば円周率に近い値が得られます。
ただし、乱数の制度が悪いと偏りが生じてうまくいきません。

計算上、実際にちゃんとした円でなくてもよく、1/4 の円で考えるとより簡単に計算できます。

// Calculates pi with Monte Carlo method.
func calcPiXorshift(n int) float64 {
  state := XorshiftState[uint64]{123456789, 362436069, 521288629, 88675123}
  insideCount := 0
  for i := 0; i < n; i++ {
    // convert uint64 -> float64 (0.0 <= x < 1.0)
    x := float64(xorshiftRand(&state)) / (1 << 64)
    y := float64(xorshiftRand(&state)) / (1 << 64)

    // check if (x, y) is inside the circle
    if x*x+y*y <= 1 {
      insideCount++
    }
  }
  return 4 * float64(insideCount) / float64(n)
}

また、比較用に math/rand を使ったものも用意しましょう。

func calcPiMathRand(n int) float64 {
  insideCount := 0
  for i := 0; i < n; i++ {
    x := float64(rand.Uint64()) / (1 << 64)
    y := float64(rand.Uint64()) / (1 << 64)
    if x*x+y*y <= 1 {
      insideCount++
    }
  }
  return 4 * float64(insideCount) / float64(n)
}

今回は疑似乱数生成の速度を測りたいので rand.Float64 は使わずに同じ条件でやっています。

実際に計算してみましょう。

func main() {
  if len(os.Args) < 2 {
    fmt.Println("usage: go run main.go [mathrand|xorshift]")
    return
  }

  mode := os.Args[1]
  calcPi := calcPiXorshift

  if mode == "mathrand" {
    calcPi = calcPiMathRand
    fmt.Println("use math/rand")
  } else if mode == "xorshift" {
    fmt.Println("use xorshift")
  } else {
    fmt.Println("usage: go run main.go [mathrand|xorshift]")
    return
  }

  start := time.Now()
  pi := calcPi(100000000)
  end := time.Now()
  fmt.Println("Calculated pi:", pi)
  fmt.Println("Diff:", math.Abs(pi-math.Pi))
  fmt.Println("Elapsed:", end.Sub(start))
}

実験結果

$ go run main.go mathrand
use math/rand
Calculated pi: 3.1413518
Diff: 0.00024085358979331062
Elapsed: 3.098946161s

$ go run main.go xorshift
use xorshift
Calculated pi: 3.1414734
Diff: 0.00011925358979292255
Elapsed: 907.902478ms

ということで、xorshift の方が 3 倍くらい速そう。
そして今回の例では、math.Pi により近いのも xorshift の方でした。^[1]

精度はよくわかんないけど、速度に関しては申し分がなさそうです。

まとめ

xorshift 速い。

Q&A コーナー

xorshift の周期は？

xorshift の周期は $2^32 - 1$ 〜 $2^{128} - 1$ らしいです。
たぶんビット数によって変わる（それはそう）

もっとも、seed を全部0にするとか、そういうことをすると破綻します。

seed はどうやってセットするの？

今回の場合、XorshiftState[uint64] の構造体を用意しています。これの a, b, c, d に適当な値を入れれば OK です。
0は避けてください。また推測可能な値は避けたほうが良いでしょう。(つまり今回の実装をそのまま使うのはあまりよくないです)
もし推測可能な値にすると、某ゲームのように容易に乱数調整されまくることになるかもしれません。

メルセンヌ・ツイスタでよくね？

MT だと超クソ長周期があるのですが、その反面生成速度に難ありです。
大量に乱数生成したいな〜って時には多分向かないです。
強いマシンがあればこっち使うと良いかも

セキュアなの？

いいえ。
セキュアな乱数が使いたい場合、Go には crypto/rand というパッケージがあります。

あとそもそも論として並列に動かすとか、そういうことをする場合、考えることが増えると思います。

そんなたくさん疑似乱数計算して何するの？

円周率計算してみたくない？したくない？あ、そう・・・
たくさん疑似乱数生成する他にもよわよわ環境で普通に疑似乱数出したいな〜とかいう場面でも使えます。
例えばレトロゲームとか。

Go の `math/rand` はどうなってるの？

ぶっちゃけよくわかんないです。
でも見た感じ xorshift っぽい作戦ではなさそう？

xorshift 最強じゃん

そうではないです。速度面は強いですが、セキュアでなかったり、長いものと比べると周期が短かったり、という欠点もあります。
脳死で選択するのではなく、ケースに応じて使い分けましょう。

脚注

今回は math.Pi の seed を固定していません。実行するたびに結果が変わりますし、math.Pi に近いほうが逆転もするかもしれません。が、これは xorshift 側の seed を変えた場合もまた然りです。つまりあんまりこれだけで疑似乱数の精度が良いとは言えないです。 ↩︎