8bit用Xorshiftの周期を検証してみた
軽くて乱数の質も良いということで有名な疑似乱数生成アルゴリズムの「Xorshift」
インターネットで色々調べていると、下記のように、1ワードを8bitにして作ってみるという試みをしたものが見つかりました。
このページを読み進めていくと、
次は周期が2^32 - 1と思って探したのですが、見つかりませんでした。 そのかわり、約半分の2^31 - 1のものが見つかりました。
との記述があり、「そんなことある??」と思ったのでちょっと検証をしてみました。 ただ数学的な検証できるほど頭が良くないので、C言語で本処理を実装し、パラメータを変えて周期がどうなるかを調べました。
結果は、周期が2**32-1のものは存在し、その組み合わせは、
- (a, b, c) = (1, 1, 3)
- (a, b, c) = (3, 3, 2)
- (a, b, c) = (3, 5, 2)
- (a, b, c) = (6, 3, 1)
- (a, b, c) = (7, 1, 2)
- (a, b, c) = (7, 6, 1)
でした。(※アルゴリズム、変数の対応は引用元と同じです)
引用元とは違う結果になりましたが、「ないことはないだろう」と少し思ってたので、組み合わせを見つけられて良かったかなと思います。(ただ、もう少し検証は必要かもしれません)
※引用元でも述べられていますが、乱数の質がどうかまでの評価は行っておりません。
※Xorshiftの理論については下記サイトも参考になると思いますので併せて掲載します