0

For a project I am currently working on I need to generate a large amount of pseudorandom floating-point numbers, between 0 and 1, in the range of thousands to hundreds of thousands as fast as possible.

What would the best method for this be?

The options I can think of currently are:

C rand(), Quite fast from my experience.

C++11 Random, rather slow but better random numbers from what I have heard.

A custom hash function such as:

u_int32_t seed = 1;
seed = (seed ^ 61) ^ (seed >> 16);
seed = seed + (seed << 3);
seed = seed ^ (seed >> 4);
seed = seed * 0x27d4eb2d;
seed = seed ^ (seed >> 15);
uint8_t a = seed&0xff;
float n = (((float)a)/UINT8_MAX);

Which is quite fast.

Speed test for the above:

Generating 100000 Random Numbers
C rand(): 1.72661
C++ random: 6.60626
hash random: 1.034

Are there any faster options? The only thing I can think of are some quicker hash or somehow doing it on the GPU via a compute shader, but I don't have much experience in that.

Any help is most appreciated.

Edit: Just to clarify, the times above are in milliseconds.

Dragonpeak
  • 11
  • 3
  • 3
    It depends on the quality of the randomness you need. `rand` is fast, but C++'s random features have distributions with statistical requirements. So you first need to decide, for your application, what you need. – François Andrieux Jun 23 '20 at 12:36
  • Looks like [this question](https://stackoverflow.com/questions/1046714/what-is-a-good-random-number-generator-for-a-game) – Dani Cuesta Jun 23 '20 at 12:36
  • I suppose that if you get your hands on a quantum computer you could get a bit more performance; otherwise those are the only options. I'm fairly certain that there are no hidden super-fast random number generators in C++ that only a few privileged C++ gurus know about. C++11 random generator, and C library's `rand()` are the only options. On Linux you could also open `/dev/urandom`, and read random bytes from it, and somehow fashion them into floating point values, but I doubt that this would be faster. – Sam Varshavchik Jun 23 '20 at 12:37
  • Just an idea and if you have the memory. If it needs to be fast, and pseudo random is good enough, could you write a program that runs once that creates a c array of 100,000 numbers as static data for your actual program? You could randomly start at a different index if you wanted to throw in some variability. – franji1 Jun 23 '20 at 12:41
  • 5
    Are you running an optimized build? Please post the compiler options you're using when you built your application. – PaulMcKenzie Jun 23 '20 at 12:50
  • 2
    What are the numbers in your speed test? I can generate `100'000` random numbers in less than 10 ms on my desktop machine with C++11 ``. – Evg Jun 23 '20 at 12:50
  • 1
    I think there should be a general FAQ about questions concerning C++ and speed. We need compiler options used, compiler used, etc. Just posting final numbers is not enough. – PaulMcKenzie Jun 23 '20 at 12:54
  • 4
    Your numbers are suspiciously low. Modern processors are typically able to generate pseudo-random numbers at rates over 1e8 per second. What is your compiler and optimization options? Also, if you want faster generation, you can employ multiple cores by using multiple threads. – Daniel Langr Jun 23 '20 at 13:05
  • If you put compqrative timings in your question, you'd better well show the code. – rubenvb Jun 23 '20 at 17:17

1 Answers1

1

What would the best method for this be?

Depends on other requirements besides the speed. Does the sequence need to be reproducible? Does the statistical quality of randomness matter? Does the distribution need to be uniform? What processor will you be using to execute the program?

If the speed is the only consideration, then the fastest solution is return 0.0, although the distribution is quite biased.

More seriously though, if statistical quality matters at least a little bit, enough that constant value is not sufficient, but still much less than speed, then the best way to choose the generator is to benchmark the known algorithms and pick the one that is fastest on your target system. <random> includes a few generators, some of which are quite simple and fast.

eerorika
  • 232,697
  • 12
  • 197
  • 326
  • Thanks, with a bit of testing I was able to get acceptable numbers in a good time using minstd_rand thanks for the advice. – Dragonpeak Jun 23 '20 at 17:12