Pseudo-random numbers/Xorshift star

Some definitions to help in the explanation

Floor operation

https://en.wikipedia.org/wiki/Floor_and_ceiling_functions

Greatest integer less than or equal to a real number.

Bitwise Logical shift operators (c-inspired)

https://en.wikipedia.org/wiki/Bitwise_operation#Bit_shifts

Binary bits of value shifted left or right, with zero bits shifted in where appropriate.

Examples are shown for 8 bit binary numbers; most significant bit to the left.

<< Logical shift left by given number of bits.

E.g Binary 00110101 << 2 == Binary 11010100

>> Logical shift right by given number of bits.

E.g Binary 00110101 >> 2 == Binary 00001101

^ Bitwise exclusive-or operator

https://en.wikipedia.org/wiki/Exclusive_or

Bitwise comparison for if bits differ

E.g Binary 00110101 ^ Binary 00110011 == Binary 00000110

Xorshift_star Generator (pseudo-code)

   /* Let u64 denote an unsigned 64 bit integer type. */
   /* Let u32 denote an unsigned 32 bit integer type. */

   class Xorshift_star
       u64 state       /* Must be seeded to non-zero initial value */
       u64 const = HEX '2545F4914F6CDD1D'

       method seed(u64 num):
           state =  num
       end method
       
       method next_int():
           u64 x = state
           x = x ^ (x >> 12)
           x = x ^ (x << 25)
           x = x ^ (x >> 27)
           state = x
           u32 answer = ((x * const) >> 32)
           
           return answer
       end method
       
       method next_float():
           return float next_int() / (1 << 32)
       end method
       
   end class

Xorshift use

   random_gen = instance Xorshift_star
   random_gen.seed(1234567)
   print(random_gen.next_int())   /* 3540625527 */
   print(random_gen.next_int())   /* 2750739987 */
   print(random_gen.next_int())   /* 4037983143 */
   print(random_gen.next_int())   /* 1993361440 */
   print(random_gen.next_int())   /* 3809424708 */

Task

Generate a class/set of functions that generates pseudo-random

numbers as shown above.

Show that the first five integers genrated with the seed 1234567

are as shown above

Show that for an initial seed of 987654321, the counts of 100_000 repetitions of

   floor(random_gen.next_float() * 5)

Is as follows:

   0: 20103, 1: 19922, 2: 19937, 3: 20031, 4: 20007

Show your output here, on this page.

Factor

<lang factor>USING: accessors kernel literals math math.statistics prettyprint sequences ; IN: rosetta-code.xorshift-star

CONSTANT: mask64 $[ 1 64 shift 1 - ] CONSTANT: mask32 $[ 1 32 shift 1 - ] CONSTANT: const 0x2545F4914F6CDD1D

TUPLE: xorshift-star state ;

<xorshift-star> ( seed -- xorshift-star )

   mask64 bitand xorshift-star boa ;

twiddle ( m n -- n ) dupd shift bitxor mask64 bitand ;

next-int ( obj -- n )

   dup state>> -12 twiddle 25 twiddle -27 twiddle tuck swap
   state<< const * mask64 bitand -32 shift mask32 bitand ;

next-float ( obj -- n ) next-int 1 32 shift / ;

! ---=== Task ===--- 1234567 <xorshift-star> 5 [ dup next-int . ] times

987654321 >>state 100,000 [ dup next-float 5 * >integer ] replicate nip histogram .</lang>

Output:

3540625527
2750739987
4037983143
1993361440
3809424708
H{ { 0 20103 } { 1 19922 } { 2 19937 } { 3 20031 } { 4 20007 } }

Go

Translation of: Python

<lang go>package main

import (

   "fmt"
   "math"

)

const CONST = 0x2545F4914F6CDD1D const mask32 = (1 << 32) - 1

type XorshiftStar struct{ state uint64 }

func XorshiftStarNew(state uint64) *XorshiftStar { return &XorshiftStar{state} }

func (xor *XorshiftStar) seed(state uint64) { xor.state = state }

func (xor *XorshiftStar) nextInt() uint32 {

   x := xor.state
   x = x ^ (x >> 12)
   x = x ^ (x << 25)
   x = x ^ (x >> 27)
   xor.state = x
   return uint32((x * CONST) >> 32 & mask32)

}

func (xor *XorshiftStar) nextFloat() float64 {

   return float64(xor.nextInt()) / (1 << 32)

}

