Analyzing XORShift128+ PRNG

xorshift128.go

// Studying XorShift128+ pseudorandom number generator
package main

import (
	"fmt"
	"strconv"
)

var state0, state1 uint64

// Permute state
func permute() {
	x, y := state0, state1
	x ^= x << 23
	x ^= x >> 17
	x ^= y ^ (y >> 26)
	state0, state1 = y, x
}

// Reverse, "unpermute" state
func reverse() {
	x, y := state1, state0
	x ^= y ^ (y >> 26)
	x = reverseXorRshift(x, 17)
	x = reverseXorLshift(x, 23)
	state0, state1 = x, y
}

// Get number from current state.
// Basically, XorShift128+ is:
//
//  initState: state0, state1 = seed0, seed1
//  getNextRandomNumber: { permute(); return rnd() }
//
func rnd() uint64 {
	return state0 + state1
}

// Helper functions

// Taken from http://stackoverflow.com/a/31515396/311196
func reverseXorLshift(y uint64, shift uint) uint64 {
	x := y & ((1 << shift) - 1)
	for i := uint(0); i < 64-shift; i++ {
		v := uint64(0)
		if (x&(1<<i) != 0) != (y&(1<<(shift+i)) != 0) {
			v = 1
		}
		x |= v << (shift + i)
	}
	return x
}

func reverseBin(x uint64) uint64 {
	s := fmt.Sprintf("%064b", x)
	// reverse string
	r := []rune(s)
	for i, j := 0, len(r)-1; i < len(r)/2; i, j = i+1, j-1 {
		r[i], r[j] = r[j], r[i]
	}
	n, err := strconv.ParseUint(string(r), 2, 64)
	if err != nil {
		panic(err)
	}
	return n
}

func reverseXorRshift(y uint64, shift uint) uint64 {
	return reverseBin(reverseXorLshift(reverseBin(y), shift))
}

var cnt = 0

func printstate() {
	cnt++
	fmt.Printf("%d\t%016x %016x\n", cnt, state0, state1)
}

func printnum(name string, n uint64) {
	fmt.Printf("%s\t%016x\n", name, n)
}

func main() {
	//state0 = 0x8000000000000000
	state0 = 0x0102030405060708
	state1 = 0x091011121314151f
	printstate()
	a := state0
	n0 := rnd()
	permute()
	c := state1
	printnum("n0", n0)
	printstate()
	n1 := rnd()
	printnum("n1", n1)
	permute()
	n2 := rnd()
	printstate()
	printnum("n2", n2)
	/*

		n0 = a + b
		n1 = b + c
		n0 - n1 = a - c

	*/
	fmt.Println()
	printnum("n0-n1", n0-n1)
	printnum("a-c", a-c)
	fb := uint64(0x8a10d09796159610)
	fa := (n0 - n1) + fb
	printnum("fa", fa)
	fbPrev := n0 - fa
	printnum("fbPrev", fbPrev)
}