How to visit many many places in one go

green points
Image by Gerd Altmann from Pixabay

No this isn’t turning into a travellog.  Imagine a huge square. It has 33,554,432 points along an edge. The entire square would thus have 1,125,899,906,842,642 points in it. That’s 250 or 3210 points. (Yes those two numbers are the same!)

Now how about contriving an algorithm that will pick a random point in this square and keep picking each point but never more than once? Eventually it will have picked every point.  If it could visit a million points every seconds, it would take something like 35.7 years to visit each and every point.

So assuming you could create an algorithm, how large would it be? How about three lines?

        public static ulong Nextulong()
        {
            ulong result = ((aUVal * ULast) + bUVal) % aUVal;
            ULast = result;
            return result;
        }

That’s in C#. The values for aUVal and bUval are

        const ulong aUVal = 1125899906842597;
        const ulong bUVal = 1051122009542795;

A uLong is just an unsigned long. That’s a 64 bit unsinged int.
This is an example of a Linear Congruential Generator BTW.

Posted in C#

Leave a Reply

Your email address will not be published. Required fields are marked *