Splitmix64 O(1) jump forward (and back) code

[Anthony]

This might be obvious to everyone here, but while toying around with this in rust I noticed that the optimizing compiler was able to come up with a jump function all on its own (this is the only RNG I've tested that it was able to do that for).  I hadn't seen an O(1) jump function posted publicly, and I thought it was interesting enough (particularly because the optimizing compiler saw it before I did), so I figured I'd post it here just to share.  

Yeah, it's kinda obvious in hindsight, but whatever. :D

Code is in Rust, but it's easy to follow if you're familiar with basically any programming language:

/* Based on the following C code:

static uint64_t state; 

uint64_t next() 

{

    uint64_t z = (state += 0x9e3779b97f4a7c15);    

    z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9;

    z = (z ^ (z >> 27)) * 0x94d049bb133111eb;

    return z ^ (z >> 31);

}

*/

const GOLDEN_GAMMA: u64 = 0x9e_37_79_b9_7f_4a_7c_15;

#[derive(Clone)]

pub struct Random

{

    state: u64

}

impl Random

{

    #[inline(always)]

    pub const fn default_seed() -> Self

    {                            

        Self {state: 0xa7_40_7f_7a ^ 0x7d_f0_3a_f4_f3_eb_c3_f9}

    }

    #[inline(always)]

    pub const fn custom_seed(seed: u64) -> Self

    {                               

        Self {state: seed}

    }

    pub fn next(&mut self) -> u64        

    {

        self.state = self.state.wrapping_add(GOLDEN_GAMMA); 

                

        let mut z = self.state;                      

        z = (z ^ (z >> 30)).wrapping_mul(0xbf_58_47_6d_1c_e4_e5_b9);            

        z = (z ^ (z >> 27)).wrapping_mul(0x94_d0_49_bb_13_31_11_eb);                      

        z ^ (z >> 31)        

    }

    #[inline(always)]

    pub fn jump_forward(&mut self, n: u64)

    {

        self.state = self.state.wrapping_add(GOLDEN_GAMMA.wrapping_mul(n));

    }

    #[inline(always)]

    pub fn jump_back(&mut self, n: u64)

    {

        self.state = self.state.wrapping_sub(GOLDEN_GAMMA.wrapping_mul(n));

    }

}

[Sebastiano Vigna]

> On 23 Feb 2020, at 19:43, Anthony <surma....@gmail.com> wrote:
>
> This might be obvious to everyone here, but while toying around with this in rust I noticed that the optimizing compiler was able to come up with a jump function all on its own (this is the only RNG I've tested that it was able to do that for). I hadn't seen an O(1) jump function posted publicly, and I thought it was interesting enough (particularly because the optimizing compiler saw it before I did), so I figured I'd post it here just to share.

Yes, the next-state function is just an add, so you just multiply the constant by the number of steps. It is pretty useless because the state is too small.

In fact, on AVX2 architecture if you use this generator in a loop the compiler will vectorize it as it understand it can advance in parallel multiple instances.

Ciao,

seba

[Chris Rutz]

In fact, on AVX2 architecture if you use this generator in a loop the compiler will vectorize it as it understand it can advance in parallel multiple instances.

I added a new topic which demonstrates this and its performance... which opens the possibility of a new larger state PRNG being developed that will auto-vectorize.

I have tried to prod Lehmer128 to do this, but have not yet succeeded.