Pseudo-random numbers/Xorshift star

Pseudo-random numbers/Xorshift star is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

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 64 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.

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 = 0;
   has $!state;
   constant mask64 = 2⁶⁴ - 1;
   constant const = 0x2545F4914F6CDD1D;

   submethod BUILD( :$seed ) { $!seed = $seed }

   method TWEAK { $!state = $!seed +& mask64 }

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

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

}

1. Test next-int

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

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

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

Output:

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