Skip to content

Instantly share code, notes, and snippets.

@susisu
Last active January 15, 2019 08:20
Show Gist options
  • Save susisu/b3543ef5e59470641524d7f78a9e1580 to your computer and use it in GitHub Desktop.
Save susisu/b3543ef5e59470641524d7f78a9e1580 to your computer and use it in GitHub Desktop.
-- tf-random 0.5
import System.Random.TF.Gen
-- Utility functions to choose one of splitted generators.
left g = let (g', _) = split g in g'
right g = let (_, g') = split g in g'
-- Initialize a generator (the seed is not relevant).
gen = seedTFGen (0, 0, 0, 0)
-- Let `b` be the tree position bits of a generator and `bi` the index in it. Now `b` and `bi` of
-- the generator `gen` can be illustrated as follows:
-- 0b 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 -- b
-- ^ -- bi
-- Apply `left` or `right` more than 32 times to make `bi` > 32 (here I choose `right` 40 times).
gen' = iterate right gen !! 40
-- 0b 00000000 00000000 00000000 11111111 11111111 11111111 11111111 11111111 -- b
-- ^ -- bi
-- Create two "independent" generators using `splitn` (I choose `nbits` = 32 for simplicity).
gen1 = splitn gen' 32 0xFFFFFFFF
gen2 = splitn gen' 32 0xFEFFFFFF
-- Something wrong happens here. Let `i` be the third argument to `splitn`. The lower 24 bits of `i`
-- are used to compute a new key, and higher 8 bits should become the next tree position.
-- The expected results are as follows:
-- gen1:
-- 0b 00000000 00000000 00000000 00000000 00000000 00000000 00000000 11111111 -- b
-- ^ -- bi
-- gen2:
-- 0b 00000000 00000000 00000000 00000000 00000000 00000000 00000000 11111110 -- b
-- ^ -- bi
-- However, since the second argument of `shiftR` operation, which is computed by `bi + nbits - 64`,
-- is wrong, the next tree position will be incorrect. The actual results are:
-- gen1:
-- 0b 00000000 00000000 00000000 00000000 00000000 11111111 11111111 11111111 -- b
-- ^ -- bi
-- gen2:
-- 0b 00000000 00000000 00000000 00000000 00000000 11111110 11111111 11111111 -- b
-- ^ -- bi
-- The correct argument can be computed by `64 - bi`. Note that the newly computed key for both
-- `gen1` and `gen2` are identical, since the lower 24 bits of `i` are equal.
-- Then apply `left` 8 times to move `bi`, and apply `left` or `right` respectively.
gen1' = left $ iterate left gen1 !! 8
gen2' = right $ iterate left gen2 !! 8
-- Now `gen1'` and `gen2'` have the identical internal state, though they should be independent to
-- each other by nature.
-- 0b 00000000 00000000 00000000 00000000 00000000 11111111 11111111 11111111 -- b
-- ^ -- bi
-- Indeed, the numbers generated from `gen1'` and `gen2'` are equal.
(v1, _) = next gen1'
(v2, _) = next gen2'
t = v1 == v2 -- True
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment