Sim's blog

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

広告

※このエリアは、60日間投稿が無い場合に表示されます。記事を投稿すると、表示されなくなります。

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)
コメント (7)   この記事についてブログを書く
この記事をはてなブックマークに追加
« 10月28日(月)のつぶやき | トップ | 10月29日(火)のつぶやき »
最新の画像もっと見る

7 コメント

コメント日が  古い順  |   新しい順
Unknown (marsee)
2013-10-30 13:33:37
私もなひたふさんのXORShiftのVHDLを試してみました。
http://marsee101.blog19.fc2.com/blog-entry-2448.html
http://marsee101.blog19.fc2.com/blog-entry-2449.html
http://marsee101.blog19.fc2.com/blog-entry-2450.html
re:Unknown (Sim)
2013-11-02 04:18:42
こんにちは、marseeさん

試されたことがあったんですね。
検定は悩ましいところです。
周期は本来ならBerlekamp-Masseyアルゴリズムを使うべきなんでしょうが、手を抜いて元の値になるまでぐるぐる回しています。
こんなに簡単な方法で乱数生成できるのは驚きました。
Unknown (オークボ電子機巧)
2013-11-07 11:36:15
はじめまして。MFT2013の記事を経由して参りました。MFT2012 の頃に自分の作品に xorshit8 を実装してみたのですが,そのときは下記の記事を参考にしていました。改めて日本語で Sim様の記事を拝見して,この実装でよかったのだと安心できました。ありがとうございます。

Xorshift pseudorandom number generator | Arklyffe.com
http://www.arklyffe.com/main/2010/08/29/xorshift-pseudorandom-number-generator/
re:Unknown (Sim)
2013-11-08 01:44:04
こんにちは、オークボ電子機巧さん

mft2013で赤外線でつながる協調ユニットを展示されていた方ですよね。ていねいな説明ありがとうございました。

8bit xorshiftのパラメータ探索されてる方がおられたんですね。記事をありがとうございます。
Unknown (オークボ電子機巧)
2013-11-08 10:39:56
Simさん,こちらこそブースにお越し頂きありがとうございました。

余談:乱数の件。クリスマスの電飾パタンに利用しようとしたのですが,ランダムなのは意外と面白くないものですね。かといってパタンに嵌めると飽きてきます。この辺の按配が難しいところです。
質問です (SL)
2016-10-05 14:53:11
はじめまして。
xorshiftの A B C はそのような方法で決めないとならないのでしょうか?
今、64Bitのxorshiftが欲しいと思って検索しているのですが、
ビットシフトの部分にどの数値を適用していいのかさっぱり分からなくて困ってます。

これって全部実験して決めるようなたぐいの物なのでしょうか?
質問です (SL)
2016-10-05 14:54:11
はじめまして。
xorshiftの A B C はそのような方法で決めないとならないのでしょうか?
今、64Bitのxorshiftが欲しいと思って検索しているのですが、
ビットシフトの部分にどの数値を適用していいのかさっぱり分からなくて困ってます。

これって全部実験して決めるようなたぐいの物なのでしょうか?

コメントを投稿

その他」カテゴリの最新記事