0

This is a continuation of another question about efficiently getting quasi-random numbers.

I need to get N unique quasi-random numbers, bias/distribution quality is no big deal. Can I get them more CPU/time-efficiently than using N calls to rand() or /dev/random etc? Maybe using some math/bitwise manipulations on few random numbers or something like that. Or using precomputed tables or...

N can be quite big like 10000 or 1000000.

Thanks.

Community
  • 1
  • 1
pati
  • 135
  • 1
  • 7
  • 1
    You should learn to benchmark your code and, for example, see if 1000000 `rand()` calls are fast enough. It's hard to get much faster than the Microsoft implementation of `rand()`. See [here](http://stackoverflow.com/questions/1026327/what-common-algorithms-are-used-for-cs-rand). – President James K. Polk Apr 08 '12 at 18:46
  • Clarification: N calls to Rand() is not going to give you N unique numbers. Are you talking about N unique numbers, or simply N "random" numbers? – Mathias Apr 08 '12 at 18:52
  • Also, I think the question as stated now is fuzzy. You can use marginally faster or slower RNGenerators, but that shouldn't change the overall results much. And what do you mean by "bias/distribution quality is no big deal"? Just returning [1 .. N] will give you N unique numbers as fast as possible, and it's a perfectly valid sequence a RNG could produce. – Mathias Apr 08 '12 at 18:57
  • Sorry, I meant N unique numbers. – pati Apr 08 '12 at 18:59
  • Yes, Mathias, after some research I'm starting to see that RNGs can be very simple and a good manipulation routine of some random number is a RNG itself. – pati Apr 08 '12 at 19:14
  • You need to establish that you actually have a problem before you start searching for solutions. Chances are the built in rand() is perfectly satisfactory, and if it's not, there are very fast (though poor quality) PRNGs out there to use. – Nick Johnson Apr 09 '12 at 05:00

1 Answers1

0

I found simething like this here:

m_w = <choose-initializer>;    /* must not be zero */
m_z = <choose-initializer>;    /* must not be zero */

uint get_random()
{
    m_z = 36969 * (m_z & 65535) + (m_z >> 16);
    m_w = 18000 * (m_w & 65535) + (m_w >> 16);
    return (m_z << 16) + m_w;  /* 32-bit result */
}
dexametason
  • 1,133
  • 7
  • 16