Skip to content

Instantly share code, notes, and snippets.

@dchest
Last active February 28, 2016 14:35
Show Gist options
  • Save dchest/944ff4cb75ef6a8150df to your computer and use it in GitHub Desktop.
Save dchest/944ff4cb75ef6a8150df to your computer and use it in GitHub Desktop.
Analyzing XORShift128+ PRNG
// 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)
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment