General > General Technical Chat

Odds seem too high when guessing random zeroes and ones

<< < (6/6)

ejeffrey:

--- Quote from: AndyBeez on April 05, 2023, 09:11:00 pm ---To prove the randomness of any random number generator, whether it is on a pocket calculator, a crypto cypher generator, or a national lottery supercomputer, you need to calculate the Standard Deviation of the random sequence. A pure random sequence will have a SD of exactly one-half.  Any other number, even 0.501 or 0.49999999999 indicates bias or 'clustering'. Averaging over even a small sample set will show whether a bias exists.

--- End quote ---

I'm sorry, this is complete nonsense.

AndyBeez:
You are clearly a genius. So how do you prove random number generator is random?

SiliconWizard:

--- Quote from: AndyBeez on April 05, 2023, 09:40:40 pm ---You are clearly a genius. So how do you prove random number generator is random?

--- End quote ---

I posted a link to an article dealing with exactly this. "Random" is a rabbit hole. There's a number of statistical tests available for characterizing various properties of PRNGs.
The Chi-squared test woule be a start, but will only exhibit part of the properties.

ejeffrey:

--- Quote from: AndyBeez on April 05, 2023, 09:40:40 pm ---You are clearly a genius. So how do you prove random number generator is random?

--- End quote ---

Well. first you use more careful terminology.  You can't prove the random number generator is random, at least by analysis of the output. You can only fail to demonstrate it's non-randomness.  So there are a lot of literature out there on randomness tests and their relevance for certain applications.

