0

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?

André Nicolas
  • 507,029
vidstige
  • 123

2 Answers2

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.

Hagen von Eitzen
  • 374,180
  • thanks for your answer. I tried it on real quick and it really iterates through each pixel exactly once. Impressive! But it has a very regular pattern for all values of K i tried, since each pixel is K pixels apart. Perhaps this is the base of the algorithm and then some other operation can make it more irregular? – vidstige Jan 15 '14 at 21:35
  • I found this interesting link http://en.wikipedia.org/wiki/Linear_congruential_generator – vidstige Jan 15 '14 at 22:11
  • I tried with a=4013, c=4223, m=76800 just to give some numbers that satisfied the constraint specified. But the period was 1024 and not 76800... Perhaps I'm missunderstanding something, but the LCG feels relevant. – vidstige Jan 15 '14 at 22:24
1

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

Retro disolve

#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 &lt; m; i++) {
    buffer[index] = 0xffffffff;
    index = (a * index + c) % m;
    if (i % speed == 0) write(STDOUT_FILENO, buffer, sizeof(buffer));
}

for (i = 0; i &lt; 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 -
vidstige
  • 123