ti.random(ti.i32) always returns number of the same parity in the same thread

[AmesingFlank]

Consider this program which generates 100 random ints and checks their parity (even or odd)

import taichi as ti
x = [0,0]

for i in range(100):
    ti.init(ti.cuda, random_seed=i)

    @ti.kernel
    def k() -> int:
        return ti.random(ti.i32) % 2 
    p = k()
    x[p] += 1

print(x) 

This ends up printing

[100, 0]

More generally, I noticed that, for a given thread, regardless of the random seed, the 1st random int it generates always has the same parity.

[lucifer1004]

Ideas:

• Make a separate package and implement multiple RNGs with Taichi.

Resources:

• RandomNumbers.jl
• Mersenne Twister
• Generating multiple disjoint streams of pseudorandom number sequences
• TinyMT
• cuRAND API
• MTGP paper, which is used by cuRAND

[lin-hitonami]

@lucifer1004 Thanks! Would you like to contribute the RNGs to Taichi? Maybe we can let them be an official module (maybe ti.math.random?) in Taichi.

[lin-hitonami]

We need to expose the random states of each thread to Python first if we want to implement RNGs outside the Taichi runtime.

taichi/taichi/runtime/llvm/runtime_module/runtime.cpp

Lines 526 to 532 in 800ff2b

	struct RandState {
	u32 x;
	u32 y;
	u32 z;
	u32 w;
	i32 lock;
	};

taichi/taichi/runtime/llvm/runtime_module/runtime.cpp

Line 568 in 800ff2b

RandState *rand_states;

[lucifer1004]

I would love to contribute, but I have higher priorities at the moment. So if this needs to be implemented very soon, I may not be able to help.

[lin-hitonami]

@lucifer1004 Thank you very much! This is an old problem, and this doesn't need to be implemented very soon. Please contribute whenever is convenient for you!

[lucifer1004]

@lin-hitonami @yuanming-hu

As for this specific issue, the root cause is

taichi/taichi/runtime/llvm/llvm_runtime_executor.cpp

Line 584 in b48baeb

int starting_rand_state = config_->random_seed * 1048576;

Then the x part of the initial random state is always an even number.

taichi/taichi/runtime/llvm/runtime_module/runtime.cpp

Lines 534 to 540 in b48baeb

	void initialize_rand_state(RandState *state, u32 i) {
	state->x = 123456789 * i * 1000000007;
	state->y = 362436069;
	state->z = 521288629;
	state->w = 88675123;
	state->lock = 0;
	}

If we change 1048576 to 1048577, for example, the output of @AmesingFlank 's code would be [51, 49].

[bobcao3]

We can move it to 1048391 which is a prime?

[lin-hitonami]

@lucifer1004 @bobcao3 Thanks! Let me make a quick fix.

[lin-hitonami]

BTW @bobcao3 it seems that the SPIRV-based backends don't use this random seed?

[bobcao3]

BTW @bobcao3 it seems that the SPIRV-based backends don't use this random seed?

They don't (and they uses a different algorithm), so this doesn't apply there.

[lucifer1004]

Shall we close this issue and open a new one to track the RNG implementations? @lin-hitonami

[lin-hitonami]

Good idea! Please open a new one!