JavaScriptにXorShift128+を移植してみたかった

[XorShiftの派生品はたくさんあるそうで](http://xoroshiro.di.unimi.it/)、このうちのXorShift128+(64bitUIntを使用した物)を移植しようと試みた。結論としてはなんとかJavaScriptを64bit以上の整数を扱えるようにしない限り不可能。できたとしても速度的な利点が失われそう。

JavaScriptの表面では数値型はNumberとして扱われるけど内部的な型としてint32、float32、float64(double)の3つに分けられるみたいだ。asm.jsでそれぞれの型指定の方法が指示されているように、JavaScriptにおいても以下のキャスト方法が使用できる。(適切に使用すれば高速化も可能)

```js:
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までとなり([※](http://www.petitmonte.com/javascript/javascript_64bit.html))、それ以上は丸められてしまう様子。
そのため、XorShift128+に要求されるuint64と言った条件を達成することができず、このままでは移植は不可能という結論に達した。

下記にはここまでの過程で実装を試みたソースと結果を示す。

## bitInt64、bitInt53モジュール
シフト演算とか排他的論理和を32bit以上でも扱えるようにしたモジュール。
XorShiftするためだけに作っているので必要以上の機能はない。
ちなみにXorは文字列処理とかやっているのでむちゃくちゃ遅い。普通のXorと大体100倍くらい。

```js:bitInt64.js
"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;
		}
	};
})();
```
```js:bitInt53.js
"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+っぽい何か
みてくれは普通に移植した実装。

```js:XorShift128+.js
"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);
	}
})();
```
しかし、これを動かすと…

```text:出力コンソール
8388645
33816707
70368778527840
211106267172129
281552312399723
352084508939685
648800200157934600
2540241598295339500
2648407164293855000
2668752809767453700
2696584197286118000
5019905297681300000
12007711744268257000
9705407345729356000
13704980455792271000
```
お尻の方に0の塊が見える…

ちなみに正規な実装だとこんな感じ。

```text:出力コンソール
8388645
33816707
70368778527840
211106267172129
281552312399723
352084508939685
648800200157934532
2540241598295339419
2648407162339308712
2668752799858137237
2693699070923777171
4963962142036894822
11906738374415673757
9632391838565739090
2066554175270807792
```
こちらはVBに移植したもの。

```vbnet:XorShift128+.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
```
これをコンパイルするときは次のように

```bat:
C:\> vbc XorShift128+.vb /removeintchecks
```
"/removeintchecks"をつけないとオーバーフロー例外が発生するので注意。(Optionキーワードでいければいいのに…)

# XorShift??+
そこで、上であげたbitInt64.jsをbitInt53.jsに交換すると0を出さない乱数の出力が可能。ただし、bit数変わるので乱数の質は悪くなっていそう。
適正なシフト数にすればいいんだろうけど、素人には弄りようのない値かなぁ…
また、モジュールの遅さの合間ってアルゴリズムの利点を完全に殺しているので、現状使う利点は一切無しというところか。

# 実行環境
node v7.4.0
vbc Version 1.3.1.60616