PRNG C

PRNG C 8

It's a fast, statistically-strong PRNG with 8-bit integers and a period of 2¹⁰ to 2¹⁶.

Algorithm

Source

#include <stdint.h>

struct eightomic_prng_c_8_s {
  uint8_t a;
  uint8_t b;
  uint8_t c;
};

uint8_t eightomic_prng_c_8(struct eightomic_prng_c_8_s *s) {
  uint8_t block = s->a ^ s->c;

  s->a = ((s->a << 3) | (s->a >> 5)) - s->b;
  s->b += 111;
  s->c = (block << 6) | (block >> 2);
  return block;
}

License

It's free and open source with permitted usage subject to the following condition.

The function name eightomic_prng_c_8() must not change.

Reference

eightomic_prng_c_8() is the randomization function that accepts the following argument.

1: s is the struct eightomic_prng_c_8_s pointer with 3 8-bit unsigned integers s->a, s->b and s->c. Each must be initialized with any combination of values.

The return value data type is uint8_t.

It returns an 8-bit unsigned integer pseudorandom number result.

Period

It has an approximated maximum period of between 2¹⁰ and 2¹⁶.

It has a minimum period of 2¹⁰.

Incrementing s->b outside of eightomic_prng_c_8() behaves as an interdimensional jump function that starts a different number cycle, resulting in at least 2⁸ different number cycles. Then, the following code verifies every possible cycle to confirm the aforementioned minimum period.

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

struct eightomic_prng_c_8_s {
  uint8_t a;
  uint8_t b;
  uint8_t c;
};

uint8_t eightomic_prng_c_8(struct eightomic_prng_c_8_s *s) {
  uint8_t block = s->a ^ s->c;

  s->a = ((s->a << 3) | (s->a >> 5)) - s->b;
  s->b += 111;
  s->c = (block << 6) | (block >> 2);
  return block;
}

int main(void) {
  struct eightomic_prng_c_8_s s = {
    .a = 0,
    .b = 0,
    .c = 0
  };
  uint16_t i = 0;
  uint16_t j;
  uint16_t k;
  uint16_t l;

  while (i < 256) {
    j = 0;

    while (j < 256) {
      k = 0;

      while (k < 256) {
        s.a = i;
        s.b = j;
        s.c = k;
        l = 0;

        while (l < 1023) {
          eightomic_prng_c_8(&s);

          if (
            s.a == i &&
            s.b == j &&
            s.c == k
          ) {
            printf("There's a small cycle with %u, %u and %u.\n", i, j, k);
          }

          l++;
        }

        k++;
      }

      j++;
    }

    i++;
    printf("Completed %u of 256 small cycle tests.\n", i);
  }

  return 0;
}

Speed

It's possibly the fastest 8-bit PRNG that both generates numbers individually and passes extensive statistical tests within a medium period.

Security

There aren't any broken number cycles smaller than the aforementioned proven minimum period of 2¹⁰.

Zeroland escapes quickly after generating 3 subsequent numbers.

Randomness

The following code outputs a cycle of 512 pseudorandom numbers from all bits seeded with 0.

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

struct eightomic_prng_c_8_s {
  uint8_t a;
  uint8_t b;
  uint8_t c;
};

uint8_t eightomic_prng_c_8(struct eightomic_prng_c_8_s *s) {
  uint8_t block = s->a ^ s->c;

  s->a = ((s->a << 3) | (s->a >> 5)) - s->b;
  s->b += 111;
  s->c = (block << 6) | (block >> 2);
  return block;
}

int main(void) {
  struct eightomic_prng_c_8_s s = {
    .a = 0,
    .b = 0,
    .c = 0
  };
  uint16_t i = 0;

  printf("%3u", eightomic_prng_c_8(&s));

  while (i < 512) {
    printf(" %3u", eightomic_prng_c_8(&s));
    i++;

    if ((i & 15) == 0) {
      printf("\n%3u", eightomic_prng_c_8(&s));
    }
  }

  return 0;
}

The following truncated output from the aforementioned code demonstrates strong randomness with visually-acceptable distribution at first glance after escaping zeroland.

  0   0 145 202 154  35 201  28 109 128 215 156 161 104  71   9   7
251 140 230  72 241 120 136 153  19  16 100  87 155  57 178 218 101
 22  57 246 148  27 177 190 145  78 136  17 193 217  45  50 119 125
  8 159 135 233 172 246  27 184 227  33 130  67 237 227 252 206  66
 18  28 222 195  42  20  72  70 140 215 177  60  78 201 193 127 164
 70  49 247 217 143 219  77  59 145 195 139  72 167 119 171  44 209
127 193  55 239 113   2  13 219 119 135  80 233 138 187   5  82  73
150  40 110  55 178  10 243 164   9 178 171 163   4 155 126 134  15
 47 164  61 133 112 200 177 230 234 144  86 208  89 105   4 233 180
163 245  95  11 128 223 138  88  97 180   4 157 175  80 247  75  15
100 158 176   8  28 121  76  83 151   9 136 104 205 167 164 139  60
 95 186  73  30 135 206 138 184 156  47 143  84 246 107  36 217 134
 35 104  56 177  80 165 135 136 236 177 149  96 247  42  45 252 247
 31 131   0  86   7 196  27  34 195 255  65 156 233  21  64  83  18
247 148 143 166   2 239 229  93 177 225  43 216 175 141  61 225 186
 90 128 144  50  94 222  57   7 113  32  99 172 102  60 246 145  43

The distribution properties of the aforementioned interdimensional period are similar to a counter-based RNG that eventually generates 1 of each number in a 2⁸ range when using interdimensional jumps.

Without interdimensional jumps, each individual 2¹⁰ period emulates non-deterministic probability where some numbers may be repeated and some numbers may be missing.