Pseudo random ordering of integers

Question

I remember an old retro effect for a screen resolution of $320\times 240$. You would iterate the pixels in a linear fashion so there are $76800$ pixels. You could iterate then one by one starting at pixel $0$ and ending with pixel $76800-1$. However, there was some clever trick using an and mask and multiplication or addition with some magic constants. I don't remember the specifics. This resulted in a pseudo-random iteration over the pixels. No pixel was ever visited twice and all pixels were visited. How can this be done? How should I approach this problem? What is this problem called?

Answer 1

There are several methods. For example, it turns out that $p=76800+1$ is prime; therefore one can take any $k$ with $1\le k<p$ and then has that $ki\equiv kj\pmod p$ implies $i\equiv j\pmod p$. Especially, $ki\bmod p$ iterates over $\{0,\ldots,p-1\}$ as $i$ runs from $0$ to $p-1$:

#define K 47465  
#define P (320*240+1)
ki = K;
for (;;) {
   setpixel(ki-1);
   ki += K; 
   if (ki>=P) {
       ki -= P;
       if (ki==0) break;
   }
} 

(I defined $K$ to be close to th egolden ratio times $p$). This is not "good" pseudorandom however as the pixels appear "too" uniformly.

Answer 2

This is done by using a Linear Congruential Generator (LCG). It's a very basic pseudo-random generator. The state is contained entirely in the last produced number and the next random number in the range is obtained as.

$x_{n+1} = (ax_n + c) \mod m;$

Where $a$, $c$, and $m$ are constants that can be used to very the series. Also $x_0$ is the seed or initial value.

Also the series is know to have a period of $m$ if and only if (from the wikipedia page)

1. $c$ and $m$ are relatively prime,
2. $a - 1$ is divisible by all prime factors of $m$
3. $a - 1$ is a multiple of $4$ if $m$ is a multiple of $4$.

For this particular case, as the period should be $320 \times 240=76800$ we let

• $m = 76800$
• $c$ can be set to any value not sharing any divisiors with $m$ such as $7$.
• $a = 3 \times 5 \times 4 \times k + 1$ where $k$ is any multiplier larger than 1.

Varying $x_0, c, k$ should give various interesting dissolve effects.

I wrote a small C-program with c = 7, k = 77 and a = 3 * 5 * 4 * k + 1

#include <unistd.h>
// Linear Congruential Generator
int main() {
    const int w = 320, h = 240;
    const int m = w * h;
    const int c = 7;
    const int k = 77;
    const int a = 3 * 5 * 4 * k + 1;
    const int speed = 1500;
    unsigned int buffer[w * h];
    int index = 0;
    int i;

    for (i = 0; i < m; i++) {
        buffer[index] = 0xffffffff;
        index = (a * index + c) % m;
        if (i % speed == 0) write(STDOUT_FILENO, buffer, sizeof(buffer));
    }

    for (i = 0; i < m; i++) {
        buffer[index] = 0xff000000;
        index = (a * index + c) % m;
        if (i % speed == 0) write(STDOUT_FILENO, buffer, sizeof(buffer));
    }
}

Test it like so:

$gcc a.c && ./a.out | ffplay -f rawvideo -pixel_format rgb32 -video_size 320x240 -i -