What is this algorithm?

[jc211]

Below looks like some kind of pseudo random number generator. Any reference to the algorithm used here?

instant-ngp/src/testbed_nerf.cu

Line 449 in 892933b

idx = ((i+step*n_elements) * 56924617 + j * 19349663 + 96925573) % (NERF_GRIDSIZE()*NERF_GRIDSIZE()*NERF_GRIDSIZE());

[Tom94]

It's a linear congruential generator, which is a form of pseudo-random number generator. Its statistical properties are somewhat bad, but it is very efficient.

Here, we don't actually care much about its statistical properties. Rather, we care about its property of producing a permutation: this use case distributes the density grid update samples more-or-less uniformly over space (due to the pseudo-random nature), but ensures good coverage by never visiting a grid cell twice without having visited all other cells (due to the permutation property).

Feel free to re-open the issue if something is still unclear!