# Xoroshiro128pのジャンプ関数を考える
### 雑な序文
ありがたいことに剣盾のグローバル乱数は高速な消費が可能で、しかも最レア証かつ星型色違いの超低確率個体を狙う場合に数億消費まで検索範囲を広げたいことがままあることから、検索処理の並列化を行いたい場面が出てきた。並列化を行う場合、検索範囲をスレッド数で分割し、1つのスレッドに1つの範囲の検索を任せる実装が素直だろう。しかし、この方法を取るには乱数を範囲の長さだけ一気に進める必要がある。更新関数を1回ずつ呼んでいたのでは、並列化する意味が無くなってしまう。したがって乱数を一定数進める関数=ジャンプ関数が必要になる。

### ジャンプ関数の考察
結論から言うと、繰り返し二乗法(ダブリング？)を使えばよい。状態の更新は${\bf x}_{n+1} = f({\bf x}_{n})$と表せるのだから、${\bf x}_{n+k}=f^{k}({\bf x}_{n})$である。ここで、前処理として$f^{2^0}, f^{2^1}, \cdots, f^{2^i},\cdots$を行列で表現し、保持しておけば、任意の$f^k$はこれらの積として得られる(たとえば$k=827=1 + 2 + 8 + 16 + 32 + 256 + 512$なら、$f,f^2,f^8,f^{16},f^{32},f^{256},f^{512}$に対応する$7$個の行列を掛けるだけで良い)。

### 処理速度
やばいくらい速い。


##### 2021.12.31追記
上記の計測はデバッグビルドで、コンパイラくんが最適化してくれていなかったので、リリースビルドにして最適化を掛けてみました。

速いね(思考放棄)
単位は間違えていません。念のため。

### 肝心のコードは？
ひとまず[ここ](https://gist.github.com/yatsuna827/20d3afbc88220e23be66c01ea204d4ac)に置きました。~~そのうち~~[PokemonPRNG](https://github.com/yatsuna827/PokemonPRNG)にも実装~~予定~~しました。

### 余談
oupo先生の[これ](https://oupo.hatenadiary.com/entry/20100112/1263306151)も同じ原理。MTみたいなクソデカ状態を持っている乱数アルゴリズムだと、遷移関数の表現もクソデカくなるので、メモするのが厳しそう…。