Pseudo-random numbers/PCG32

From Rosetta Code
Revision as of 09:29, 12 August 2020 by PureFox (talk | contribs) (Added Go)
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.


Go

Translation of: Python

<lang go>package main

import ( 

   "fmt"
   "math"

)

const CONST = 6364136223846793005 const mask32 = (1 << 32) - 1

type Pcg32 struct{ state, inc uint64 }

func Pcg32New() *Pcg32 { return &Pcg32{0x853c49e6748fea9b, 0xda3e39cb94b95bdb} }

func (pcg *Pcg32) seed(seedState, seedSequence uint64) { 

   pcg.state = 0
   pcg.inc = (seedSequence << 1) | 1
   pcg.nextInt()
   pcg.state = pcg.state + seedState
   pcg.nextInt()

}

func (pcg *Pcg32) nextInt() uint32 { 

   old := pcg.state
   pcg.state = old*CONST + pcg.inc
   pcgshifted := uint32((((old >> 18) ^ old) >> 27) & mask32)
   rot := uint32((old >> 59) & mask32)
   return (pcgshifted >> rot) | (pcgshifted << ((-rot) & 31))

}

func (pcg *Pcg32) nextFloat() float64 { 

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

}

func main() { 

   randomGen := Pcg32New()
   randomGen.seed(42, 54)
   for i := 0; i < 5; i++ {
       fmt.Println(randomGen.nextInt())
   }

   var counts [5]int
   randomGen.seed(987654321, 1)
   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:
2707161783
2068313097
3122475824
2211639955
3215226955

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

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.new("6364136223846793005") var Mask64 = (BigInt.one << 64) - BigInt.one var Mask32 = (BigInt.one << 32) - BigInt.one

class Pcg32 { 

   construct new() {
       _state  = BigInt.fromBaseString("853c49e6748fea9b", 16)
       _inc    = BigInt.fromBaseString("da3e39cb94b95bdb", 16)
   }

   seed(seedState, seedSequence) {
       _state = BigInt.zero
       _inc = ((seedSequence << BigInt.one) | BigInt.one) & Mask64
       nextInt
       _state = _state + seedState
       nextInt
   }

   nextInt {
       var old = _state
       _state = (old*Const + _inc) & Mask64
       var xorshifted = (((old >> 18) ^ old) >> 27) & Mask32
       var rot = (old >> 59) & Mask32
       return ((xorshifted >> rot) | (xorshifted << ((-rot) & 31))) & Mask32
   }

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

}

var randomGen = Pcg32.new() randomGen.seed(BigInt.new(42), BigInt.new(54)) for (i in 0..4) System.print(randomGen.nextInt)

var counts = List.filled(5, 0) randomGen.seed(BigInt.new(987654321), BigInt.one) 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
Retrieved from "https://rosettacode.org/wiki/Pseudo-random_numbers/PCG32?oldid=301861"