Pseudorandom Number Generation via LCG's

mgcadmin 25-03-2023

Random numbers are incredibly useful, from running simulations to procedural terrain generation in video games and million other uses in between, they come up all. the. time.

Ironically, it is almost impossible to generate truly random numbers. And actually IS impossible to do it via an algebraic formula. Thats why random number generators are actually called pseudorandom number generators(pnrg).

There are many different techniques to implementing pnrgs with wildly varying approaches. However, before we get much farther I feel like I should state the following: implementing a pnrg is surprisingly difficult, and very easy to do wrong.

Just as with sorting its usually best to use whatever facilities your programming language of choice makes available in its standard library than try to write a production pnrg yourself, though it's still worthwhile to understand what's actually going on under the hood.

Linear Congruential Generators

LCG's are derived from a very simple formula:

previous number = (A * previous number + C) % M

where A, C, M are constants, and previous is started from some seed number. Based on what constants are chosen, the results can be wildly different.

An LCG will eventually start repeating itself, and the amount of numbers it outputs in a row before the sequence repeats is called the "period" of the LCG. The longer the period, the more random your sequence appears.

The rand() function in the C standard library is based on LCG's - and there is a reason C++ introduced the <random> header. Regardless, lets see how we can implement one ourselves:

 
class LCG {
    private:
        int seedNo;
        int A = 6364136223846793005; 
        int C = 1;
        int M = pow(2, 31) - 1;
    public:
        LCG(int seed = 1) {
            seedNo = seed;
        }
        int nextInt() {
            static int prev = seedNo;
            prev = (A * prev + C) % M;
            return prev;
        }
}; 

Let's see how we did:

 
int main(int argc, char* argv[]) {
    for (int i = 0; i < 5; i++) {
        LCG lcg(i);
        for (int i = 0; i < 10; i++) {
            cout<<lcg.nextInt()<<" ";
        }
        cout<<endl;
    }
    return 0;
} 
max@MaxGorenLaptop$ ./lcg
 1 1284865838 1311059223 1078613516 -759360483 689433626 980903571 -630262568 313537017 -1280290874 
 1137655759 1402005604 -2047445611 2086704690 177681611 -571736912 1732688625 -1737397410 1978237319 148946364
 1275960845 -111264950 252453379 1505785736 877230825 1518416374 481088063 -648464876 -534352507 -1317061790
 -102953413 1648477536 1197101537 -848034930 -456257033 1004908908 -834616323 -1864501638 1095555443 1313949240
 -1799938087 -230014938 184426671 -88240188 -88571531 -1346319214 -212180053 1692162576 918144209 1626359742

Well, that looks pretty random, but how can we improve on it? Well, first being able to confine the output to a range would be useful, and also simple with use of modulo:

 
class LCG {
       //....
        int nextInt(int limit) {
            static int prev = seedNo;
            prev = (A * prev + C) % M;
            return prev % limit;
        } 
};


max@MaxGorenLaptop:/mnt/c/Users/mgoren/Desktop$ ./lcg
 1 46 23 12 29 26 47 16 49 98 
 7 0 49 50 3 76 41 94 35 88
 13 74 3 36 33 46 63 20 33 98
 59 96 25 42 47 8 53 22 15 56
 17 38 75 96 17 46 71 16 9 90

Or, We cold extract the M most bits of the values generated, giving us a different distribution:

//....
int nextInt(int limit) {
    static int prev = seedNo;
    prev = (A * prev + C) % M;
    unsigned mask = ((1 << 24) - 1) >> 8;
    prev = prev & mask;
    return prev % limit;
} 


max@MaxGorenLaptop:/mnt/c/Users/mgoren/Desktop$ ./lcg
 1 58 43 28 49 42 59 80 93 22 
 35 92 1 50 15 88 57 86 59 72
 61 78 7 0 65 90 23 44 37 2
 43 28 61 10 99 20 73 98 67 76
 53 22 67 4 41 70 15 56 85 66

So there you are, pseudorandom numbers via Linear Congruential Generators. Happy hacking!

---