func main() {

   randomGen := XorshiftStarNew(1234567)
   for i := 0; i < 5; i++ {
       fmt.Println(randomGen.nextInt())
   }

   var counts [5]int
   randomGen.seed(987654321)
   for i := 0; i < 1e5; i++ {
       j := int(math.Floor(randomGen.nextFloat() * 5))
       counts[j]++
   }
   fmt.Println("\nThe counts for 100,000 repetitions are:")
   for i := 0; i < 5; i++ {
       fmt.Printf("  %d : %d\n", i, counts[i])
   }

}</lang>

Output:

3540625527
2750739987
4037983143
1993361440
3809424708

The counts for 100,000 repetitions are:
  0 : 20103
  1 : 19922
  2 : 19937
  3 : 20031
  4 : 20007

Python

<lang python>mask64 = (1 << 64) - 1 mask32 = (1 << 32) - 1 const = 0x2545F4914F6CDD1D

class Xorshift_star():

   def __init__(self, seed=0):
       self.state = seed & mask64

   def seed(self, num):
       self.state =  num & mask64
   
   def next_int(self):
       "return random int between 0 and 2**32"
       x = self.state
       x = (x ^ (x >> 12)) & mask64
       x = (x ^ (x << 25)) & mask64
       x = (x ^ (x >> 27)) & mask64
       self.state = x
       answer = (((x * const) & mask64) >> 32) & mask32 
       return answer
   
   def  next_float(self):
       "return random float between 0 and 1"
       return self.next_int() / (1 << 32)

if __name__ == '__main__':

   random_gen = Xorshift_star()
   random_gen.seed(1234567)
   for i in range(5):
       print(random_gen.next_int())
       
   random_gen.seed(987654321)
   hist = {i:0 for i in range(5)}
   for i in range(100_000):
       hist[int(random_gen.next_float() *5)] += 1
   print(hist)</lang>

Output:

3540625527
2750739987
4037983143
1993361440
3809424708
{0: 20103, 1: 19922, 2: 19937, 3: 20031, 4: 20007}

Raku

Works with: Rakudo version 2020.07

Translation of: Python

<lang perl6>class Xorshift-star {

   has $!seed;
   has $!state;
   constant mask64 = 2⁶⁴ - 1;
   constant const = 0x2545F4914F6CDD1D;

   submethod BUILD ( Int :$seed where * > 0 = 1 ) {
       $!seed  = $seed;
       $!state = $!seed +& mask64
    }

   method next-int {
       $!state +^= ($!state +> 12) +& mask64;
       $!state +^= ($!state +< 25) +& mask64;
       $!state +^= ($!state +> 27) +& mask64;
       (($!state * const) +> 32) +& (2³² - 1)
   }

   method next-rat { self.next-int / 2³² }

}

Test next-int

my $rng = Xorshift-star.new( :seed(1234567) ); .say for $rng.next-int xx 5;

Test next-rat (since these are rational numbers by default)

$rng = Xorshift-star.new( :seed(987654321) ); say ( ($rng.next-rat * 5).floor xx 100_000 ).Bag;</lang>

Output:

3540625527
2750739987
4037983143
1993361440
3809424708
Bag(0(20103) 1(19922) 2(19937) 3(20031) 4(20007))

Wren

Translation of: Python

Library: Wren-big

As Wren doesn't have a 64-bit integer type, we use BigInt instead. <lang ecmascript>import "/big" for BigInt

var Const = BigInt.fromBaseString("2545F4914F6CDD1D", 16) var Mask64 = (BigInt.one << 64) - BigInt.one var Mask32 = (BigInt.one << 32) - BigInt.one

class XorshiftStar {

   construct new(state) {
       _state  = state & Mask64
   }

   seed(num) { _state = num & Mask64}

   nextInt {
       var x = _state 
       x = (x ^ (x >> 12)) & Mask64
       x = (x ^ (x << 25)) & Mask64
       x = (x ^ (x >> 27)) & Mask64
       _state = x
       return (((x * Const) & Mask64) >> 32) & Mask32
   }

   nextFloat { nextInt.toNum / 2.pow(32) }

}

var randomGen = XorshiftStar.new(BigInt.new(1234567)) for (i in 0..4) System.print(randomGen.nextInt)

var counts = List.filled(5, 0) randomGen.seed(BigInt.new(987654321)) for (i in 1..1e5) {

   var i = (randomGen.nextFloat * 5).floor
   counts[i] = counts[i] + 1

} System.print("\nThe counts for 100,000 repetitions are:") for (i in 0..4) System.print(" %(i) : %(counts[i])")</lang>

Output:

3540625527
2750739987
4037983143
1993361440
3809424708

The counts for 100,000 repetitions are:
  0 : 20103
  1 : 19922
  2 : 19937
  3 : 20031
  4 : 20007