Pseudo Random Traversal of a Set

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

    • Pseudo Random Traversal of a Set

      I was trying to write my own code to perform the pseudo random traversal of a set and ran into a situation where the skip value generated could be a multiple of the prime therefore causing the algorithm to always "randomly" generate 0s.

      The following is pseudo-ish code that I wrote.

      Source Code

      1. int primes[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31};
      2. int members = rand() % 25 + 5;
      3. int prime;
      4. //find the smallest prime number greater than members
      5. for (int i = 0; i < primes.length; i++) {
      6. if (primes[i] > members) {
      7. prime = primes[i];
      8. break;
      9. }
      10. }
      11. //randomly generate 3 non-zero coefficients
      12. int coefficients[3];
      13. for (int i = 0; i < coefficients.length; i++) {
      14. coefficients[i] = rand() % 5 + 1; //5 was arbitrarily chosen
      15. }
      16. //generate the skip value
      17. int skip = coefficients[0] * members * members + coefficients[1] * members + coefficients[2];
      18. //randomly traverse the set
      19. //if skip is a multiple of prime then this always generates 0
      20. int nextMember = 0;
      21. for (int i = 0; i < members; i++) {
      22. cout << nextMember << endl;
      23. do {
      24. nextMember += skip;
      25. nextMember %= prime;
      26. } while (nextMember >= members);
      27. }
      Display All


      The question is what did I miss which occasionally can cause the random traversal to keep generating 0s. Thanks for your help and wonderful book!

      The post was edited 3 times, last by ssrun ().

    • First, thank you for the username - I always have trouble thinking those up!

      If skip is a multiple of prime, you will always get 0 as the remainder when doing skip%prime. Adding this remainder back to the skip value will have us going around in circles (generating zeros).

      So the skip formula can't be correct, as you have already noticed, unless both you and I are misunderstanding the formula in the book.

      e.g. we have a set of 4 numbers and generate the random numbers 2, 3 and 1. That gives:

      2(4*4) + (3*4) + 1 = 32 + 12 + 1 = 45

      Prime would be 5

      45%5 = 0
      (45+0)%5 = 0
      And so on...

      I'd throw in a check to see if the skip value is divisble by the prime and, if so, add a number smaller than the prime to it. In the spirit of pseudo-random traversal, you could add a random number in the range of 1 to members.