11

I need a good random number generator for a program I'm writing in C. It's a fractal flame generator, if you're interested. My images were coming out very grainy, even though I had success with the same algorithm in the past. The difference, I finally realized, was the random number generator I was using. Incredibly, it makes an ENORMOUS difference. I'm hoping that an even better random number generator might yield better results. The answer could come in the form of a code sample or a link to a pre-existing random number library. The most important requirements:

  • it should produce relatively high quality streams of random numbers
  • its period must be over ten billion
  • it should be fast enough and offer a good performance trade-off.
Void Star
  • 2,401
  • 4
  • 32
  • 57
  • http://en.wikipedia.org/wiki/Comparison_of_hardware_random_number_generators – JosephH Feb 15 '13 at 08:38
  • this question is valid IMHO. A bit too selft centered, but still valid in the requirements. – UmNyobe Feb 15 '13 at 08:42
  • 1
    @UmNyobe I nominated this question for reopening. I can't see why this is "not a real question". Not a good question? Maybe, but it's still a valid one. – Philipp Feb 15 '13 at 08:51
  • rand() is a pretty good random number generator in C. – SecurityMatt Feb 15 '13 at 09:10
  • 4
    Woah... I didn't expect such a negative response. I don't understand this community and it's somewhat rigid rules sometimes. In my opinion, this is a perfectly valid question. It has specific points that an answer must meet so it's not too general, it gives some context, so answers can be made specific to the situation, it isn't so specific that it won't ever be useful to anyone again. I know I'm not supposed to, but I'm beginning to take this a bit personally. It seems like I get attacked a lot on this site. – Void Star Feb 15 '13 at 09:16
  • "Questions asking us to recommend or find a book, tool, software library, tutorial or other off-site resource are off-topic for Stack Overflow as they tend to attract opinionated answers and spam." – Jim Balter Sep 13 '14 at 03:23

2 Answers2

13

This seems like a good use-case for the Mersenne Twister

  • It's faster than most standard implementations of rand()
  • It has a very long (2^19937 − 1) period
  • It has a pretty high quality - it passes most standardized randomness tests
  • It's public domain
Philipp
  • 67,764
  • 9
  • 118
  • 153
  • no, he is giving a candidate. +1 btw, never heard of Mersenne before – UmNyobe Feb 15 '13 at 08:40
  • Wow, this looks like a REALLY good random number generator. Thanks so much Philipp, I would never have found this on my own. – Void Star Feb 15 '13 at 09:18
  • 1
    I'm surprised that MT is faster than most implementations of `rand()`. Isn't `rand()` commonly an LCG, hence very fast but poor quality? – Steve Jessop Feb 15 '13 at 10:24
  • Considering the fact that this actually turned my non-working `rand()`-based algorithm into something I could actually work with, +1! – zeboidlund Nov 04 '13 at 05:58
8

If you are looking for a very fast, decent quality algorithm, you should think about xorshift128+ or xorshift1024*. They are almost as fast as LCGs (according to my comparison they are only 30% slower than simply inline LCG), having much better quality than LCG the same time.

You can find their code and comparison here: http://xorshift.di.unimi.it/

Piotr Jurkiewicz
  • 1,653
  • 21
  • 25
  • 1
    underappreciated answer here - I've used these in a couple projects so far and they work great, with such a simple implementation! – Void Star Nov 07 '16 at 16:55