# Going backward in random number generation

**URL:** <https://discourse.julialang.org/t/going-backward-in-random-number-generation/24257>\
**Category:** General Usage\
**Created:** [May 15, 2019, 8:36pm UTC](https://discourse.julialang.org/t/going-backward-in-random-number-generation/24257 "2019-05-15T20:36:53Z")\
**Posts on this page:** 18\
**Page:** 1

<div class="post-metadata">

**Author:** ![rveltz](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rveltz/32/2707_2.png) [@rveltz](https://discourse.julialang.org/u/rveltz)\
**Post date:** [May 15, 2019, 8:36pm UTC](https://discourse.julialang.org/t/going-backward-in-random-number-generation/24257/1 "2019-05-15T20:36:53Z")

</div>

Hi,

I have a function `sample()` that generate trajectories from random numbers. Before calling this function, I would do

```julia
Random.seed!(1)

```

My problem is that I call `rand()` one more time than necessary in `sample()` given the way my algorithm is implemented. This is part of my package [PiecewiseDeterministicMarkovProcesses.jl](https://github.com/rveltz/PiecewiseDeterministicMarkovProcesses.jl).

Hence, if I call `rand()` after my function `sample()`, I missed a random number in the sequence of calls to `rand()`.

My question is then: how can I go back once in the random generator?

I found empirically that this works, but it is a bit hacky:

```julia
using Random
Random.seed!(1)
rand() #0.23603334566204692
# this following call is erroneous, I want to remove it from the stack of calls
rand() #0.34651701419196046
Random.GLOBAL_RNG.idxF-=1
rand() # gives 0.34651701419196046 as expected

```

Thank you for your help,

Best regards

---

<div class="post-metadata">

**Author:** ![Henrique\_Becker](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/henrique_becker/32/15443_2.png) [@Henrique\_Becker](https://discourse.julialang.org/u/Henrique_Becker)\
**Post date:** [May 15, 2019, 8:50pm UTC](https://discourse.julialang.org/t/going-backward-in-random-number-generation/24257/2 "2019-05-15T20:50:25Z")

</div>

I am not sure if I understand, why would be a problem to miss a random number of the sequence? And why the solution is not to remove the extra and unnecessary call?

---

<div class="post-metadata">

**Author:** ![greg\_plowman](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/greg_plowman/32/8100_2.png) [@greg\_plowman](https://discourse.julialang.org/u/greg_plowman)\
**Post date:** [May 15, 2019, 8:52pm UTC](https://discourse.julialang.org/t/going-backward-in-random-number-generation/24257/3 "2019-05-15T20:52:16Z")

</div>

> [@rveltz](#):
>
> I missed a random number in the sequence of calls to `rand()` .

Why does this matter?

---

<div class="post-metadata">

**Author:** ![rveltz](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rveltz/32/2707_2.png) [@rveltz](https://discourse.julialang.org/u/rveltz)\
**Post date:** [May 15, 2019, 8:52pm UTC](https://discourse.julialang.org/t/going-backward-in-random-number-generation/24257/4 "2019-05-15T20:52:42Z")

</div>

Mostly for debugging purposes

---

<div class="post-metadata">

**Author:** ![tkluck](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tkluck/32/15769_2.png) [@tkluck](https://discourse.julialang.org/u/tkluck)\
**Post date:** [May 15, 2019, 9:52pm UTC](https://discourse.julialang.org/t/going-backward-in-random-number-generation/24257/5 "2019-05-15T21:52:44Z")

</div>

@rveltz I hope you’re not getting the feeling people are dismissive. As a reader, here’s what I got from this thread:

> [@rveltz](#):
>
> I found empirically that this works, but it is a bit hacky:

> [@greg\_plowman](#):
>
> Why does this matter?

> [@rveltz](#):
>
> Mostly for debugging purposes

Naively, a hacky solution should be good enough for debugging purposes. After all, at some point you found the bug, you fixed it, and you remove the debugging hack. So maybe you can be more specific?

Another reason for asking that is that being able to go backward in a random number generator arguably defeats its purpose, depending on what other constraints you have. But we have no way of weighing that without a description of those other constraints!

Can you give us something to go on?

---

<div class="post-metadata">

**Author:** ![greg\_plowman](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/greg_plowman/32/8100_2.png) [@greg\_plowman](https://discourse.julialang.org/u/greg_plowman)\
**Post date:** [May 16, 2019, 4:48am UTC](https://discourse.julialang.org/t/going-backward-in-random-number-generation/24257/6 "2019-05-16T04:48:31Z")

</div>

The PCG family of RNGs has an `advance!` function which can be used with a negative argument to backtrack. See package [RandomNumbers](https://github.com/sunoru/RandomNumbers.jl).

```julia
Julia-1.1.0> using RandomNumbers.PCG

Julia-1.1.0> seed = 1234567
1234567

Julia-1.1.0> rng = PCGStateOneseq(UInt64, seed)
PCGStateOneseq{UInt128,Val{:XSH_RS},UInt64}(0xa10d40ffc2b1e573e589b22b2450d1fd)

Julia-1.1.0> rand(rng)
0.5716257379273757

Julia-1.1.0> rand(rng)
0.9945058856417783

Julia-1.1.0> advance!(rng, -1)
PCGStateOneseq{UInt128,Val{:XSH_RS},UInt64}(0xa84bc492b096c6e1ef3582ace3953880)

Julia-1.1.0> rand(rng)
0.9945058856417783

```

---

<div class="post-metadata">

**Author:** ![rveltz](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rveltz/32/2707_2.png) [@rveltz](https://discourse.julialang.org/u/rveltz)\
**Post date:** [May 16, 2019, 6:12am UTC](https://discourse.julialang.org/t/going-backward-in-random-number-generation/24257/7 "2019-05-16T06:12:51Z")

</div>

I was expected something like the answer of @greg_plowman. Indeed, I did not dive into the `rand` implementation, so I am not sure my hacky code does the thing I want

---

<div class="post-metadata">

**Author:** ![c42f](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/c42f/32/52842_2.png) [@c42f](https://discourse.julialang.org/u/c42f)\
**Post date:** [May 16, 2019, 7:55am UTC](https://discourse.julialang.org/t/going-backward-in-random-number-generation/24257/8 "2019-05-16T07:55:43Z")

</div>

PRNGS don’t generally have a way to go backward in the sequence. Some are designed with an `O(1)` method for skipping to a point in the sequence, but that’s a rarity as far as I know.

What you’ve found with `GLOBAL_RNG.idxF` is an interesting implementation detail of the way that the `MersenneTwister` is optimized for speed: it generates random numbers in batches and stores the batch in a cache. When you get to the batch size, `idxF` will wrap around to 1, and your trick above will result in an index out of bounds error. It would be possible to design the cache for any PRNG to always allow going back in the sequence by up to a given number of slots but it’s a pretty unusual requirement.

---

<div class="post-metadata">

**Author:** ![rveltz](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rveltz/32/2707_2.png) [@rveltz](https://discourse.julialang.org/u/rveltz)\
**Post date:** [May 16, 2019, 8:19am UTC](https://discourse.julialang.org/t/going-backward-in-random-number-generation/24257/9 "2019-05-16T08:19:34Z")

</div>

Thank you a lot for this clarification!

---

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [May 16, 2019, 9:47am UTC](https://discourse.julialang.org/t/going-backward-in-random-number-generation/24257/10 "2019-05-16T09:47:08Z")

</div>

> [@rveltz](#):
>
> Mostly for debugging purposes

I think a clean way for generic RNGs may be a wrapper type

```julia
struct BackwardRandom{T,R}
    buffer::Vector{T}
    rng::R
end

```

that implements `rand` by calling it on `rng` and keeping the last `N` draws in `buffer`, which you could then query, or use in place of calling `rand` on `rng` the desired number of times.

---

<div class="post-metadata">

**Author:** ![rfourquet](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rfourquet/32/3610_2.png) [@rfourquet](https://discourse.julialang.org/u/rfourquet)\
**Post date:** [May 16, 2019, 1:22pm UTC](https://discourse.julialang.org/t/going-backward-in-random-number-generation/24257/11 "2019-05-16T13:22:33Z")

</div>

I don’t know if this applies for your needs, but you can `copy` the global RNG:

```julia
r = copy(Random.GLOBAL_RNG)
rand() # 0.29854174909400233
copy!(Random.GLOBAL_RNG, r)
rand() # 0.29854174909400233

```

---

<div class="post-metadata">

**Author:** ![rveltz](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rveltz/32/2707_2.png) [@rveltz](https://discourse.julialang.org/u/rveltz)\
**Post date:** [May 16, 2019, 6:21pm UTC](https://discourse.julialang.org/t/going-backward-in-random-number-generation/24257/12 "2019-05-16T18:21:12Z")

</div>

That’s interesting!

---

<div class="post-metadata">

**Author:** ![jerlich](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jerlich/32/5205_2.png) [@jerlich](https://discourse.julialang.org/u/jerlich)\
**Post date:** [May 17, 2019, 10:41am UTC](https://discourse.julialang.org/t/going-backward-in-random-number-generation/24257/13 "2019-05-17T10:41:37Z")

</div>

I think it is better to not use the global random generator. That way you don’t have to worry about another process calling rand and messing up your sequence.

```julia
julia> rng = MersenneTwister(1234);

julia> rand!(rng, zeros(5))
5-element Array{Float64,1}:
 0.5908446386657102
 0.7667970365022592
 0.5662374165061859
 0.4600853424625171
 0.7940257103317943

```

---

<div class="post-metadata">

**Author:** ![robertfeldt](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/robertfeldt/32/239_2.png) [@robertfeldt](https://discourse.julialang.org/u/robertfeldt)\
**Post date:** [May 20, 2019, 12:28pm UTC](https://discourse.julialang.org/t/going-backward-in-random-number-generation/24257/14 "2019-05-20T12:28:38Z")

</div>

I’m probably late to the party here but I did do a very similar thing as proposed by Tamas here by implementing a wrapperRNG for the RandomNumers.jl package. Instead of saving the sequence itself I saved the current state in “snapshots” so that you can then “jump” back in the sequence by finding the closest snapshot pre the point you want to move to and then advance it. If you use one of the RNG’s in the package that have small state this can be both mem and cpu efficient IMHO.

> **[GitHub - JuliaRandom/RandomNumbers.jl: Random Number Generators for the Julia...](https://github.com/JuliaRandom/RandomNumbers.jl)**
>
> Random Number Generators for the Julia Language. Contribute to JuliaRandom/RandomNumbers.jl development by creating an account on GitHub.

---

<div class="post-metadata">

**Author:** ![c42f](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/c42f/32/52842_2.png) [@c42f](https://discourse.julialang.org/u/c42f)\
**Post date:** [May 21, 2019, 1:08am UTC](https://discourse.julialang.org/t/going-backward-in-random-number-generation/24257/15 "2019-05-21T01:08:11Z")

</div>

This seems like it could be useful if you have to abandon a computation and want to redo part of it with the same sequence. With a small state it seems quite practical.

---

<div class="post-metadata">

**Author:** ![rfourquet](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rfourquet/32/3610_2.png) [@rfourquet](https://discourse.julialang.org/u/rfourquet)\
**Post date:** [May 21, 2019, 9:41am UTC](https://discourse.julialang.org/t/going-backward-in-random-number-generation/24257/16 "2019-05-21T09:41:24Z")

</div>

Another approach, for `MersenneTwister`, would be to “jump forward” (using `Future.randjump`) by a number of steps a bit less than the period. But given that `MersenneTwister` uses caches, this is not totally straightforward to implement (see e.g. [#25129](https://github.com/JuliaLang/julia/pull/25129)). Moreover, I didn’t succeed after trying few minutes, so I may be overlooking something (I’m not sure what the exact period is, I thought it was `2^19937-1`, but in the “dSFMT.h” file, it says a _multiple_ of this number…).

---

<div class="post-metadata">

**Author:** ![foobar\_lv2](https://avatars.discourse-cdn.com/v4/letter/f/ee59a6/32.png) [@foobar\_lv2](https://discourse.julialang.org/u/foobar_lv2)\
**Post date:** [May 21, 2019, 9:51am UTC](https://discourse.julialang.org/t/going-backward-in-random-number-generation/24257/17 "2019-05-21T09:51:08Z")

</div>

I really recommend just using a different PRNG if you want to go backwards or make snapshots. RandomNumbers.jl offers various alternatives.

---

<div class="post-metadata">

**Author:** ![ignace](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ignace/32/24275_2.png) [@ignace](https://discourse.julialang.org/u/ignace)\
**Post date:** [April 22, 2021, 11:49am UTC](https://discourse.julialang.org/t/going-backward-in-random-number-generation/24257/18 "2021-04-22T11:49:34Z")

</div>

Do you also have a trick out there if one wants to backtrack random numbers, more than 1 samples ago (possibly a large number of samples!)?

Thanks!