# Comparing the Speed of Random Number Generation to Reading Data

Imagine you need $n$ random numbers from a Gaussian distribution with $\mu=0$ and $\sigma=1$. And you need to use each of these $n$ numbers $k$ times in various operations. Let's identify the numbers by $j \in 1 \ldots n$.

I see 3 methods of accessing these $n$ numbers during the operations:

1. Generate $n$ numbers once, store them in memory and read each one $k$ times.
2. Generate $n$ numbers once, store them on disk and read each one $k$ times.
3. Set the generator's seed to $j$ and generate the number $n * k$ times.

To determine the total run time, let's define the following terms:

• $T_{rand}$: the time to generate 1 random number
• $T_{seed}$: the time to set the seed
• $T_{w,mem}$: the time to store 1 number in memory
• $T_{w,dis}$: the time to store 1 number on disk
• $T_{s,mem}$: the time to search 1 number in memory
• $T_{s,dis}$: the time to search 1 number on disk
• $T_{r,mem}$: the time to read 1 number from memory
• $T_{r,dis}$: the time to read 1 number from disk

I believe the total run time for the three methods are:

1. $T_{total,1} = n * T_{rand}+ n * T_{w,mem} + n * k * T_{s,mem} + n * k * T_{r,mem}$
2. $T_{total,2} = n * T_{rand}+ n * T_{w,dis} + n * k * T_{s,dis} + n * k * T_{r,dis}$
3. $T_{total,3} = n * T_{seed}+ n * k * T_{rand}$

It would seem strangely coincidental to me if these three methods had similar speeds. I can imagine one of them vastly outperforms the others. This is were I would like some advice. If helpful, you may assume:

• Number $n$ is large; possible so large that storing $n$ values in memory is not possible.
• The randomness can be of low quality.
• Storing and reading from disk is done efficiently, e.g. with Hadoop.

My questions are:

• Do you see other methods to solve this problem?
• What other information do I need to determine which method is the fastest?
• Which aspects of the procedure will dominate in determining the total time it takes?
• Which method is the fastest? And, if possible, why?
• This question is incomplete in that: there are two types of random number generator. One is the plain type like random(). The second is a cryptographic ally secure one where future output cannot be predicted from past output. The latter is much harder so affects the question. Which do you want? – Paul Uszak Sep 26 '17 at 13:24
• Further, what's the point of a naff RNG? How naff also affects the question, so what are you trying to achieve? Can you simply alternate between 0.003 and -1.7777, because that's pretty naff too? – Paul Uszak Sep 26 '17 at 13:26
• Why not empirically test the various methods? – Yuval Filmus Sep 26 '17 at 13:36
• @PaulUszak Let's assume the RNG need not be cryptographically secure. What is 'naff'? – LBogaardt Sep 26 '17 at 13:38
• The point is quick concurrent accesses. But nothing stresses a hard disk more than concurrent accesses. You don't need them here, don't create a bottleneck. – Yves Daoust Sep 27 '17 at 6:14