4 ms·

In which algorithms is the random number generation the bottleneck?

• berkut 5y ago
  Monte Carlo simulations - i.e. pathtracing... Generating well distributed random numbers with low overhead is quire important for that. It's not the bottleneck, but it is very important.
  • 0-_-0 5y ago
    In path tracing you don't want random numbers but low discrepancy sequences
    • berkut 5y ago
      And some of the ways (ignoring things like Sobol and Halton) of generating those are using random numbers :)
• fanf2 5y ago
  I was recently doing some randomised testing, and for some reason the software I was working with chose to use the getrandom() system call for every random number. This completely swamped the performance measurement I was trying to make, more than half the time wasted on random numbers. I switched to PCG with Lemire’s nearly divisionless modular reduction, and the performance numbers were sensible again.
• jeffbee 5y ago
  It can be significant if you are using a PRNG to make sampling decisions in a large data stream for example. I don't know about "the bottleneck" but if you can make a thing handle 1% more HTTP requests per second by doubling the speed of your PRNG, why wouldn't you?
• spacechild1 5y ago
  Noise generation in audio applications. At a sample rate of 44.1 kHz, a single noise generator has to produce 44100 random numbers per second. Now imagine you have dozens or hundreds of them. Luckily, you can get away with very cheap and simple algorithms.