Some quick notes:

* In issue 33144, we achieved a significant speed-up for _randbelow_with_getrandbits() by removing a single test.  The code for that method is thin and almost any additional logic will slow it down.

* The attached PR (now closed) causes a performance regression.  Shuffling a thousand element list regressed from 505 usec per loop to 576 usec per loop.

* We only promise that the output of random() will be reproducible across versions; however, we should have an aversion to changing the output of the other methods unless it is really necessary (because it may change the result of simulations or random selections which will cause some consternation for some end-users).  For seed(8675309), the result of "[randrange(1024) for i in range(10)]" changes under the PR from [823, 438, 575, 465, 718, 186, 25, 1015, 654, 988] to [411, 219, 522, 961, 679, 516, 881, 919, 287, 882].  This is allowed but not desireable.

When I get a chance, I'll take a closer look at Mark's suggestion.