6

I'm working on an algorithm which needs to generate millions of numbers as fast as possible. Actually I found out that the rand() function of my algorithm takes 75% of the process time.

So I'm looking for something faster. And I don't need a big range at all. (I only need integer numbers below 1000)

Do you know something I could use ?

Thanks !

Edit :

I use this numbers for shuffling groups of less than 1000 entities.

I found out more about the "fast rand". And there is SSE version version which is even faster and generates 4 numbers at a time.

https://software.intel.com/en-us/articles/fast-random-number-generator-on-the-intel-pentiumr-4-processor/

8
  • 75% of 3 seconds isn't much. Usually, rand() is very fast. How long does your code take to run to create 1 million numbers? Commented Oct 7, 2014 at 13:42
  • 1
    Don't think of 75% as "slow". After all, even if it runs in a nanosecond, something will take 100% of the time. If the program mainly does nothing except generate random numbers, you would expect that to take up most of the time. However, if you want it to be faster, that does tell you where to look. Commented Oct 7, 2014 at 13:47
  • I wasn't saying that it was "slow" but that's probably where I should start if I want to improve my algorithm.
    – Kevin P
    Commented Oct 7, 2014 at 13:50
  • 1
    I always have to ask - did you get this from gprof? If so, don't believe it, because gprof ignores blocked time like I/O, as well as any time taken in non-pg-compiled libraries. If you are writing these numbers somewhere, that could well be the real time-taker. I use this method. Commented Oct 7, 2014 at 13:54
  • 1
    How "random" do your "random" numbers need to be? If you're on a Linux/glibc based system, your problem is that rand is actually implemented in terms of random, which is a rather high-quality (and therefore slow) PRNG. Lower-quality ones like a pure LCG should be much faster, but might have sufficiently bad statistical properties to make them unsuitable for your application. Commented Oct 7, 2014 at 15:18

4 Answers 4

8
static unsigned int g_seed;

// Used to seed the generator.           
inline void fast_srand(int seed) {
    g_seed = seed;
}

// Compute a pseudorandom integer.
// Output value in range [0, 32767]
inline int fast_rand(void) {
    g_seed = (214013*g_seed+2531011);
    return (g_seed>>16)&0x7FFF;
}
6
  • 2
    And where do you get it from that this is faster than the rand() implementation that Kevin's machine has? Commented Oct 7, 2014 at 13:58
  • 1
    I just tested it : takes 1.2s for 100 millions numbers, rand() takes 5s. I'll have to check if it's truly random but thanks !
    – Kevin P
    Commented Oct 7, 2014 at 14:06
  • It is a bit more faster than rand(). There are some corner cases but not so big deal. @JensGustedt and my pleasure kevinP
    – Asis
    Commented Oct 7, 2014 at 14:16
  • It resulted in a 35% decrease of time on my algorithm with similar results. I guess I'll combine your fastrand with @Aaron Digulla answer to improve it a little more.
    – Kevin P
    Commented Oct 7, 2014 at 14:22
  • @KevinP: This is a simple Linear Congruential Generator using the same parameters as the Microsoft rand() implementation. It's fast but not high-quality randomness. Commented Oct 7, 2014 at 14:48
3

Mersenne Twister algorithm is a quite fast yet balanced pseudo-random number generator.

Here is a sample implementation : http://fmg-www.cs.ucla.edu/geoff/mtwist.html

3
  • In most systems, rand() is a pseudo-random number generator. I'm wondering how slow his implementation actually is. Commented Oct 7, 2014 at 13:43
  • I guess they're not changing the default implementation because it would break pre-seeded softwares...
    – blue112
    Commented Oct 7, 2014 at 13:46
  • modern mersenne Twisters are really not that fast compared to their equally ranking alternatives. Commented Jan 2, 2019 at 20:38
3

If you are using Intel Ivy Bridge processor, you could very well offload random number generation to hardware using RDRAND instruction.

This stack overflow article talks about the throughput of RDRAND.

You could also identify if the processor supports RDRAND and use hardware offload or else fall back to software implementation.

0

In most systems, rand() is a pseudo-random number generator. So the code should be just a few shift + bit-OR operations and able to produce millions of numbers per second on a typical PC. You don't say what you get and what your hardware is or which C library you're using, so it's hard to see why your implementation is "slow".

Maybe you can try to reuse bits: Take the lowest ten bits (= 1024 values), modulo 1000 to get the number range you want. Then shift and when you run out of bits, call rand() again for more bits.

2
  • 3
    I'm not sure if this is necessarily a good idea, re-using bits may not guarantee the period of the most likely linear congruent method he is using. Commented Oct 7, 2014 at 13:51
  • 1
    Modulo operations are not a good idea if you're looking for high performance. Commented Oct 3, 2018 at 20:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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