How to generate a repeating integer sequence from 0 to n?

Question

I'm trying to write some code that will create a pseudo-random integer sequence that uses every digit from 0 to n, and then repeats. The naive approach would be to create an array of n integers, and then scramble them somehow, then loop through them all. That's trading space for speed, but I need to preserve space if possible.

Thinking about this reminded me of "FizzleFade", the algorithm Wolfenstein 3D used to fill the screen with red, one pixel at a time, without filling the same pixel twice. It's quite simple (this example just prints the X and Y coordinates):

    uint32_t rndval = 1;
    uint16_t x, y;
    do {
        y = rndval & 0x000FF;
        x = (rndval & 0x1FF00) >> 8;
        unsigned lsb = rndval & 1;
        rndval >>= 1;
        if (lsb) {
            rndval ^= 0x00012000;
        }
        if (x < 320 && y < 200)
            printf("x: %d y: %d\n", x, y);
    } while (rndval != 1);

At least, it looks simple. This appears to be a Linear Feedback Shift Register. However, I don't know how to adapt this code for n bits. I don't know how they determined that XOR value. I first tried to adapt the above code to 8-bit values like this:

#include <stdio.h>
#include <stdint.h>

int fizzlefade(void) {
    uint8_t rndval = 1;
    uint16_t values = 0;
    do {
        unsigned lsb = rndval & 1;
        rndval >>= 1;
        if (lsb) {
            rndval ^= 0x21;
        }
        printf("%d\n", rndval);
        values++;
    } while (rndval != 1);
    printf("Total number of values: %d\n", values);
    return 0;
}

int main(void) {
    printf("Fizzlefade demo\n");
    fizzlefade();
    return 0;
}

However, no matter what I change the XOR value to, I only get N values, where N < n, usually less than 100 values for an 8-bit value. How I do I determine the XOR taps? Do I need a different starting value? Is there a faster/smaller way than using an LFSR?

EDIT: I made a bit of progress. I noticed that in the original, the rndval was double the size of the output values. So I changed my rndval to a 16-bit unsigned, then changed the XOR to 0x1200 to mimic the original code. This gives me 250 random values, all unique -- so close! Still not sure what to do.

You could use a [linear congruential random number generator](https://en.wikipedia.org/wiki/Linear_congruential_generator) with parameters chosen so as to give full period `m`. — Nate Eldredge, Jul 06 '20 at 12:51

score 2 · Accepted Answer · answered Jul 06 '20 at 12:41

2

(I gotta run... but here's a quickie answer, based on prime numbers and modulo.

#include <stdio.h>
 
int main(void) {
    int max = 20;
    int prime = 29;
 
    for(int i=0; i<max; ++i)
    {
        int p_rand = (i*prime) % max + 1;
        printf("Pseudo Random: %d\n", p_rand);
    }
 
    return 0;
}

Output

Pseudo Random: 1
Pseudo Random: 10
Pseudo Random: 19
Pseudo Random: 8
Pseudo Random: 17
Pseudo Random: 6
Pseudo Random: 15
Pseudo Random: 4
Pseudo Random: 13
Pseudo Random: 2
Pseudo Random: 11
Pseudo Random: 20
Pseudo Random: 9
Pseudo Random: 18
Pseudo Random: 7
Pseudo Random: 16
Pseudo Random: 5
Pseudo Random: 14
Pseudo Random: 3
Pseudo Random: 12

(All numbers from 1 to 20, no duplicates, in a pseudo-random order)

answered Jul 06 '20 at 12:41

abelenky

63,815
23
109
159

How do you choose that prime number? Is it just the next prime after the n you want? – Aurelius Jul 06 '20 at 12:46
2

Any number having no common divisors with `max` will do. In particular, any prime larger than `max` will do. However, I suspect this pattern may be more regular than you are looking for; in this case it's equivalent to adding 9 each time and wrapping around when you hit the end (modulo aka clock arithmetic). – Nate Eldredge Jul 06 '20 at 12:49
Interesting, trying this with 255 as max and 257 as the prime gives me all the even numbers, followed by all the odd numbers, from 1 to 255. Changing the prime to 317 gives me a nice, random-ish sequence. This is awesome! – Aurelius Jul 06 '20 at 12:51

How to generate a repeating integer sequence from 0 to n?

1 Answers1

Output