1

I have an unsigned int storing a random number. I need to use this number to generate a series of "random like" numbers and have it generate those exact same numbers if this original random number turns up again.

i.e.

Random number: 123456789

First "random like number": 3

Second "random like number": 7

Third "random like number": 1

Fourth "random like number": 9

and so on.

Next time that random number comes around, the exact same numbers need to be generated from it.

The non random numbers can be duplicated and/or wrap around (to start again if whatever algorithm is used runs out of numbers, it can start again from the beginning). Just as long as each time, those same numbers are generated.

I realise this is exactly what rand() does (seeding with the random number), however I cannot use rand. So perhaps a more concise question would be how do I replicate a "mini" rand function (it doesn't have to be anything complicated, just so long as the numbers coming out look somewhat randomised).

Also I cannot use boost (unfortunately).

Any pointers/tips?

razlebe
  • 7,134
  • 6
  • 42
  • 57
Steve
  • 13
  • 3

4 Answers4

4

I don't know exactly why you cannot use rand itself but, if not, then you could just roll your own. Use your integer to seed a number then use the standard Xn+1 = a * Xn + c mod m.

The Wikipedia page for linear congruential method has some sample values for a, c and m.

Now LCM isn't the greatest random number generator in the world but, if you just want numbers that "look somewhat randomised", it should be sufficient.

As an example of an LCM algorithm, the following function, based on the Microsoft Visual/Quick C/C++ entry from that linked page above:

// LCM pseudo-random number generator.
// Outputs numbers from 0..32767 inclusive.
// With protection against identical sequences.
//   due to full 32-bit cycle but only returning 15 bits.

uint32_t myRand (void) {
    const static uint32_t a = 214013U;
    const static uint32_t c = 2531011U;
    // m is, of course, 2^32 since the values will wrap.

    static uint32_t seed = 1;
    seed = seed * a + c;
    return (seed >> 16) & 0x7FFF;
}

has a cycle time of the full range of 32-bit numbers but only returns certain bits of the seed each time, which reduces the appearance of identical sequences.

If you want a C++ class to do this so that all random number generators are independent of each other (as suggested by TomZ), you can use something like:

class myRand {
    public:
        myRand ();
        myRand (unsigned int newSeed);
        ~myRand ();
        void setSeed (unsigned int newSeed);
        unsigned int getSeed (void);
        unsigned int next (void);
    private:
        unsigned int seed;
        const static unsigned int a = 214013U;
        const static unsigned int c = 2531011U;
};

myRand::myRand () { seed = 1; }
myRand::myRand (unsigned int newSeed) { setSeed (newSeed); }
myRand::~myRand () { }
void myRand::setSeed (unsigned int newSeed) { seed = newSeed; }
unsigned int myRand::getSeed (void) { return seed; }
unsigned int myRand::next (void) {
    seed = (seed * a + c) & 0xffffffff;
    return (seed >> 16) & 0x7fff;
}

 

#include <iostream>

int main (void) {
    myRand r (5);

    std::cout << r.next() << "\n";          //    54
    std::cout << r.next() << "\n";          // 28693

    unsigned int saveSeed = r.getSeed();
    std::cout << r.next() << "\n";          // 12255
    std::cout << r.next() << "\n";          // 24449

    r.setSeed (saveSeed);
    std::cout << r.next() << "\n";          // 12255
    std::cout << r.next() << "\n";          // 24449

    return 0;
}
paxdiablo
  • 854,327
  • 234
  • 1,573
  • 1,953
  • Thanks very much, works perfectly. FYI, I can't use rand because something else (that I don't have control over) is using it, so I cannot guarantee whether that or my code will pick the next number and therefore may get different results each time the random number pops up. – Steve Nov 01 '11 at 10:42
  • With the use of a static seed variable, this is just as vulnerable as rand(). Instead, create a class that stores seed as a member and create an instance of the class whenever you need a RNG. It will be safer. – TomZ Nov 01 '11 at 15:31
  • @Tom, `rand` is only vulnerable in this case because someone else is calling it. That's incredibly unlikely if you roll your own `myRand` simply because no-one else will actually _know_ about it :-) However, I'll add a class version for completeness. – paxdiablo Nov 02 '11 at 04:22
3

You can pick any pseudo random number generation engine from <random> (or <tr1/random>) and fuel a uniform-integer distribution with it.

As long as you seed the engine with the same number, the resulting sequence of integers will be the same.

Example:

#include <random>

std::mt19937 rng;  // everyone's favourite engine: fast, long period
std::uniform_int_distribution<uint32_t> uniformUINT32(0, 99);  // numbers in the range [0, 100)

int main()
{
  static const unsigned long int seed = 123;
  rng.seed(seed);

  int val;
  val = uniformUINT32(rng);  // a predictable random number (69)
  val = uniformUINT32(rng);  // ditto (71)
}
Kerrek SB
  • 464,522
  • 92
  • 875
  • 1,084
2

Put together a class implementing a Linear-Congruential Generator:

http://en.wikipedia.org/wiki/Linear_congruential_generator

You can look up good values for A and C, and use 2^32 as M (the modulus) Example from Numerical Recipes: A = 1664525, C = 1013904223

As the article states, using 2^32 as the modulus is 'free' on a 32bit word size.

This is the same algorithm that most versions of rand() use.

Be aware that it is not secure.

The seed value is x. Using the same seed will generate the same sequence.

TomZ
  • 777
  • 1
  • 7
  • 12
0

For your case you could use Pseudo Random Number Generator (suitable for doing some quick fancy stuff but not for security/scientific related areas)

Rn = Rn * 1664525 + 1013904223

Datatype of Rn is uint32_t for supporting type wraparound. Initial value of Rn act as a seed.

SridharKritha
  • 8,481
  • 2
  • 52
  • 43