# RandomInteger: speed with long lists

I noticed an interesting effect with RandomInteger when looking at the time to create 10^8 random integers. The following code lines all take about 0.5 seconds on a i7 Windows 64bit Laptop:

AbsoluteTiming[RandomInteger[{1, 2^15}, 100000000];]
AbsoluteTiming[RandomInteger[{0, 2^20 - 1}, 100000000];]
AbsoluteTiming[RandomInteger[{-10, 2^20 - 11}, 100000000];]
AbsoluteTiming[RandomInteger[{1, 2^20}, 100000000];]


With one little change the speed drops by a factor of ~3 using this codes:

AbsoluteTiming[RandomInteger[{0, 2^20}, 100000000];]
AbsoluteTiming[RandomInteger[{0, 2^15}, 100000000];]


RandomReal does not show this behaviour. It is also not related to packed arrays: I checked that.

Can someone confirm the above shown (other Mathematica version or other plattform (Linux)? Does anyone have a clue why that happens?

• I have windows too, but I would expect the same on other platforms. – Coolwater Apr 30 '16 at 19:24
• Noteworthy is also the fact that RepeatedTiming[RandomInteger[{0, 2^15}, 100000000];] is slower, but RepeatedTiming[RandomInteger[{0, 2^15 - 1}, 100000000];] is fast... It perhaps has something to do with the data types selected internally by the RNG depending on the range over which the numbers are requested, but I don't know for sure. – MarcoB Apr 30 '16 at 20:38
• I get a factor of 2 to 2.5 depending on which variant I try. A factor of 2 is easy to explain: the numbers are generated as binary bit strings, and when the range is just past a power of 2, roughly half the candidates exceed and must be discarded. With reals this is not an issue (random bits are generated to fill the mantissa so we have a value between 0 and 1, then the thing gets scaled to fit the actual range requested). – Daniel Lichtblau Apr 30 '16 at 21:26
• @Daniel That makes good sense. I wonder if you would care to pour your comment in an answer, since it pretty much answers the question anyway. – MarcoB Apr 30 '16 at 22:13
• @Daniel I thought of that too. However 2^15 an 2^20 perform at the same Speed. When you take the range {0,2^20-1} it is a factor 2.6 faster. In my opinion that is not explained by this hypothesis as 2^20 results in way longer numbers. Or do I get it wrong? – Eisbär May 1 '16 at 11:04

Slightly expanding my comment. It is a partial answer, explaining most but not all of the observed timing increase. First I show some representative timings. Note that I use 2^16-1 and 2^21-1 below, for reasons that will be explained.

AbsoluteTiming[RandomInteger[2^16 - 1, 100000000];]
AbsoluteTiming[RandomInteger[2^21 - 1, 100000000];]

(* Out[37]= {1.0384, Null}

Out[38]= {1.27375, Null} *)

AbsoluteTiming[RandomInteger[2^15, 100000000];]
AbsoluteTiming[RandomInteger[2^20, 100000000];]

(* Out[39]= {2.44224, Null}

Out[40]= {2.91487, Null} *)


Generating random integers between 0 and 2^15 means creating randoms, uniformly distributed, almost all of which are 16 or fewer bits (except we have to allow for 2^15, which requires 16 bits to represent in binary). All underlying methods in the Mathematica kernel generate some batch of bits at a time. For this case, 16 get strung together. The examples above that generate between 0 and either 2^16-1 or 2^15 both use sets of 16 bits. The latter case will discard all values larger than 2^15, which is to say, around half the time a generated value gets tossed. This accounts for a factor of 2 or so in the speed differences. The total differences above are more like a factor of 2.4, so this is clearly not the full explanation.

If we work with 2^16 - 2 as upper bound the timing gets slightly slower than for 2^16-1. My guess, not looking at the code, is that the exact power-of-2 bits special case is fast because no check for exclusion is performed. If we look at cases where it must be performed but essentially never discards, the respective timing ratios get closer to 2.

AbsoluteTiming[RandomInteger[2^16 - 2, 100000000];]
AbsoluteTiming[RandomInteger[2^21 - 2, 100000000];]

(* Out[41]= {1.18563, Null}

Out[42]= {1.32423, Null} *)


The ratios are still above 2. My guess at this point is that there is some modest inefficiency in the way new sets are generated and merged to cover for the values discarded. Specifically, it might be the case that exactly the number discarded get generated, causing, in the worst case, another half or so tof the new set to be tossed, so repetitions get us into a log(n) loop where n is the number of values being generated. It could be faster to generate roughly twice as many as needed to account for the approximate size of the set that will be discarded. All this is speculation; I last had dealings with that code I think in the 1990's. In particular I do not recall how the generate-and-discard process decided on how many to generate at each step. So my speculation might be on target if it is generating exactly the number needed, or if it is generating some fixed fraction beyond the estimated number required to fill the customer's order, so to speak.