C++ Program To Implement Park Miller Random Number Generation Algorithm

Numerous applications, including computer simulations, games, cryptography, statistical sampling, and more, require the ability to generate random numbers. Computers can only compute random numbers using mathematical formulas and cannot produce "true" random numbers themselves. These types of random numbers calculated by algorithms are called pseudo-random .

The Park-Miller algorithm , was published in 1988 by Stephen Park and Keith Miller . It is one well-liked method for producing pseudo-random numbers in computer programs. This algorithm is still very simple to code and effective even after over 30 years.

First, we select an arbitrary number called the 'seed' value. This seed can be any randomly chosen number and allows us to initialize the random number generation. From this starting seed, the Park-Miller formula calculates the next random number in sequence and then uses that number as a seed to calculate the next.

Here is the formula:

next_random_number = (16807 * current_seed) % 2^31 - 1

In the formula, 16807 and 2^31 - 1 (same as 2147483647) are constant prime numbers. Let's take an example:

Seed = 5

Next random number = (16807 * 5) % 2147483647

= 1043618065

Now, 1043618065 becomes the seed for generating the next number in the sequence. Repeating this calculation gives us a nice random pattern, even though the numbers are technically pseudo-random.

With this easy algorithm, we can get a sequence of nice pseudo-random numbers in our C++ programs. The randomness improves by changing seed values unpredictably. It allows practical usage in many applications like simulations, games, testing, sampling, etc. Yet, the coding remains simple, efficient, and portable across platforms. Due to this, the Park-Miller is a popular choice among C++ developers today.

Algorithm with proper steps:

Here are the steps to implement the Park-Miller random number generation algorithm in simple words:

1. Choose a Seed Value:

First, we must select an integer number that will act as the seed value. This seed can be any randomly picked number. A common choice is to just start with seed = 1.

1. Initialize Variables:

Declare a variable called 'seed' and initialize it with the seed value we picked in step 1. Also, have a variable 'next_random' to store the next random number generated.

1. Define the Generator Function:

After that, we need a function that will calculate and return the next random number every time we call it. Let's call it getnextrandom_number.

1. Apply the Formula:

Inside the function, apply the Park-Miller formula:

next_random = (16807 * seed) % 2147483647

It generates a random integer between 0 and 2147483647 from the previous seed.

1. Update the Seed:

Now, replace the old seed with the next random number calculated above.

seed = next_random

1. Return the Number:

Finally, return next_random from the function to use in our program.

1. Call the Function:

Call the getnextrandom_number in a loop or wherever required to keep getting more random numbers.

So, in 7 easy steps, we can generate a nice sequence of random numbers using this reliable and tested algorithm.

Example:

Let us take a C++ Program for Implementing the Park-Miller Random Number Generation Algorithm.

#include <iostream>

class ParkMiller {
private:
    long seed;

public:
    ParkMiller(long seed) : seed(seed) {}

    // Generate a pseudo-random number using the Park-Miller algorithm
    long generateRandomNumber() {
        const long a = 16807;   // Multiplier
        const long m = 2147483647;  // Modulus
        const long q = m / a;
        const long r = m % a;

        long temp = a * (seed % q) - r * (seed / q);

        if (temp > 0) {
            seed = temp;
        } else {
            seed = temp + m;
        }

        return seed;
    }
};

int main() {
    long seed = 1234;  // You can use any seed value

    ParkMiller rng(seed);

    // Generate and print 10 random numbers
    std::cout << "Park-Miller Random Numbers:" << std::endl;
    for (int i = 0; i < 10; ++i) {
        std::cout << rng.generateRandomNumber() << std::endl;
    }

    return 0;
}

Output:

Park-Miller Random Numbers:
165394961
1229862357
2064994670
622466744
51635271
1328980414
1729261113
2098655378
1808216131
404005600