早くて、高品質な乱数と言われるXorShiftの128bit版をいくつかの言語で実装してみた。
これを実装するにあたってのポイントは以下の通り。
- 論理シフトを用いること。
- unsigned int32(符号なしint)を用いること。(符号を持たないこと)
- それができない言語であっても、値は32bit以上の保持は行わないこと。(それ以上は切り捨てる)
恐らく上記を全て満たせればどの言語で実装を作っても同じ乱数が生成できるはず、
ということで複数言語での再現性のある乱数の生成に試みた。
Github
オンラインコンパイラ
C++
Dlang
C#
VisualBasic
JavaScript
Python
HSP
CommonLisp
Tcl
Clojure
XorShift実装
出力例
>> defaults
["z":521288629, "x":123456789, "y":362436069, "w":88675123]
>> seeds in r
["z":21449032, "x":378445824, "y":2745476186, "w":424195189]
>> rand 0 to UInt32Max
3701687786
458299110
2500872618
3633119408
516391518
>> randInt 0 to 100
68
3
88
94
81
>> randFloat 0 to 1
0.0805981
0.379583
0.276967
0.171588
0.364294
>> shuffle array
[4, 17, 8, 2, 9, 13, 0, 7, 14, 0, 3, 6, 1, 18, 10, 15, 12, 11, 16, 5]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 0]
>> randCount in r
24
C++
TestXS.cpp
#include <iostream>
#include "XorShift.cpp"
using namespace std;
using namespace XorShifts;
int main(){
//XorShift乱数ジェネレータの初期化
// 論文デフォルトシード
auto r_def=XorShift::defaultSeed();
// 固定値シード
auto r_const=XorShift(100);
// 時間シード
auto r=XorShift();
//デフォルトシード値の取得
cout<<">> defaults"<<endl;
cout<<"x:"<<XorShift::defaults.x<<endl;
cout<<"y:"<<XorShift::defaults.y<<endl;
cout<<"z:"<<XorShift::defaults.z<<endl;
cout<<"w:"<<XorShift::defaults.w<<endl;
//適用したシード値の取得
cout<<">> seeds in r"<<endl;
cout<<"x:"<<r.seeds.x<<endl;
cout<<"y:"<<r.seeds.y<<endl;
cout<<"z:"<<r.seeds.z<<endl;
cout<<"w:"<<r.seeds.w<<endl;
//乱数の生データを取得
cout<<">> rand 0 to UInt32Max"<<endl;
for(int i=0;i<5;i++){
cout<<r_def.rand()<<endl;
}
//0-100の乱数(100含む)を整数で取得
cout<<">> randInt 0 to 100"<<endl;
for(int i=0;i<5;i++){
cout<<r_const.randInt(0,100)<<endl;
}
//0-1の乱数を浮遊小数点で取得
cout<<">> randFloat 0 to 1"<<endl;
for(int i=0;i<5;i++){
cout<<r.randFloat()<<endl;
}
//静的配列のシャッフル
//値渡しとなるので元の配列は破壊されない
cout<<">> shuffle array"<<endl;
int a[20],a_copy[20];
for(int i=0;i<20;i++) a[i]=i;
int a_length=sizeof(a)/sizeof(a[0]);
int* a_rand=r.shuffle(a,a_copy,a_length);
for(int i=0;i<a_length;i++) cout<<a_rand[i]<<", ";
cout<<endl;
for(auto val:a) cout<<val<<", ";
cout<<endl;
//vector<T>のシャッフル
cout<<">> shuffle vector<T>"<<endl;
vector<int> b;
for(int i=0;i<20;i++) b.push_back(i);
for(auto val:r.shuffle(b)) cout<<val<<", ";
cout<<endl;
for(auto val:b) cout<<val<<", ";
cout<<endl;
//今の乱数を回した回数
cout<<">> randCount in r"<<endl;
cout<<r.randCount<<endl;
}
XorShift.cpp
#include <stdint.h>
#include <string>
#include <vector>
#include <ctime>
namespace XorShifts{
class XorShift{
private:
struct dictionary{uint32_t x;uint32_t y;uint32_t z;uint32_t w;};
uint32_t x;
uint32_t y;
uint32_t z;
uint32_t w;
uint32_t t;
public:
static const struct dictionary defaults;
uint32_t randCount=0;
struct dictionary seeds;
XorShift(
uint32_t w=time(nullptr),
uint32_t x=NULL,
uint32_t y=NULL,
uint32_t z=NULL
){
x=x!=NULL? x: w<<13;
y=y!=NULL? y: (w>>9)^(x<<6);
z=z!=NULL? z: y>>7;
seeds={x,y,z,w};
this->w=w;this->x=x;this->y=y;this->z=z;
}
uint32_t rand(){
randCount++;
uint32_t t=x^(x<<11);
x=y;
y=z;
z=w;
return w=(w^(w>>19))^(t^(t>>8));
}
int randInt(int min=0,int max=0x7FFFFFFF){
return rand()%(max-min+1)+min;
}
float randFloat(float min=0,float max=1){
return (float)(rand()%0xFFFF)/0xFFFF*(max-min)+min;
}
template<typename T>
T* shuffle(const T* _arr,T* arr,int arrLength){
for(int i=0;i<arrLength;i++) arr[i]=_arr[i];
for(int i=0;i<=arrLength-2;i++){
int r=randInt(i,arrLength-1);
T tmp=arr[i];
arr[i]=arr[r];
arr[r]=tmp;
}
return arr;
}
template<typename T>
std::vector<T> shuffle(std::vector<T> arr){
for(int i=0;i<=arr.size()-2;i++){
int r=randInt(i,arr.size()-1);
T tmp=arr[i];
arr[i]=arr[r];
arr[r]=tmp;
}
return arr;
}
static inline XorShift defaultSeed(){
return XorShift(
XorShift::defaults.w,
XorShift::defaults.x,
XorShift::defaults.y,
XorShift::defaults.z
);
}
};
const struct XorShift::dictionary XorShift::defaults={
123456789,
362436069,
521288629,
88675123
};
}
D言語
TestXS.d
import std.stdio;
import XorShift:XorShift;
void main(){
//XorShift乱数ジェネレータの初期化
// 論文デフォルトシード
auto r_def=new XorShift.defaultSeed();
// 固定値シード
auto r_const=new XorShift(100);
// 時間シード
auto r=new XorShift();
//デフォルトシード値の取得
writeln(">> defaults");
writeln(XorShift.defaults);
//適用したシード値の取得
writeln(">> seeds in r");
writeln(r.seeds);
//乱数の生データを取得
writeln(">> rand 0 to UInt32Max");
for(int i=0;i<5;i++){
writeln(r_def.rand());
}
//0-100の乱数(100含む)を整数で取得
writeln(">> randInt 0 to 100");
for(int i=0;i<5;i++){
writeln(r_const.randInt(0,100));
}
//0-1の乱数を浮遊小数点で取得
writeln(">> randFloat 0 to 1");
for(int i=0;i<5;i++){
writeln(r.randFloat());
}
//配列のシャッフル
//値渡しとなるので元の配列は破壊されない
writeln(">> shuffle array");
auto a=new int[20];
foreach(i;0..a.length-1) a[i]=i;
writeln(r.shuffle(a));
writeln(a);
//今の乱数を回した回数
writeln(">> randCount in r");
writeln(r.randCount);
}
XorShift.d
module XorShift;
import std.datetime;
import std.concurrency;
static public class XorShift{
private:
Generator!uint r;
public:
static immutable uint[string] defaults;
static this(){
defaults=[
"x":123456789,
"y":362436069,
"z":521288629,
"w":88675123
];
}
immutable uint[string] seeds;
uint randCount=0;
this(
uint w=cast(uint)Clock.currStdTime(),
uint x=0x7FFFFFF7,uint y=0x7FFFFFF7,uint z=0x7FFFFFF7
){
if(x==0x7FFFFFF7) x=w<<13;
if(y==0x7FFFFFF7) y=(w>>9)^(x<<6);
if(z==0x7FFFFFF7) z=y>>7;
seeds=["x":x,"y":y,"z":z,"w":w];
r=randGen(w,x,y,z);
}
Generator!uint function(uint,uint,uint,uint) randGen=(w,x,y,z)=>new Generator!uint((){
yield(w);
uint t;
for(;;){
t=x^(x<<11);
x=y;
y=z;
z=w;
yield(w=(w^(w>>19))^(t^(t>>8)));
}
});
uint rand(){
randCount++;
r.popFront();
return r.front;
}
int randInt(int min=0,int max=0x7FFFFFFF){
return rand()%(max-min+1)+min;
}
float randFloat(float min=0,float max=1){
return cast(float)(rand()%0xFFFF)/0xFFFF*(max-min)+min;
}
template shuffle(T){
T[] shuffle(T[] _arr){
auto arr=new T[_arr.length];
arr[]=_arr;
for(int i=0;i<=arr.length-2;i++){
int r=randInt(i,arr.length-1);
T tmp=arr[i];
arr[i]=arr[r];
arr[r]=tmp;
}
return arr;
}
}
static class defaultSeed:XorShift{
public:
this(){
super(
XorShift.defaults["w"],
XorShift.defaults["x"],
XorShift.defaults["y"],
XorShift.defaults["z"]
);
}
}
}
C♯
TestXS.cs
using System;
using System.Collections.Generic;
using System.Linq;
using XorShifts;
class TestXS{
static void Main(){
//XorShift乱数ジェネレータの初期化
// 論文デフォルトシード
var r_def=new XorShift.defaultSeed();
// 固定値シード
var r_const=new XorShift(100);
// 時間シード
var r=new XorShift();
//デフォルトシード値の取得
Console.WriteLine(">> defaults");
Console.WriteLine(String.Join(", ",XorShift.defaults));
//適用したシード値の取得
Console.WriteLine(">> seeds in r");
Console.WriteLine(String.Join(", ",r.seeds));
//乱数の生データを取得
Console.WriteLine(">> rand 0 to UInt32Max");
for(int i=0;i<5;i++){
Console.WriteLine(r_def.rand());
}
//0-100の乱数(100含む)を整数で取得
Console.WriteLine(">> randInt 0 to 100");
for(int i=0;i<5;i++){
Console.WriteLine(r_const.randInt(0,100));
}
//0-1の乱数を浮遊小数点で取得
Console.WriteLine(">> randFloat 0 to 1");
for(int i=0;i<5;i++){
Console.WriteLine(r.randFloat());
}
//静的配列のシャッフル
//値渡しとなるので元の配列は破壊されない
Console.WriteLine(">> shuffle Array");
int[] a=Enumerable.Range(0,20).ToArray();
Console.WriteLine(String.Join(", ",r.shuffle(a)));
Console.WriteLine(String.Join(", ",a));
//List<T>のシャッフル
Console.WriteLine(">> shuffle List<T>");
var b=new List<int>(Enumerable.Range(0,20));
Console.WriteLine(String.Join(", ",r.shuffle(b)));
Console.WriteLine(String.Join(", ",b));
//今の乱数を回した回数
Console.WriteLine(">> randCount in r");
Console.WriteLine(r.randCount);
}
}
XorShift.cs
using System;
using System.Collections.Generic;
namespace XorShifts{
class XorShift{
private IEnumerator<uint> r;
public static readonly Dictionary<string,uint> defaults=new Dictionary<string,uint>(){
{"x",123456789},
{"y",362436069},
{"z",521288629},
{"w",88675123}
};
public readonly Dictionary<string,uint> seeds;
public uint randCount=0;
public XorShift(uint? _w=null,uint? _x=null,uint? _y=null,uint? _z=null){
uint w=_w ?? (uint)Environment.TickCount;
uint x=_x ?? w<<13;
uint y=_y ?? (w>>9)^(x<<6);
uint z=_z ?? y>>7;
seeds=new Dictionary<string,uint>(){
{"x",x},{"y",y},{"z",z},{"w",w}
};
r=randGen(w,x,y,z);
}
public IEnumerator<uint> randGen(uint w,uint x,uint y,uint z){
uint t;
for(;;){
t=x^(x<<11);
x=y;
y=z;
z=w;
yield return w=(w^(w>>19))^(t^(t>>8));
}
}
public uint rand(){
randCount++;
r.MoveNext();
return r.Current;
}
public int randInt(int min=0,int max=0x7FFFFFFF){
return (int)(rand()%(max-min+1))+min;
}
public float randFloat(float min=0,float max=1){
return (float)(rand()%0xFFFF)/0xFFFF*(max-min)+min;
}
public T[] shuffle<T>(T[] _arr){
var arr=(T[])_arr.Clone();
for(int i=0;i<=arr.Length-2;i++){
int r=randInt(i,arr.Length-1);
T tmp=arr[i];
arr[i]=arr[r];
arr[r]=tmp;
}
return arr;
}
public List<T> shuffle<T>(List<T> _arr){
var arr=new List<T>(_arr);
for(int i=0;i<=arr.Count-2;i++){
int r=randInt(i,arr.Count-1);
T tmp=arr[i];
arr[i]=arr[r];
arr[r]=tmp;
}
return arr;
}
public class defaultSeed:XorShift{
public defaultSeed():base(
defaults["w"],
defaults["x"],
defaults["y"],
defaults["z"]
){}
}
}
}
VisualBasic.NET
TestXS.vb
Option Strict On
Imports System.Console
Imports System.Collections.Generic
Imports System.Linq
Imports XorShifts
Module TestXS
Sub Main()
'XorShift乱数ジェネレータの初期化
' 論文デフォルトシード
Dim r_def As New XorShift.defaultSeed()
' 固定値シード
Dim r_const As New XorShift(100)
' 時間シード
Dim r As New XorShift()
'デフォルトシード値の取得
WriteLine(">> defaults")
WriteLine(String.Join(", ",XorShift.defaults))
'適用したシード値の取得
WriteLine(">> seeds in r")
WriteLine(String.Join(", ",r.seeds))
'乱数の生データを取得
WriteLine(">> rand 0 to UInt32Max")
For i=0 To 5-1
WriteLine(r_def.rand())
Next
'0-100の乱数(100含む)を整数で取得
WriteLine(">> randInt 0 to 100")
For i=0 To 5-1
WriteLine(r_const.randInt(0,100))
Next
'0-1の乱数を浮遊小数点で取得
WriteLine(">> randFloat 0 to 1")
For i=0 To 5-1
WriteLine(r.randFloat())
Next
'静的配列のシャッフル
'値渡しとなるので元の配列は破壊されない
WriteLine(">> shuffle Array")
Dim a As Integer()=Enumerable.Range(0,20).ToArray()
WriteLine(String.Join(", ",r.shuffle(a)))
WriteLine(String.Join(", ",a))
'List(Of T)のシャッフル
WriteLine(">> shuffle List(Of T)")
Dim b As New List(Of Integer)(Enumerable.Range(0,20))
WriteLine(String.Join(", ",r.shuffle(b)))
WriteLine(String.Join(", ",b))
'今の乱数を回した回数
WriteLine(">> randCount in r")
WriteLine(r.randCount)
End Sub
End Module
XorShift.vb
Option Strict On
Imports System.Collections.Generic
Imports System.Linq
Namespace XorShifts
Class XorShift
Private r As IEnumerator(Of UInteger)
Public Shared ReadOnly defaults As New Dictionary(Of String,UInteger) From {
{"x",123456789},
{"y",362436069},
{"z",521288629},
{"w",88675123}
}
Public ReadOnly seeds As Dictionary(Of String,UInteger)
Public randCount As UInteger=0
Sub New(
Optional _w As UInteger?=Nothing,
Optional _x As UInteger?=Nothing,
Optional _y As UInteger?=Nothing,
Optional _z As UInteger?=Nothing
)
Dim w=CUInt(If(_w IsNot Nothing,_w,CUInt(Environment.TickCount)))
Dim x=CUInt(If(_x IsNot Nothing,_x,w<<13))
Dim y=CUInt(If(_y IsNot Nothing,_y,w>>9 Xor x<<6))
Dim z=CUInt(If(_z IsNot Nothing,_z,y>>7))
seeds=New Dictionary(Of String,UInteger) From {
{"x",x},{"y",y},{"z",z},{"w",w}
}
r=randGen(w,x,y,z)
End Sub
Public Iterator Function randGen(w As UInteger,x As UInteger,y As UInteger,z As UInteger) As IEnumerator(Of UInteger)
Dim t As UInteger
Do
t=x Xor (x<<11)
x=y
y=z
z=w
w=(w Xor (w>>19)) Xor (t Xor (t>>8))
Yield w
Loop
End Function
Public Function rand() As UInteger
randCount+=1UI
r.MoveNext()
Return r.Current
End Function
Public Function randInt(Optional min As Integer=0,Optional max As Integer=&H7FFFFFFFI) As Integer
Return CInt(rand() mod (CUInt(max)-min+1)+min)
End Function
Public Function randFloat(Optional min As Single=0,Optional max As Single=1) As Single
Return CSng((rand() mod &HFFFFUI)/&HFFFFUI*(max-min)+min)
End Function
Public Function shuffle(Of T)(_arr As T()) As T()
Dim arr=CType(_arr.Clone(),T())
For i=0 To arr.Length-2
Dim r As Integer=randInt(i,arr.Length-1)
Dim tmp As T=arr(i)
arr(i)=arr(r)
arr(r)=tmp
Next
Return arr
End Function
Public Function shuffle(Of T)(_arr As List(Of T)) As List(Of T)
Dim arr As New List(Of T)(_arr)
For i=0 To arr.Count-2
Dim r As Integer=randInt(i,arr.Count-1)
Dim tmp As T=arr(i)
arr(i)=arr(r)
arr(r)=tmp
Next
Return arr
End Function
PubLic Class defaultSeed
Inherits XorShift
Sub New()
MyBase.New(
defaults("w"),
defaults("x"),
defaults("y"),
defaults("z")
)
End Sub
End Class
End Class
End Namespace
JavaScript
TestXS.js
"use strict";
const XorShift=require("./XorShift");
(function(){
//XorShift乱数ジェネレータの初期化
// 論文デフォルトシード
const r_def=new XorShift.defaultSeed();
// 固定値シード
const r_const=new XorShift(100);
// 時間シード
const r=new XorShift();
//デフォルトシード値の取得
console.log(">> defaults");
console.log(XorShift.defaults);
//適用したシード値の取得
console.log(">> seeds in r");
console.log(r.seeds);
//乱数の生データを取得
console.log(">> rand 0 to UInt32Max");
for(let i=0;i<5;i++){
console.log(r_def.rand());
}
//0-100の乱数(100含む)を整数で取得
console.log(">> randInt 0 to 100");
for(let i=0;i<5;i++){
console.log(r_const.randInt(0,100));
}
//0-1の乱数を浮遊小数点で取得
console.log(">> randFloat 0 to 1");
for(let i=0;i<5;i++){
console.log(r.randFloat());
}
//配列のシャッフル
//値渡しとなるので元の配列は破壊されない
console.log(">> shuffle Array");
var a=[...Array(20).keys()];
console.log(r.shuffle(a));
console.log(a);
//今の乱数を回した回数
console.log(">> randCount in r");
console.log(r.randCount);
})();
XorShift.js
"use strict";
module.exports=(()=>{
const r=Symbol();
class XorShift{
constructor(
w=0|Date.now(),
x,y,z
){
if(x===undefined) x=0|w<<13;
if(y===undefined) y=0|(w>>>9)^(x<<6);
if(z===undefined) z=0|y>>>7;
this.seeds={x:x>>>0,y:y>>>0,z:z>>>0,w:w>>>0};
Object.defineProperty(this,"seeds",{writable:false});
this.randCount=0;
this[r]=this.randGen(w,x,y,z);
}
*randGen(w,x,y,z){
var t;
for(;;){
t=x^(x<<11);
x=y;
y=z;
z=w;
yield w=((w^(w>>>19))^(t^(t>>>8)))>>>0;
}
}
rand(){
this.randCount=0|this.randCount+1;
return this[r].next().value;
}
randInt(min=0,max=0x7FFFFFFF){
return 0|this.rand()%(max+1-min)+min;
}
randFloat(min=0,max=1){
return Math.fround(this.rand()%0xFFFF/0xFFFF)*(max-min)+min;
}
shuffle(_arr){
var arr=_arr.concat();
for(let i=0;i<=arr.length-2;i=0|i+1){
let r=this.randInt(i,arr.length-1);
let tmp=arr[i];
arr[i]=arr[r];
arr[r]=tmp;
}
return arr;
}
}
XorShift.defaults={
x:123456789,
y:362436069,
z:521288629,
w:88675123
};
XorShift.defaultSeed=class XorShift_default extends XorShift{
constructor(){
super(
XorShift.defaults["w"],
XorShift.defaults["x"],
XorShift.defaults["y"],
XorShift.defaults["z"]
);
}
}
Object.freeze(XorShift);
return XorShift;
})();
Python
:TestXS.py
from XorShift import XorShift
if __name__=="__main__":
#XorShift乱数ジェネレータの初期化
# 論文デフォルトシード
r_def=XorShift.defaultSeed()
# 固定値シード
r_const=XorShift(100)
# 時間シード
r=XorShift()
#デフォルトシード値の取得
print(">> defaults")
print(XorShift.defaults)
#適用したシード値の取得
print(">> seeds in r")
print(r.seeds)
#乱数の生データを取得
print(">> rand 0 to UInt32Max")
for i in range(5):
print(r_def.rand())
#0-100の乱数(100含む)を整数で取得
print(">> randInt 0 to 100")
for i in range(5):
print(r_const.randInt(0,100))
#0-1の乱数を浮遊小数点で取得
print(">> randFloat 0 to 1")
for i in range(5):
print(r.randFloat())
#listのシャッフル
#値渡しとなるので元の配列は破壊されない
print(">> shuffle list")
a=list(range(0,20))
print(r.shuffle(a))
print(a)
#rangeのシャッフル
print(">> shuffle range")
b=range(0,20)
print(r.shuffle(b))
print(b)
#tuple(タプル)のシャッフル
print(">> shuffle tuple")
c=tuple(range(0,20))
print(r.shuffle(c))
print(c)
#iter(イテレータ)のシャッフル
print(">> shuffle iter")
d=iter(range(0,20))
print([i for i in r.shuffle(d)])
print([i for i in d])
#今の乱数を回した回数
print(">> randCount in r")
print(r.randCount)
:XorShift.py
from time import time
from copy import copy
class XorShift:
defaults={
"x":123456789,
"y":362436069,
"z":521288629,
"w":88675123
}
def __init__(self,
w=int(time()),
x=None,
y=None,
z=None
):
if x is None: x=w<<13
if y is None: y=(w>>9)^(x<<6)
if z is None: z=y>>7
self.seeds={"x":x,"y":y,"z":z,"w":w}
self.randCount=0
self.__r=self.randGen(w,x,y,z)
def randGen(self,w,x,y,z):
while True:
t=x^(x<<11&0xFFFFFFFF)
x,y,z=y,z,w
w=(w^(w>>19))^(t^(t>>8))
yield w
def rand(self):
self.randCount+=1
return next(self.__r)
def randInt(self,min=0,max=0x7FFFFFFF):
return self.rand()%(max+1-min)+min
def randFloat(self,min=0,max=1):
return self.rand()%0xFFFF/0xFFFF*(max-min)+min
def shuffle(self,_arr):
arr=copy(_arr)
if isinstance(arr,list):
isList=True
elif isinstance(arr,range) or isinstance(arr,tuple):
isList=True
arr=list(arr)
else:
isList=False
arr=list(arr)
for i in range(0,len(arr)-1):
r=self.randInt(i,len(arr)-1)
arr[i],arr[r]=arr[r],arr[i]
if not isList:
arr=iter(arr)
return arr
def defaultSeed():return type("defaultSeed",(XorShift,),{
"__init__":lambda self:
XorShift.__init__(
self,
**XorShift.defaults
)
})()
HSP
TestXS.hsp
#runtime "hsp3cl"
#packopt name "XorShift"
#include "XorShift.as"
#cmpopt varinit 1
#module TestXS
#deffunc main
;XorShift乱数ジェネレータの初期化
; 論文デフォルトシード
new@XorShift_defaultSeed r_def
; 固定値シード
new@XorShift r_const,100
; 時間シード
new@XorShift r
;デフォルトシード値の取得
mes ">> xsDefaults"
foreach xsSeedKeys
mes xsSeedKeys(cnt)+":"+xsDefaults(xsSeedKeys(cnt))
loop
;適用したシード値の取得
mes ">> xsSeeds in r"
foreach xsSeedKeys
mes strf("%s:%.0f",xsSeedKeys(cnt),xsSeeds(r,xsSeedKeys(cnt)))
loop
;乱数の生データを取得
mes ">> xsRand 0 to UInt32Max"
repeat 5
mes strf("%.0f",xsRand(r_def))
loop
;0-100の乱数(100含む)を整数で取得
mes ">> xsRandInt 0 to 100"
repeat 5
mes xsRandInt(r_const,0,100)
loop
;0-1の乱数を浮遊小数点で取得
mes ">> xsRandFloat 0 to 1"
repeat 5
mes xsRandFloat(r)
loop
;静的配列のシャッフル
;値渡しとなるので元の配列は破壊されない
mes ">> xsShuffle array"
dim a,20
foreach a: a(cnt)=cnt: loop
xsShuffle r,a,a_rand
out=""
foreach a_rand: out+=str(a_rand(cnt))+", ": loop
mes out
out=""
foreach a: out+=str(a(cnt))+", ": loop
mes out
;今の乱数を回した回数
mes ">> xsRandCount in r"
mes xsRandCount(r)
return
#global
main
XorShift.as
#ifndef XorShift
seedKeys@XorShift="x","y","z","w"
defaults@XorShift=123456789,362436069,521288629,88675123
#module XorShift seeds,randCount,x,y,z,w
#define global xsSeedKeys seedKeys@XorShift
#define global ctype xsDefaults(%1) getDictionary@XorShift(%1,defaults@XorShift)
#modcfunc xsSeeds str key
return getDictionary(key,seeds)
#modcfunc xsRandCount
return randCount
#defcfunc local getDictionary str key,array dict
item="undefined"
foreach seedKeys
if key=seedKeys(cnt):item=dict(cnt):break
loop
return item
#define new(%1,%2=-1,%3=-1,%4=-1,%5=-1) \
dimtype %1,5: \
newmod %1,XorShift,%2,%3,%4,%5
#modinit int _w,int _x,int _y,int _z
if _w!=-1 :w=_w :else :w=gettime(7)+1000*(gettime(6)+60*(gettime(5)+60*(gettime(4)+24*gettime(3))))
if _x!=-1 :x=_x :else :x=w<<13
if _y!=-1 :y=_y :else :y=(w>>9)^(x<<6)
if _z!=-1 :z=_z :else :z=y>>7
seeds=double(strf("%u",x)),double(strf("%u",y)),double(strf("%u",z)),double(strf("%u",w))
randCount=0
return
#modcfunc xsRand
randCount++
t=x^(x<<11)
x=y
y=z
z=w
w=(w^(w>>19&0x1FFF))^(t^(t>>8&0xFFFFFF))
return double(strf("%u",w))
#define global ctype xsRandInt(%1,%2=0,%3=0x7FFFFFFF) randInt@XorShift(%1,%2,%3)
#modcfunc local randInt int min,int max
return int(xsRand(thismod)\(max+1-min)+min)
#define global ctype xsRandFloat(%1,%2=0,%3=1) randFloat@XorShift(%1,%2,%3)
#modcfunc local randFloat double min,double max
return xsRand(thismod)\0xFFFF/0xFFFF*(max-min)+min
#define global xsShuffle(%1,%2,%3) %tshuffle \
%i=length(%2) :\
dimtype %3,vartype(%2(0)),%p :\
foreach %3: %3(cnt)=%2(cnt): loop :\
shuffle@XorShift %1,%o,%3
#modfunc local shuffle var arrLength,array arr
dimtype tmp,vartype(arr(0))
repeat arrLength-1
r=xsRandInt(thismod,cnt,arrLength-1)
tmp=arr(cnt)
arr(cnt)=arr(r)
arr(r)=tmp
loop
return
#global
#module XorShift_defaultSeed seeds,randCount,x,y,z,w
#define new(%1) \
dimtype %1,5: \
newmod %1,XorShift_defaultSeed
#modinit
x=xsDefaults("x")
y=xsDefaults("y")
z=xsDefaults("z")
w=xsDefaults("w")
seeds=x,y,z,w
randCount=0
return
#global
#endif
XorShift.as(コルーチン版)
#ifndef XorShift
seedKeys@XorShift="x","y","z","w"
defaults@XorShift=123456789,362436069,521288629,88675123
#module @randGen@XorShift co,x,y,z,w
#define global randGen@XorShift(%1,%2,%3,%4,%5) \
newmod %1,@randGen@XorShift,%2,%3,%4,%5
#modinit int _w,int _x,int _y,int _z
w=_w:x=_x:y=_y:z=_z
newlab co,1:return
*infLoop
t=x^(x<<11)
x=y
y=z
z=w
w=(w^(w>>19&0x1FFF))^(t^(t>>8&0xFFFFFF))
newlab co,1:return
goto*infLoop
return
#modcfunc next@XorShift
gosub co
return double(strf("%u",w))
#global
#module XorShift seeds,randCount,r
#define global xsSeedKeys seedKeys@XorShift
#define global ctype xsDefaults(%1) getDictionary@XorShift(%1,defaults@XorShift)
#modcfunc xsSeeds str key
return getDictionary(key,seeds)
#modcfunc xsRandCount
return randCount
#defcfunc local getDictionary str key,array dict
item="undefined"
foreach seedKeys
if key=seedKeys(cnt):item=dict(cnt):break
loop
return item
#define new(%1,%2=-1,%3=-1,%4=-1,%5=-1) \
dimtype %1,5: \
newmod %1,XorShift,%2,%3,%4,%5
#modinit int _w,int _x,int _y,int _z
if _w!=-1 :w=_w :else :w=gettime(7)+1000*(gettime(6)+60*(gettime(5)+60*(gettime(4)+24*gettime(3))))
if _x!=-1 :x=_x :else :x=w<<13
if _y!=-1 :y=_y :else :y=(w>>9)^(x<<6)
if _z!=-1 :z=_z :else :z=y>>7
seeds=double(strf("%u",x)),double(strf("%u",y)),double(strf("%u",z)),double(strf("%u",w))
randCount=0
randGen@XorShift r,w,x,y,z
return
#modcfunc xsRand
randCount++
return next@XorShift(r)
#define global ctype xsRandInt(%1,%2=0,%3=0x7FFFFFFF) randInt@XorShift(%1,%2,%3)
#modcfunc local randInt int min,int max
return int(xsRand(thismod)\(max+1-min)+min)
#define global ctype xsRandFloat(%1,%2=0,%3=1) randFloat@XorShift(%1,%2,%3)
#modcfunc local randFloat double min,double max
return xsRand(thismod)\0xFFFF/0xFFFF*(max-min)+min
#define global xsShuffle(%1,%2,%3) %tshuffle \
%i=length(%2) :\
dimtype %3,vartype(%2(0)),%p :\
foreach %3: %3(cnt)=%2(cnt): loop :\
shuffle@XorShift %1,%o,%3
#modfunc local shuffle var arrLength,array arr
dimtype tmp,vartype(arr(0))
repeat arrLength-1
_r=xsRandInt(thismod,cnt,arrLength-1)
tmp=arr(cnt)
arr(cnt)=arr(_r)
arr(_r)=tmp
loop
return
#global
#module XorShift_defaultSeed seeds,randCount,r
#define new(%1) \
dimtype %1,5: \
newmod %1,XorShift_defaultSeed
#modinit
x=xsDefaults("x")
y=xsDefaults("y")
z=xsDefaults("z")
w=xsDefaults("w")
seeds=x,y,z,w
randCount=0
randGen@XorShift r,w,x,y,z
return
#global
#endif
CommonLisp
TestXS.lisp
(load "XorShift")
(require :XorShifts)
(let (
(r_def (make-instance 'xs:XorShift-defaultSeed))
(r_const (make-instance 'xs:XorShift :w 100))
(r (make-instance 'xs:XorShift))
a
)
;デフォルトのシード値を取得
(format t ">> defaults~%")
(format t "~a~%" xs:defaults)
;今の乱数に与えたシード値初期値
(format t ">> seeds in r~%")
(format t "~a~%" (xs:seeds r))
;乱数の生データを取得
(format t ">> rand 0 to UInt32Max~%")
(dotimes(i 5)
(format t "~d~%" (xs:rand r_def))
)
;0-100の乱数(100含む)を整数で取得
(format t ">> randInt 0 to 100~%")
(dotimes(i 5)
(format t "~d~%" (xs:randInt r_const 0 100))
)
;0-1の乱数を浮遊小数点で取得
(format t ">> randFloat 0 to 1~%")
(dotimes (i 5)
(format t "~d~%" (xs:randFloat r))
)
;listのシャッフル
;値渡しとなるので元の配列は破壊されない
(format t ">> shuffle list~%")
(setf a (loop for i from 0 below 20 collect i))
(format t "~A~%" (xs:shuffle r a))
(format t "~A~%" a)
;今の乱数を回した回数
(format t ">> randCount in r~%")
(format t "~d~%" (xs:randCount r))
)
(quit)
XorShift.lisp
(provide :XorShifts)
(defpackage XorShifts
(:use common-lisp)
(:nicknames :xs)
(:export
:XorShift
:XorShift-defaultSeed
:defaults
:seeds
:randCount
:rand
:randInt
:randFloat
:shuffle
)
)
(in-package XorShifts)
(defconstant defaults '(
(:x . 123456789)
(:y . 362436069)
(:z . 521288629)
(:w . 88675123)
))
(defclass XorShift()(
(w :initarg :w
:initform (get-universal-time))
(x :initarg :x
:initform nil)
(y :initarg :y
:initform nil)
(z :initarg :z
:initform nil)
(seeds :reader seeds
:initform nil)
(randCount :reader randCount
:initform 0
)
))
(defmethod initialize-instance :after ((self XorShift) &key)
(with-slots (w x y z seeds) self
(unless x (setf x (ash w 13)))
(unless y (setf y (logxor (ash w -9) (ash x 6))))
(unless z (setf z (ash y -7)))
(setf seeds `(
(:x . ,x)
(:y . ,y)
(:z . ,z)
(:w . ,w)
))
)
)
(defmethod rand((self XorShift))
(incf (slot-value self 'randCount))
(with-slots (w x y z) self
(let (tt)
(setf tt (logxor x (logand (ash x 11) #xFFFFFFFF)))
(setf x y)
(setf y z)
(setf z w)
(setf w (logxor (logxor w (ash w -19)) (logxor tt (ash tt -8))))
)
)
)
(defmethod randInt((self XorShift) &optional (min 0) (max #x7FFFFFFF))
(+(mod(rand self) (1+(- max min))) min)
)
(defmethod randFloat((self XorShift) &optional (min 0) (max 1))
(+(*(float(/(mod(rand self) #xFFFF) #xFFFF)) (- max min)) min)
)
(defmethod shuffle((self XorShift) _arr)
(let ((arr (copy-seq _arr)))
(loop for i from 0 below (1- (length arr)) do
(let ((r (randInt self i (1- (length arr)))))
(rotatef (nth i arr) (nth r arr))
)
)
arr
)
)
(defclass XorShift-defaultSeed(XorShift)(
(w :initform (rest(assoc :w defaults)))
(x :initform (rest(assoc :x defaults)))
(y :initform (rest(assoc :y defaults)))
(z :initform (rest(assoc :z defaults)))
))
Clojure(CLR)
TestXS.clj
(require 'XorShift)
(let [
r_def (XorShift/make-XorShift-defaultSeed)
r_const (XorShift/make-XorShift 100)
r (XorShift/make-XorShift)
a (atom nil)
]
;デフォルトのシード値を取得
(println ">> defaults")
(println XorShift/defaults)
;今の乱数に与えたシード値初期値
(println ">> seeds in r")
(println (:seeds r))
;乱数の生データを取得
(println ">> rand 0 to UInt32Max")
(loop[i 0](when(< i 5)
(println (XorShift/-rand r_def))
(recur(inc i))))
;0-100の乱数(100含む)を整数で取得
(println ">> randInt 0 to 100")
(loop[i 0](when(< i 5)
(println (XorShift/randInt r_const 0 100))
(recur(inc i))))
;0-1の乱数を浮遊小数点で取得
(println ">> randFloat 0 to 1")
(loop[i 0](when(< i 5)
(println (XorShift/randFloat r))
(recur(inc i))))
;listのシャッフル
;値渡しとなるので元の配列は破壊されない
(println ">> shuffle list")
(reset! a (for[i (range 20)] i))
(println (XorShift/-shuffle r @a))
(println @a)
;今の乱数を回した回数
(println ">> randCount in r")
(println @(:randCount r))
)
XorShift.clj
(ns XorShift)
(def defaults{
:x 123456789
:y 362436069
:z 521288629
:w 88675123
})
(defprotocol IXorShift
(-rand[self])
(randInt[self][self min max])
(randFloat[self][self min max])
(-shuffle[self _arr])
)
(def MXorShift{
:-rand(fn[self]
(swap! (:randCount self) inc)
(let [t (bit-xor @(:x self) (bit-and (bit-shift-left @(:x self) 11) 0xFFFFFFFF))]
(reset! (:x self) @(:y self))
(reset! (:y self) @(:z self))
(reset! (:z self) @(:w self))
(reset! (:w self) (bit-xor (bit-xor @(:w self) (bit-shift-right @(:w self) 19)) (bit-xor t (bit-shift-right t 8))))
)
)
:randInt(fn
([self] (randInt self 0 0x7FFFFFFF))
([self min max]
(+(mod(-rand self) (inc(- max min))) min)
)
)
:randFloat(fn
([self] (randFloat self 0 1))
([self min max]
(+(*(float(/(mod(-rand self) 0xFFFF) 0xFFFF)) (- max min)) min)
)
)
:-shuffle(fn[self _arr]
(let [arr (map #(atom %) _arr)]
(loop[i 0](when(< i (dec(count arr)))
(let [r (randInt self i (dec(count arr)))]
(let [tmp @(nth arr i)]
(reset! (nth arr i) @(nth arr r))
(reset! (nth arr r) tmp)
))
(recur(inc i))))
(map #(deref %) arr)
)
)
})
(defrecord XorShift[w x y z seeds randCount])
(extend XorShift IXorShift MXorShift)
(defn make-XorShift
([](make-XorShift Environment/TickCount))
([{:keys [w x y z] :or {w Environment/TickCount,x nil,y nil,z nil}}]
(let [x (if(= nil x) (bit-shift-left w 13) x)]
(let [y (if(= nil y) (bit-xor (bit-shift-right w 9) (bit-shift-left x 6)) y)]
(let [z (if(= nil z) (bit-shift-right y 7) z)]
(let [seeds {
:x x
:y y
:z z
:w w
}]
(XorShift. (atom w) (atom x) (atom y) (atom z) seeds (atom 0))
))))
)
)
(defrecord XorShift-defaultSeed[w x y z seeds randCount])
(extend XorShift-defaultSeed IXorShift MXorShift)
(defn make-XorShift-defaultSeed[]
(let [w (:w defaults),x (:x defaults),y (:y defaults),z (:z defaults)]
(let [seeds {
:x x
:y y
:z z
:w w
}]
(XorShift-defaultSeed. (atom w) (atom x) (atom y) (atom z) seeds (atom 0))
))
)
Tcl
TestXS.tcl
source XorShift.tcl
apply {{} {
#XorShift乱数ジェネレータの初期化
# 論文デフォルトシード
set r_def [XorShift::defaultSeed new]
# 固定値シード
set r_var [XorShift new 100]
# 時間シード
set r [XorShift new]
#デフォルトシード値の取得
puts ">> defaults"
puts [array get XorShift::defaults]
#for(var i in XorShift.defaults){
# WScript.Echo(i+":"+XorShift.defaults[i]);
#}
#適用したシード値の取得
puts ">> seeds in r"
array set r_seeds [$r seeds]
puts [array get r_seeds]
#乱数の生データを取得
puts ">> rand 0 to UInt32Max"
for {set i 0} {$i<5} {incr i} {
puts [$r_def rand]
}
#0-100の乱数(100含む)を整数で取得
puts ">> randInt 0 to 100"
for {set i 0} {$i<5} {incr i} {
puts [$r_var randInt 0 100]
}
#0-1の乱数を浮遊小数点で取得
puts ">> randFloat 0 to 1"
for {set i 0} {$i<5} {incr i} {
puts [$r randFloat]
}
#listのシャッフル
#値渡しとなるので元のlistは破壊されない
puts ">> shuffle list"
set a {}
for {set i 0} {$i<20} {incr i} {set a [concat $a $i]}
puts [$r shuffle $a]
puts $a
#今の乱数を回した回数
puts ">> randCount in r"
puts [$r randCount]
#コンソール停止
gets stdin
}}
XorShift.tcl
oo::class create XorShift {
variable x
variable y
variable z
variable w
variable seeds
method seeds {} {return [array get seeds]}
variable randCount
method randCount {} {return $randCount}
constructor {
{_w "[clock clicks -milliseconds]"}
{_x "$w<<13"}
{_y "($w>>9)^($x<<6)"}
{_z "$y>>7"}
} {
set randCount 0
set w [expr $_w]
set x [expr $_x]
set y [expr $_y]
set z [expr $_z]
array set seeds [list x $x y $y z $z w $w]
}
method rand {} {
incr randCount
set t [expr $x^($x<<11&0xFFFFFFFF)]
set x $y
set y $z
set z $w
return [set w [expr ($w^($w>>19))^($t^($t>>8))]]
}
method randInt {{min 0} {max 0x7FFFFFFF}} {
return [expr [my rand]%($max-$min+1)+$min]
}
method randFloat {{min 0} {max 1}} {
return [expr [my rand]%0xFFFF*1./0xFFFF*($max-$min)+$min]
}
method shuffle {arr} {
for {set i 0} {$i<=[llength $arr]-2} {incr i} {
set r [my randInt $i [expr [llength $arr]-1]]
set tmp [lindex $arr $i]
lset arr $i [lindex $arr $r]
lset arr $r $tmp
}
return $arr
}
}
namespace eval XorShift {
variable defaults
array set defaults {
x 123456789
y 362436069
z 521288629
w 88675123
}
oo::class create defaultSeed {
superclass XorShift
constructor {} {
next $XorShift::defaults(w) \
$XorShift::defaults(x) \
$XorShift::defaults(y) \
$XorShift::defaults(z)
}
}
}
実装の補足とか
- ジェネレータを使える言語についてはそれを使用し、使えないものについてはクラスに値を保持させた。
- 2017/01/15追記:
- モジュール化したものに置換。
- 2017/01/15追記:
- シード値はXorShift実装例のwを置き換えるものとした。
- シードのデフォルト値は各言語の時間的なものを適用した。
- 2017/01/08追記:
- x,y,z,wの全シード値を変更できるように修正した。
- 静的メンバ変数(プロパティ)(pythonとCLのみメソッド)に各シードのデフォルト値を定義した。
- 動的メンバ変数(プロパティ)に乱数カウンタと論文で見られるwの初期シード値(wのみ)を追加した。
- シードのデフォルト値を時間を基に線形合同法(シード値はUnix?で使用される標準値)を行った値に変更。
- 2017/01/15追記:
- シード値関連をx,y,z,w全て連想配列に格納(C++は構造体、HSPはメソッド、CLは連想リスト)。
- HSPでnewcomから"Scripting.Dictionary"(Windows標準API)が使えることも知ったけど、色々環境的な理由で断念。
Keysの回収がやたら面倒だとか機能的な問題も少しあるみたい。 - シードのデフォルト値を適用するためのサブクラスを追加(C++、HSPはメソッド)。
- w以外のシード値を標準でシフト&排他的論理和でシャッフルするようにした。
- 2017/01/08追記:
- 乱数の取得にあたって範囲内の整数を取得するrandIntメソッドと浮遊小数点値を取得するrandFloatメソッドを作成した。ただし、randFloatメソッドについてはシードを変えても偏りが見られるため何かかしらの修正が必要だと考える。
- 2017/01/08追記:
- randFloutメソッドで上位16bitを切り捨てて計算するように変更。また、上記のシードの変更にも加え、値の偏りについては改善されたように見える。
- 乱数の生データを受け取るrandメソッドを定義した。
- shuffleメソッドを追加した。各言語の主流なリストオブジェクトをいくつかずつ対応。
- 静的言語についてはtemplate/Genericを用いて実装。
- 引数で与えたリストを破壊しないように内部で複製を行う。
- HSPのメソッド名を名前空間の関係から頭にxsを付けたものに変更。
- 2017/01/08追記:
- JavaScriptの型を固定するためにUint32Arrayオブジェクトを使用した。また、JavaScriptには符号なしのビットシフトを行うための>>>演算子が存在する。
- 2017/01/08追記: JavaScriptでInt32をラップアラウンドさせると2進数の値も負数になるが、hoge>>>0でUInt型にキャストできることを確認。Uint32Arrayよりもこちらの方が軽そうなのでUint32Arrayを削除した。
- Python、CommonLispにおいては、UInt型を明示して使用することができないため、0xFFFFFFFF(Uint最大値)と論理積を行うことでマスクを行って固定した。
- HSPは整数型がInt型しか存在しない。こちらの意見を参考に実装した。また、HSPはラップアラウンド(整数型の限界を超えて値がひっくり返る現象)を起こした値であっても、strfで符号なし型として表示(%u)することでUInt型を表現できる。
- Tclの実装(2017/9/3投稿)を統合。
- 言語自身の文法の部分を除けばすんなり実装できた。
名前空間関連には結構悩んだので妥協策がちょいちょい見える。 - UInt風ギミックの実装についてはPython・CommonLisp編と一緒。
これにより生成される乱数の質は他言語実装と殆ど一緒。 - arrayを直に返せないことに衝撃。listに変換し直せばとりあえず返せるのでそれで妥協。
- せっかくだから言語機能のコルーチンをジェネレータとして使いたかったけど、
クラス内で使用する方法が分からなかったので諦めた。
C++等の実装で使ったジェネレータ風実装でお茶を濁した。
- 言語自身の文法の部分を除けばすんなり実装できた。
- 2018/3/7 HSP修正。
- 2018/3/16 HSP修正。
- コルーチン版追加。HSP3dish互換性のため未使用版と並行して記載する。
- 2018/5/25 ClojureCLR追加。
- CLRである理由は時間シードの取得で.Netに依存するため。Environment/TickCountの部分を(rand-int 07FFFFFFF)にでも置き換えておけば普通のClojureでも動きます。
- 関数型言語だけどアプローチはオブジェクト指向。一部の人には怒られる。