Sim's blog

電子工作はじめてみました

8bit用xorshift乱数発生アルゴリズム

2013-10-29 23:12:24 | その他
先日、twitterでのやりとりを介してxorshift乱数発生アルゴリズムのことを知りました。非常に簡単な処理(xorとshiftだけ)で周期の長い擬似乱数を生成できるアルゴリズムです。詳しくはwikipediaのxorshiftで。
例になっているのは全て1ワードが32bitのものでした。8bitマイコンとかでも使いやすいように1ワードが8bitのバージョンを作れないかと思って試してみました。
乱数検定はしていませんが、周期だけは確認しています。

(1) 周期が255 (= 2^8 - 1)

アルゴリズム
uint8_t x;
x ^= x >> A;
x ^= x << B;
x ^= x >> C;
return x;

シードはxの初期値です。AとBとCは定数で、全探索してみたところ24組が周期255になることが分かりました。

1 : 1 1 2 (A B Cの順)
2 : 1 1 3
3 : 1 7 3
4 : 1 7 6
5 : 1 7 7
6 : 2 1 1
7 : 2 5 5
8 : 3 1 1
9 : 3 1 5
10 : 3 5 4
11 : 3 5 5
12 : 3 5 7
13 : 3 7 1
14 : 4 5 3
15 : 5 1 3
16 : 5 3 6
17 : 5 3 7
18 : 5 5 2
19 : 5 5 3
20 : 6 3 5
21 : 6 7 1
22 : 7 3 5
23 : 7 5 3
24 : 7 7 1

(2) 周期が16777215 (= 2^24 - 1)

アルゴリズム
uint8_t x, y, z, t;
t = x ^ x << a;
x = y;
y = z;
z ^= z >> c ^ t ^ t >> b;
return z;

シードはx, y, zの初期値です。周期が16777215になるのは1通りでした。

1 : 1 5 3 (A B Cの順)

(3) 周期が2147483647 (= 2^31 - 1)

アルゴリズム
t = x ^ x << a;
x = y;
y = z;
z = w;
w ^= w >> c ^ t ^ t >> b;
return w;


次は周期が2^32 - 1と思って探したのですが、見つかりませんでした。そのかわり、約半分の2^31 - 1のものが見つかりました。今までの例は0以外の全ての値を取るので、シードとしてどの値から始めても同じ周期になりますが、今回のはちょうど半分しか回っていないので、初期値によっては周期が2^31-1にならない可能性があるのではないかと思います。その意味でも周期が2^32 - 1のものが見つからなかったのは残念です。
周期が2147483647となるA B Cの組は13通りありました。

1 : 1 1 6
2 : 1 1 7
3 : 1 2 7
4 : 1 4 7
5 : 1 6 7
6 : 3 1 6
7 : 3 2 1
8 : 3 5 1
9 : 4 3 1
10 : 5 1 5
11 : 6 1 3
12 : 6 5 2
13 : 7 2 1

おわりに

乱数検定とかしてないので、どのくらい良い乱数かは分かりませんが、周期だけは長いです。

参考文献

G. Marsaglia, “Xorshift RNGs,”Journal of Statistical Software, 8(14), July 2003.
(http://www.jstatsoft.org/v08/i14/paper)

10月28日(月)のつぶやき

2013-10-29 02:42:59 | Twitter

川崎市長選は、川崎まるごとWiFi化計画の人が当選したみたいだ。


@makube04 疑似乱数生成アルゴリズムとかだとMersenne Twisterが人気ですね。疑似乱数なのでseedをどこから取るかという問題は残りますが。


@makube04 wikipediaを見ると2496バイトもいるみたいですね。乱数のためだけに、これだけのメモリはさすがに使えないです。
rand()で使われているアルゴリズムがかなりいい加減なんでしょうね。


@makube04 xorshiftという疑似乱数生成アルゴリズムだと内部状態が16バイトでいいみたいです。


@makube04 @sinimanari 32bit xor、shift、代入だけとは実にシンプルですね。


@engadgetjp Maker Faire Tokyo 2013のチケットプレゼント応募


ヘェー : 49,800円の3Dプリンタ組み立てキット ~完成品でも59,800円 - PC Watch pc.watch.impress.co.jp/docs/news/2013… @pc_watchさんから

Simさんがリツイート | 1 RT

WIZNetのW5500を載せたシールド。2260円。イーサネットシールドより安い。2段重ねw
ioShield for Arduino
strawberry-linux.com/catalog/items?…

1 件 リツイートされました

2010年頃からあった。300円。
USBインターフェースIC SP5301CY/TR (2個入)
akizukidenshi.com/catalog/g/gI-0…


@makube04 そういえば、朝は寝ぼけていて肝心の話を忘れていました。x = rand( ) ^ rand( ) ^ ... ^ rand( );のように8回くらいxorしてやると、そこそこまともな乱数になってくれます。


@Maneco1227 @makube04 xorの回数は、中心極限定理に関するものなので特に素数でなくてもよく、そこそこの回数でいいみたいです。正規分布を作るときは12回というのが使われるみたいです。