71 lines
2.7 KiB
Text
71 lines
2.7 KiB
Text
;Some definitions to help in the explanation:
|
||
|
||
:Floor operation<br>
|
||
::https://en.wikipedia.org/wiki/Floor_and_ceiling_functions<br>
|
||
::Greatest integer less than or equal to a real number.
|
||
|
||
:Bitwise Logical shift operators (c-inspired)<br>
|
||
::https://en.wikipedia.org/wiki/Bitwise_operation#Bit_shifts<br>
|
||
::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
|
||
|
||
|
||
;[https://www.pcg-random.org/download.html#minimal-c-implementation| PCG32] Generator (pseudo-code):
|
||
|
||
PCG32 has two unsigned 64-bit integers of internal state:
|
||
# '''state''': All 2**64 values may be attained.
|
||
# '''sequence''': Determines which of 2**63 sequences that <code>state</code> iterates through. (Once set together with <code>state</code> at time of seeding will stay constant for this generators lifetime).
|
||
|
||
Values of <code>sequence</code> allow 2**63 ''different'' sequences of random numbers from the same <code>state</code>.
|
||
|
||
The algorithm is given 2 U64 inputs called <code>seed_state</code>, and <code>seed_sequence</code>. The algorithm proceeds in accordance with the following pseudocode:-
|
||
<pre>
|
||
const N<-U64 6364136223846793005
|
||
const inc<-U64 (seed_sequence << 1) | 1
|
||
state<-U64 ((inc+seed_state)*N+inc
|
||
do forever
|
||
xs<-U32 (((state>>18)^state)>>27)
|
||
rot<-INT (state>>59)
|
||
OUTPUT U32 (xs>>rot)|(xs<<((-rot)&31))
|
||
state<-state*N+inc
|
||
end do
|
||
</pre>
|
||
Note that this an [[wp:Anamorphism |anamorphism]] – dual to catamorphism, and encoded in some languages as a general higher-order `unfold` function, dual to `fold` or `reduce`.
|
||
|
||
;Task:
|
||
|
||
* Generate a class/set of functions that generates pseudo-random
|
||
numbers using the above.
|
||
|
||
* Show that the first five integers generated with the seed <code>42, 54</code>
|
||
are: 2707161783 2068313097 3122475824 2211639955 3215226955
|
||
|
||
|
||
|
||
* Show that for an initial seed of <code>987654321, 1</code> 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.
|
||
|
||
|