I’ve long been an admirer of Chris Wellons’ work and have written about him many times. I almost always learn something new and useful from his blog posts so of course I take notice when he publishes something new. His latest post is about building a linear congruential pseudo-random number generator. If you know anything at all about linear congruential PRNGs you might wonder what there is to say. Quite a bit, it turns out. Although they are very simple—just the recurrence relation \(x_{n+1} = x_{n} × C + A \bmod M\) where \(x_{0}\) is the seed—properly choosing the values of \(C\), \(A\), and \(M\) is important.
A good strategy is to choose prime numbers with certain properties for \(A\) and \(C\) and Wellons shows how easy this is to do using the excellent Calc utility built into Emacs. One of the things I learned from the post was that Calc has a function for the Miller–Rabin primality test. That’s not on the Calc Cheat Sheet so I’d long since forgotten about it and always cranked up my own Scheme version when I needed to check for the primality of large numbers. Having it available in Calc is a big win, especially since I’m probably making the calculations in Calc anyway.
Like all of Wellons’ posts this one is interesting and instructive and definitely worth your time.