Pseudorandom Traversal

    This site uses cookies. By continuing to browse this site, you are agreeing to our Cookie Policy.

    • Pseudorandom Traversal

      Hello! :]

      I started reading your book the other day and I was wondering about this part. You mention some "mathematical feature of prime numbers and quadratic equations" which makes the skipping work, and I'm trying to understand why, but I'm not sure, if i got this right. It would be nice to know what the feature is called, so I have some clue for starting a search for more information. I didn't find anything particularly useful on goole, as most of what turned up was concerning roots of quadratics modulo primes.

      So what i was thinking is:
      If you don't want a sequence like

      f(n+1) = (f(n) + c) mod p

      to repeat before all values < p turned up, c and p have to be relatively prime e.g.:

      c = 2, p = 5, f(0) = 3 gives you
      3, 0, 2, 4, 1 and then it starts over.

      c = 2, p = 4, f(0) = 3 gives you
      3, 1 and then starts over.

      But with a skip value being calculated as Skip = RandomA*members*members + RandomB*members + RandomC this won't always work out, I think.
      Taking, for example, the numbers from the chapter:

      members = 10, prime = 11
      and suppose RandomA = 1, RandomB = 2, RandomC = 1

      Then we get:
      1*10*10 + 2*10 + 1 = 100 + 20 + 1 = 121
      which has 11 as a factor. And now

      nextMember += skip;
      nextMember %= prime;

      will always yield the same result (nextMember) as 121 % 11 is 0 thus breaking the algorithm and, even worse, resulting in an infinite loop in the GetNext() function, right?
      Of course, it's not very likely to happen, especially with larger numbers, but it can.

      And now I'm wondering if all this is correct, or if I'm just missing something, so I hope someone can help me out here :]

      Really enjoying this book so far btw, I like it's approach!

      [edit: typo and trying to get this a little bit more readable...]

      The post was edited 1 time, last by powderedtoastman ().

    • RE: Pseudorandom Traversal

      An excellent post!

      I checked the arbiter of all things complicated, Wikipedia: en.wikipedia.org/wiki/Full_cycle.

      Looking there it is clear that the skip value can never be a multiple of the set size. The quadratic equation can of course generate such a number. So.....

      Congratulations - you've found a bug that has existed in this code base for nearly 10 years. :)

      The solution - don't bother so much with the quadratic, but DO bother with generating a skip value that is not a multiple of the set size, which would be easy enough by just choosing another prime number from the table at random.

      That also makes the code a lot easier to explain. To be honest I can't recall the original source material of this algorithm - I wrote it back in 1996, I think, to manage the generation of Ultima Online registration codes.

      Nice work, powderedtoastman!
      Mr.Mike
      Author, Programmer, Brewer, Patriot

    • Thank you!

      So they're doing it the other way around, using the set size for the modulo operation and the prime as a skip value? That's nice, as it gets rid of having to check, if the number is within your set, as well as having to calculate an extra skip value first :]

      Just not sure what arbiter means here (sorry, english is not my native language and the dictionary says something along the lines of a judge or a referee?).

      When I posted, I was trying to remember, where i took the fact from that (a + b) % c = ((a % c) + (b % c)) % c. Well it's easy enough to test on some sample numbers, so then i just took it as a given, but that's hardly formal. Today it came back to me. It's a property of a quotient ring that it has by construction.

      Ha, that's cool, i always enjoy the anecdotes, especially the UO ones, as they tend to bring back memories from playing it as a teenager some 10 years ago :D

    • So, I messed around a bit with the formula from the wikipedia page:

      en.wikipedia.org/wiki/Linear_congruential_generator

      I wanted to test it on the filling the screen with pixels function. My screen is 640*480. So the formula looked something like:

      GetNext()
      {
      nextMember = (modifier*nextMember + some_prime) % 307200;
      }

      and then for the pixel position I used:

      p=GetNext();
      int x = p % SCREENWIDTH;
      int y = p / SCREENWIDTH;

      The problem is now, that it doesn't look really random at all. If I use the total pixel number of 307200 there are always different patterns depending on the prime and modifier. Only if I use a prime for the total number of pixels as well (as suggested in the wikipedia article, I used 307189) and a modifier>1 it actually fills the screen relatively randomly. However, it doesn't fill the screen completely now. It stops at maybe 80% or so. Probably some math shenanigans going on there.
      So I thought, before wasting more time trying to figure this out I bring it here. Maybe somebody already thought about that?

      p.s.: I am only half way through the book, but I really like it so far. It's great to read without having to have a computer right at your hand, which is good for long train rides ;)