Xorshift を作る

疑似乱数列生成法の1つである Xorshift を作ってみよう。今回は前置きなくいきなりプログラムだ。

xorshift_func.py

import polyphony
from polyphony import module, pure
from polyphony import testbench
from polyphony.io import Port
from polyphony.typing import bit, bit32
from polyphony.timing import clksleep, clkfence, wait_rising, wait_falling

def xorshift(seed:bit32)->bit32:
    y:bit32 = seed

    y = y ^ ( y << 13 )
    y &= 0xFFFFFFFF
    y = y ^ ( y >> 17 )
    y &= 0xFFFFFFFF

    y = y ^ ( y << 5)
    y &= 0xFFFFFFFF
    return y

@testbench
def test():
    y:bit32 = 2463534242
    for i in range(10):
        rv:bit32 = xorshift(y)
        print(rv)
        y = rv

if __name__ == '__main__':
    test()

このソースは 32bit 版だ。64bit 版、128bit版というのもあるらしいのでいずれチャレンジしてみたいと思う。

ソースの中に bit32 というタイプヒントを入れている。これでPolyphony は 32bit の変数と解釈する。

プログラムの３か所に不思議ともいえる &(アンド) がある。bit32 と宣言しているので、そんなことをしなくてもよさそうなものだ。

    y &= 0xFFFFFFFF

この部分は Python でシミュレーションした時に効いてくる。Python ではタイプヒントはあくまでヒントであって、実行時には int である。シフトすればその分、大きな値になる。それを抑制するコードになっている。

Python で実行してみよう。

> python xorshift_func.py
723471715
2497366906
2064144800
2008045182
3532304609
374114282
1350636274
691148861
746858951
2653896249

実行結果が10進表示だが、c の結果と同じであることを確認した。
#class を使った Xorshift

先の Xorshift は関数版だった。Polyphony の現在は関数内に状態を持つことが出来ない(クロージャ的な事は出来ない)。そのため、関数の第一引数に seed を入れている。seed が毎回同じなら毎回同じ値を返す。これでは乱数とは言えない。Python の class をつかって書き直してみよう。

xorshift_class.py

import polyphony
from polyphony import module, pure
from polyphony import testbench
from polyphony.io import Port
from polyphony.typing import bit, bit32
from polyphony.timing import clksleep, clkfence, wait_rising, wait_falling

from xorshift_func import xorshift

@module
class xorshift_module:
    def __init__(self, seed:bit32):
        self.seed = seed
        self.i_start  = Port(bit, 'in', protocol='ready_valid')
        self.o_data  = Port(bit32, 'out', protocol='ready_valid')
        self.append_worker(self.xorshift_worker)

    def xorshift_worker(self):
        seed:bit32 = self.seed
        while polyphony.is_worker_running():
            self.i_start.rd()
            rv:bit32 = xorshift(seed)
            self.o_data.wr(rv)
            seed = rv
            
m=xorshift_module(2463534242)

@testbench
def test(m):
    for i in range(10):
        rv = 0
        m.i_start.wr(1)
        rv:bit32 = m.o_data.rd()
        print(rv)
        y = rv

test(m)

先の関数がライブラリとして使えることがわかる。

#おまけ c 版のソース

xorshift_c.c

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

uint32_t
xorshift(void)
{
    static uint32_t y = 2463534242;

    y = y ^ (y << 13);
    y = y ^ (y >> 17);

    y = y ^ (y << 5);
    return y;
}

int
main(int argc, char **argv)
{
    uint32_t a;
    int i;
    uint32_t n = (argc == 2)?atoi(argv[1]):1;
    for( i = 0 ; i < n ; i++ ) {
        a = xorshift();
        printf("%u\n", a);
    }
    return 0;
}