-1
$\begingroup$

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?
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Paul Uszak Sep 26 '17 at 13:24
  • $\begingroup$ 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? $\endgroup$ – Paul Uszak Sep 26 '17 at 13:26
  • 2
    $\begingroup$ Why not empirically test the various methods? $\endgroup$ – Yuval Filmus Sep 26 '17 at 13:36
  • $\begingroup$ @PaulUszak Let's assume the RNG need not be cryptographically secure. What is 'naff'? $\endgroup$ – LBogaardt Sep 26 '17 at 13:38
  • 1
    $\begingroup$ 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. $\endgroup$ – Yves Daoust Sep 27 '17 at 6:14
1
$\begingroup$

The answer is completely computer-architecture and random-generator -dependent. All you can do is to benchmark the different approaches after making them concrete.

$\endgroup$
  • $\begingroup$ A few years ago, IBM had published a linear congruential random number generator for their high end POWER cpus that ran at one cycle per number throughput. It requires an FPU with fused multiply-add, so it should be possible to adapt it to modern Intel processors. $\endgroup$ – gnasher729 Sep 26 '17 at 21:01
  • $\begingroup$ @gnasher729: Intel processors even have a built-in nondeterministic RNG nowadays. $\endgroup$ – Yves Daoust Sep 27 '17 at 6:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.