Development of binary matrix calculation library and calculation of Xorshift RNG parameter
Abstract
バイナリ行列※1は，0 と 1 の 2 値しかとらない行列で，xorshift 疑似乱数生成器の位数計算などに用いられる．しかしながら，高速にバイナリ行列を計算する専用のライブラリを確認できなかったため開発した．char 型の配列を利用した計算と比較して，1/8 のメモリで済み，bit 演算により バイナリ行列乗算を 24~ 600 倍程度高速に計算できると推測される※2．ライブラリとしての利便性を考慮して，演算子のオーバーロードを行うとともに，サンプルプログラムとして xorshift 疑似乱数生成器の位数を計算した．
※1. Wikipedia では，"logical matrix, binary matrix, relation matrix, Boolean matrix, or (0,1) matrix" の名称で紹介されている[8]．bits martix の名称は一般的でないと思われる．
※2. char 型の配列を利用したバイナリ行列演算を実装していないため，直接の比較はしていないが，利用した手法 [3] から，32x32 bits で約 24 倍，64x64 bits で約 60 倍，1024x1024 bits で約 120 倍，4096x4096 bits で約 590 倍，高速に計算できると推測される．
※1. Wikipedia では，"logical matrix, binary matrix, relation matrix, Boolean matrix, or (0,1) matrix" の名称で紹介されている[8]．bits martix の名称は一般的でないと思われる．
※2. char 型の配列を利用したバイナリ行列演算を実装していないため，直接の比較はしていないが，利用した手法 [3] から，32x32 bits で約 24 倍，64x64 bits で約 60 倍，1024x1024 bits で約 120 倍，4096x4096 bits で約 590 倍，高速に計算できると推測される．
