feat: Use 30 bits of R's RNG

[krlmlr]

Closes #782.

[aviator-app]

Current Aviator status

Aviator will automatically update this comment as the status of the PR changes.
Comment /aviator refresh to force Aviator to re-examine your PR (or learn about other /aviator commands).

This PR was merged using Aviator.

---

See the real-time status of this PR on the Aviator webapp.

Use the Aviator Chrome Extension to see the status of your PR within GitHub.

[szhorvat]

I am confused about why this is not causing mass test failures. This changes the behaviour of the RNG. For the same seed, it should return a different sequence of integers.

I just checked in rrandom.c that the only sampler that we don't rely directly on R for is get_int.

rigraph/src/rrandom.c

Lines 101 to 116 in b806ec2

	static igraph_rng_type_t igraph_rng_R_type = {
	/* name= */ "GNU R",
	/* bits = */ 30, // tested by test-rng.R, #782
	/* init= */ igraph_rng_R_init,
	/* destroy= */ igraph_rng_R_destroy,
	/* seed= */ igraph_rng_R_seed,
	/* get= */ igraph_rng_R_get,
	/* get_int= */ NULL,
	/* get_real= */ igraph_rng_R_get_real,
	/* get_norm= */ igraph_rng_R_get_norm,
	/* get_geom= */ igraph_rng_R_get_geom,
	/* get_binom= */ igraph_rng_R_get_binom,
	/* get_exp= */ igraph_rng_R_get_exp,
	/* get_gamma= */ igraph_rng_R_get_gamma,
	/* get_pois= */ igraph_rng_R_get_pois,
	};

Nevertheless, get_int is used by many functions, e.g. barabasi_game(). I just checked that sample_pa(10) continues to return the same result before and after this PR.

Is something wrong? Do you understand why nothing changed, @ntamas ?

All this said, I strongly recommend running revdepchecks again after this PR, @krlmlr The output of some randomized functions should change (and that's fine, but may break some other packages' tests)

[szhorvat]

sample_pa() was the wrong function to test as it only uses RNG_INTEGER() in specific situations. But sample_tree() always uses it, yet it still continues to return the same result. That does not look right.

[krlmlr]

We did not change igraph_rng_R_get_real() .

[krlmlr]

Confirming the same results for yesterday's version and the current main branch.

set.seed(20240108)
igraph::sample_tree(20)
#> IGRAPH 596b969 U--- 20 19 -- 
#> + edges from 596b969:
#>  [1] 14--16 13--16  5--13  8--13  8--10 10--11  5-- 6  6--15  9--15  9--12
#> [11] 12--18  7--16 12--17  4--17  2--11  2--20  3--18  1--16 15--19

^{Created on 2024-01-08 with reprex v2.0.2}

It looks legit, though. In sample_tree() we draw random numbers for very small integer ranges. These are derived from the most significant bits in the number returned by the integer RNG. The MSBs stay the same (and are very very unlikely to change) for the same initial seed, though, because we get them by multiplying a real in [0; 1) with 2^31 - 1 (old, slightly wrong) or 2^30 (new).

[krlmlr]

Anyway, running revdepchecks is a good idea here.

[szhorvat]

Yes, I also looked in more detail and I think I see why this is happening.

Nevertheless, there should be a note in the changelog that randomized functions may not return the same result for the same seed.