Test like the mean and standard deviation (it's not clear which you meant -- you said standard deviation, but your description of that is for the mean) are extremely basic tests for uniform distribution, but you need to at least specify the statistical properties, not "it must be exactly 0.500000000000000000000" since no finite measurement will give you exactly 50% every time.  More importantly: while uniform distribution is sometimes (but not always!) a desirable property of a random number generator, it's not the primary thing we mean when we say random.  What makes a random number generator random is that it has no discernible correlations or patterns between numbers.  Of course all pseudo-random generators are trivially non-random, if you know the internal state you can predict all future values, but you test for the types of patterns you care about.  A randomness test that doesn't look at correlations but only the statistical distribution of individual values is not a meaningful test of randomness.

Nominal Animal:
Arduino random() (from avr-libc or newlib) is a linear congruential generator, and not a very "random" one at that.

The most commonly used tool for evaluating pseudo-random number generators –– randomness testing –– is the TestU01 framework, and specifically its BigCrush test suite.

My favourite generator, Xorshift64* keeping only 32 most significant bits, passes all the tests in the BigCrush test suite:

--- Code: ---uint64_t  prng_state;  /* Initialize to any non-zero value! */

uint32_t  prng_u32(void)
{
    uint64_t  x = prng_state;
    x ^= x >> 12;
    x ^= x << 25;
    x ^= x >> 27;
    prng_state = x;
    return (x * UINT64_C(2685821657736338717)) >> 32;
}

--- End code ---
On 32-bit microcontrollers, it is also much faster than the LCGs commonly used.  On 8-bit microcontrollers, the 64-bit × 64-bit = 64-bit multiplication and then dropping the low 32 bits, is a bit slow, but still faster than the 32-bit non-power-of-two division and modulus used in LCGs.

In other words, it beats random().  Libraries only stick to LCGs for historical reasons: it would be nasty to change program behaviour, so they tend to try to keep random() producing the same (not very good) sequences for the same seeds.

An extension to provide just one bit at a time:

--- Code: ---uint32_t  prng_bitcache;
signed char prng_bitcache_left = 0;

int prng_bit(void)
{
    int  bit;

    if (prng_bitcache_left < 1) {
        prng_bitcache_left = 31;
        prng_bitcache = prng_u32();
    } else {
        prng_bitcache_left--;
    }

    bit = prng_bitcache & 1;
    prng_bitcache >>= 1;
    return bit;
}

--- End code ---
The trick is that you do need to initialize the 64 bits of prng_state to a "random" value, anything except all zeros, to get an unpredictable sequence.
(If you always initialize it to the same value, you will always get the same sequence.)

I also like to do a few dozen rounds of the Xorshift64* steps (each step being x^=x>>12; x^=x<< 25; x^=x>>27;) to thoroughly mix the initial state.

Furthermore, you can periodically modify prng_state (as long as the result is nonzero) to introduce additional entropy, "randomness" to the sequence.  Some microcontrollers have suitable entropy sources in hardware, but also things like ADC reading a chaotic oscillator or a floating pin should work.
As an example OP could use,

--- Code: ---void prng_randomize(int pin)
{
    int_fast8_t  i;
    union {
        uint64_t  u64;
        unsigned char uc[8];
    } temp;

    // A small delay to ensure chaotic oscillator or floating pin has time to go wonky
    delayMicroseconds(500);

    // Read 8-bit ADC readings, reject all-zeros
    do {
        for (i = 0; i < 8; i++)
            temp.uc[i] = analogRead(pin);
    } while (!temp.u64);

    // Mix the state thoroughly
    i = 16; while (i-->0) {
        temp.u64 ^= temp.u64 >> 12;
        temp.u64 ^= temp.u64 << 25;
        temp.u64 ^= temp.u64 >> 27;
    }

    // Done.
    prng_state = temp.u64;
}

--- End code ---


Combining all of the above,

--- Code: ---#define EXTRA_LED 12
#define BOARD_LED LED_BUILTIN
#define ENTROPY_PIN 0

uint64_t  prng_state;  /* Initialize to any non-zero value! */

uint32_t  prng_u32(void)
{
    uint64_t  x = prng_state;
    x ^= x >> 12;
    x ^= x << 25;
    x ^= x >> 27;
    prng_state = x;
    return (x * UINT64_C(2685821657736338717)) >> 32;
}

uint32_t  prng_bitcache;
signed char prng_bitcache_left;

void prng_randomize(int pin)
{
    int_fast8_t  i;
    union {
        uint64_t  u64;
        unsigned char uc[8];
    } temp;

    // A small delay to ensure chaotic oscillator or floating pin has time to go wonky
    delayMicroseconds(500);

    // Read 8-bit ADC readings.  Mix in 'i' in case analogRead always reads as zero.
    do {
        for (i = 0; i < 8; i++)
            temp.uc[i] = analogRead(pin) ^ i;
    } while (!temp.u64);

    // Mix the state thoroughly
    i = 16; while (i-->0) {
        temp.u64 ^= temp.u64 >> 12;
        temp.u64 ^= temp.u64 << 25;
        temp.u64 ^= temp.u64 >> 27;
    }

    // Done.
    prng_state = temp.u64;
    prng_bitcache_left = 0;
}

int prng_bit(void)
{
    int  bit;

    if (prng_bitcache_left < 1) {
        prng_bitcache_left = 31;
        prng_bitcache = prng_u32();
    } else {
        prng_bitcache_left--;
    }

    bit = prng_bitcache & 1;
    prng_bitcache >>= 1;
    return bit;
}

void setup() {
  Serial.begin(9600);

  pinMode(BOARD_LED, OUTPUT);
  pinMode(EXTRA_LED, OUTPUT);
  pinMode(ENTROPY_PIN, INPUT);  // No pullups or pulldowns!

  prng_randomize(ENTROPY_PIN);
}

void loop() {

  // blip, blip, blip, random draw
  digitalWrite(BOARD_LED, 0);
  digitalWrite(EXTRA_LED, 0);
  delay(500);
  for (unsigned char c=0; c < 3; c++) {
    digitalWrite(BOARD_LED, 0);
    digitalWrite(EXTRA_LED, 0);
    delay(190);
    digitalWrite(BOARD_LED, 1);
    digitalWrite(EXTRA_LED, 1);
    delay(10);
  }
  digitalWrite(BOARD_LED, 0);
  digitalWrite(EXTRA_LED, 0);
  delay(1000);

  int  bit = prng_bit();
  digitalWrite(BOARD_LED, bit);
  digitalWrite(EXTRA_LED, !bit);

  delay(1500);
}

--- End code ---
This is only compile-tested, though, so might have some brainfarts in it.  Lemme know if you find anything odd in it.

Navigation

[0] Message Index

[*] Previous page

There was an error while thanking
Thanking...
Go to full version
Powered by SMFPacks Advanced Attachments Uploader Mod