XorShiftの派生品はたくさんあるそうで、このうちのXorShift128+(64bitUIntを使用した物)を移植しようと試みた。結論としてはなんとかJavaScriptを64bit以上の整数を扱えるようにしない限り不可能。できたとしても速度的な利点が失われそう。
JavaScriptの表面では数値型はNumberとして扱われるけど内部的な型としてint32、float32、float64(double)の3つに分けられるみたいだ。asm.jsでそれぞれの型指定の方法が指示されているように、JavaScriptにおいても以下のキャスト方法が使用できる。(適切に使用すれば高速化も可能)
var a=(1+2)|0; //int32
var b=Math.fround(1+2); //float
var c=+(1+2); //double
この時、各種論理演算子がint32以外では使用できない。>>>でキャストすればuint32に見せかけることもできる(uint32になってる?)けど扱う実体としてはint32になるっぽい。また、仮に32bit以上でも論理演算子を使用できても、今度は浮遊小数点の精度問題に発展する。
JavaScriptで扱える最大の値型はdouble型となるが、double型で整数の精度は53bitまでとなり(※)、それ以上は丸められてしまう様子。
そのため、XorShift128+に要求されるuint64と言った条件を達成することができず、このままでは移植は不可能という結論に達した。
下記にはここまでの過程で実装を試みたソースと結果を示す。
bitInt64、bitInt53モジュール
シフト演算とか排他的論理和を32bit以上でも扱えるようにしたモジュール。
XorShiftするためだけに作っているので必要以上の機能はない。
ちなみにXorは文字列処理とかやっているのでむちゃくちゃ遅い。普通のXorと大体100倍くらい。
"use strict";
module.exports=(()=>{
const pad0="0000000000000000000000000000000000000000000000000000000000000000"
return class{
static ash(base,s){
return Math.floor(base*Math.pow(2,s));
}
static xor(left,right){
var leftBit=(pad0+left.toString(2)).slice(-64);
var rightBit=(pad0+right.toString(2)).slice(-64);
var xorBit="0b";
for(var i=0;i<64;i++) xorBit+=leftBit[i]!==rightBit[i]?"1":"0";
return +xorBit;
}
};
})();
"use strict";
module.exports=(()=>{
const pad0="00000000000000000000000000000000000000000000000000000"
return class{
static ash(base,s){
return Math.floor(base*Math.pow(2,s));
}
static xor(left,right){
var leftBit=(pad0+left.toString(2)).slice(-53);
var rightBit=(pad0+right.toString(2)).slice(-53);
var xorBit="0b";
for(var i=0;i<53;i++) xorBit+=leftBit[i]!==rightBit[i]?"1":"0";
return +xorBit;
}
};
})();
XorShift128+っぽい何か
みてくれは普通に移植した実装。
"use strict";
const [ash,xor]=(b=>[b.ash,b.xor])(require("./bitInt64"));
function* XorShift128t(s){
for(;;){
var s1=s[0];
const s0=s[1];
s[0]=s0;
s1=xor(s1,ash(s1,23));
s[1]=xor(s1,xor(s0,xor(ash(s1,-18),(ash(s0,-5)))));
yield s[1]+s0;
}
}
(function(){
var s=[1,2];
var rand=XorShift128t(s);
for(let i=0;i<15;i++){
console.log(rand.next().value);
}
})();
しかし、これを動かすと…
8388645
33816707
70368778527840
211106267172129
281552312399723
352084508939685
648800200157934600
2540241598295339500
2648407164293855000
2668752809767453700
2696584197286118000
5019905297681300000
12007711744268257000
9705407345729356000
13704980455792271000
お尻の方に0の塊が見える…
ちなみに正規な実装だとこんな感じ。
8388645
33816707
70368778527840
211106267172129
281552312399723
352084508939685
648800200157934532
2540241598295339419
2648407162339308712
2668752799858137237
2693699070923777171
4963962142036894822
11906738374415673757
9632391838565739090
2066554175270807792
こちらはVBに移植したもの。
Option Strict On
Imports System.Collections.Generic
Module Program
Iterator Function XorShift128t(s As ULong()) As IEnumerator(Of ULong)
Do
Dim s1 As ULong=s(0)
Dim s0 As ULong=s(1)
s(0)=s0
s1=s1 Xor s1<<23
s(1) =s1 Xor (s0 Xor ((s1>>18) Xor (s0>>5)))
Yield s(1)+s0
Loop
End Function
Sub Main()
Dim s={1UL,2UL}
Dim rand As IEnumerator(Of ULong)=XorShift128t(s)
For i=1 To 15
rand.MoveNext()
Console.WriteLine(rand.Current)
Next
End Sub
End Module
これをコンパイルするときは次のように
C:\> vbc XorShift128+.vb /removeintchecks
"/removeintchecks"をつけないとオーバーフロー例外が発生するので注意。(Optionキーワードでいければいいのに…)
XorShift??+
そこで、上であげたbitInt64.jsをbitInt53.jsに交換すると0を出さない乱数の出力が可能。ただし、bit数変わるので乱数の質は悪くなっていそう。
適正なシフト数にすればいいんだろうけど、素人には弄りようのない値かなぁ…
また、モジュールの遅さの合間ってアルゴリズムの利点を完全に殺しているので、現状使う利点は一切無しというところか。
実行環境
node v7.4.0
vbc Version 1.3.1.60616