Shortest pseudo-random algorithm in the world

Some years ago, when I studied computer science, I bought the book Graphic Gems by Andrew Glassner. At page 221 there is a fantastic algorithm (in an article by Mike Morton). In only a few lines of code it traverses an array in a seemingly random order. Here is an example of that algorithm where num is an 8-bit number. It is initiated to 1 and then magically takes on all numbers from 1 to 255 in a seemingly random order. Num could just as well be initiated to any other number between 1 and 255. Just don’t use 0. The inner loop only has one conditional jump, one shift and one xor operation. This must be the shortest, fastest and meanest pseudo-random number generation algorithm in the world!

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

#define MASK 0xB8

int main(void)
{
   int i;
   uint8_t num = 1;

   for (i = 0; i < 255; i++) {
      printf("%d\n", num);
      if (num & 1) {
         num >>= 1;
         num ^= MASK;
      } else {
         num >>= 1;
      }
   }

   return 0;
}

It produces pseudo-random numbers from 1 to (2^w – 1), where w is bit width, see table below. In the example above bit width is 8 (unsigned char, uint8_t).

Bit width Mask
2 0x03
3 0x06
4 0x0C
5 0x14
6 0x30
7 0x60
8 0xB8
9 0x0110
10 0x0240
11 0x0500
12 0x0CA0
13 0x1B00
14 0x3500
15 0x6000
16 0xB400
17 0x00012000
18 0x00020400
19 0x00072000
20 0x00090000
21 0x00140000
22 0x00300000
23 0x00400000
24 0x00D80000
25 0x01200000
26 0x03880000
27 0x07200000
28 0x09000000
29 0x14000000
30 0x32800000
31 0x48000000
32 0xA3000000

For instance if bit width is 16 (uint16_t, short int) then the mask is 0xB400 and the pseudo-random numbers produced are in the range 1 to (2^16 – 1) = 65535. To get a full 32-bit sequence just change the mask to 0xA3000000 and integer type to uint32_t (standard int on 32-bit platforms).

Note though that the numbers produced are not very random. Enough only for simple applications. In the book it is used for a graphical effect where pixels are slowly copied from memory to the visible screen in a seemingly random order to produce a ”digital dissolve” effect.

The sequence produced is repeatable. If you seed num with the same number it will always produce the same stream of integers. That could potentially be used for a simple stream cipher (seed num with the key and then xor each byte in the stream with a new pseudo-random number). But it is not safe because the sequence is not random enough for this purpose and can easily be cryptoanalyzed.

Annonser

Om albertveli

Grävande programmerare.
Det här inlägget postades i Linux/DIY, Programmering. Bokmärk permalänken.

Kommentera

Fyll i dina uppgifter nedan eller klicka på en ikon för att logga in:

WordPress.com Logo

Du kommenterar med ditt WordPress.com-konto. Logga ut / Ändra )

Twitter-bild

Du kommenterar med ditt Twitter-konto. Logga ut / Ändra )

Facebook-foto

Du kommenterar med ditt Facebook-konto. Logga ut / Ändra )

Google+ photo

Du kommenterar med ditt Google+-konto. Logga ut / Ändra )

Ansluter till %s