Pseudo-random numbers/PCG32

Pseudo-random numbers/PCG32 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

| Bitwise or operator

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

Bitwise comparison gives 1 if any of corresponding bits are 1

E.g Binary 00110101 | Binary 00110011 == Binary 00110111

PCG32 Generator (pseudo-code)

   /* Let u64 denote an unsigned 64 bit integer type. */
   /* Let u32 denote an unsigned 32 bit integer type. */
   
   u64 global constant CONST = 6364136223846793005
   
   class Pcg32
       u64 instance variable state = HEX 853c49e6748fea9b 
       u64 instance variable inc   = HEX da3e39cb94b95bdb    /* Always odd */
   
       method seed(u64 seed_state, u64 seed_sequence)
           state =  0
           inc = (seed_sequence << 1) | 1  # shift and | ensures its odd
           next_int()
           state = state + seed_state
           next_int()
       end method
       
       method next_int()
           u64 old = state
           state = (old * CONST) + inc
           u32 xorshifted = ((old >> 18) ^ old) >> 27
           u32 rot = old >> 59
           u32 answer = (xorshifted >> rot) | (xorshifted << ((-rot) & 31))
           
           return answer
       end method
       
       method next_float():
           return float next_int() / (1 << 32)
       end method
       
   end class

PCG32 Use

   random_gen = instance Pcg_32
   random_gen.seed(42, 54)
   print(random_gen.next_int())   /* 2707161783 */
   print(random_gen.next_int())   /* 2068313097 */
   print(random_gen.next_int())   /* 3122475824 */
   print(random_gen.next_int())   /* 2211639955 */
   print(random_gen.next_int())   /* 3215226955 */

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 42, 54

are as shown above

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

   floor(random_gen.next_float() * 5)

Is as follows:

   0: 20049, 1: 20022, 2: 20115, 3: 19809, 4: 20005

• Show your output here, on this page.

Python

<lang python>mask64 = (1 << 64) - 1 mask32 = (1 << 32) - 1 CONST = 6364136223846793005

class PCG32():

   def __init__(self, seed_state=None, seed_sequence=None):
       if all(type(x) == int for x in (seed_state, seed_sequence)):
           self.seed(seed_state, seed_sequence)
       else:
           self.state = self.inc = 0
   
   def seed(self, seed_state, seed_sequence):
       self.state = 0
       self.inc = ((seed_sequence << 1) | 1) & mask64
       self.next_int()
       self.state = (self.state + seed_state)
       self.next_int()
       
   def next_int(self):
       "return random 32 bit unsigned int"
       old = self.state
       self.state = ((old * CONST) + self.inc) & mask64
       xorshifted = (((old >> 18) ^ old) >> 27) & mask32
       rot = (old >> 59) & mask32
       answer = (xorshifted >> rot) | (xorshifted << ((-rot) & 31))
       answer = answer &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 = PCG32()
   random_gen.seed(42, 54)
   for i in range(5):
       print(random_gen.next_int())
       
   random_gen.seed(987654321, 1)
   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:

2707161783
2068313097
3122475824
2211639955
3215226955
{0: 20049, 1: 20022, 2: 20115, 3: 19809, 4: 20005}

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:

2707161783
2068313097
3122475824
2211639955
3215226955

The counts for 100,000 repetitions are:
  0 : 20049
  1 : 20022
  2 : 20115
  3 : 19809
  4 : 20005