Semiconductors work way down in the quantum realm, and easily yield random noise.
Many modern microcontrollers will contain a “true random number generator.” This includes the SAM chips used on Arduino Zero and Due.
I found my writeup and code!
Writeup:
I was quite disappointed when my new 5-disk MP3 CD changer wouldn’t
“shuffle” (play songs once each in random order) severals CDs worth of
MP3 songs (say, 100+ songs per CD for each of the 5 CDs…) A bit of
reflection convinced me that the programmers didn’t know how to
maintain a shuffled list of several hundred songs in a microcontroller
whose memory was probably full before they added the mp3 decoder. But
you don’t NEED to maintain such a list just to produce a shuffled
sequence.
The enclosed code in shuffle_lib.c will return a shuffled sequence of any
number of items up to 65535, using only 6 bytes or less of storage. A
pseudo-random number generator (PRNG) can be used to produce a non-repeating
sequence of numbers, but the usual implementation will generate only a
sequence of length 2^N-1 (for an N bit number.) That’s not a problem, you
can just filter out all the numbers that are outside the range of interest.
The other problem with a PRN is that the sequence itself repeats; 12 always
follows 232, or whatever. Since our PRNG is generating a larger range than
we want anyway, this can be fixed by permuting the number somehow before
filtering, using a separate permutation constant. This means that our final
algorithm is something like:
shufflednum(max) = filter(max, permute(prng(randreg), permuteconst));
The code example enclosed uses a standard shift-with-xor-feedback scheme for
the PRNG, simple subtraction for the permutation, and a test against the
maximum as the filter, making it quite fast. (however, it needs to be fast
if the number of items to be shuffled is much smaller than the size of the
PRNG. to get 10 items with a 16 bit PRN, you may end up filtering out 65525
numbers. This can be optimized by using a shorter PRN, of course.) Note
that by changing the PRNG seed, you change the starting position of the
shuffled list, but not the list itself, while changing the permutation
constant results in dramatically different sequences.
Enclosed files:
shuffle_lib.c: library functions in hopefully machine-independent C code
shuffle_test.c: demonstration program, written for unix, tested on Solaris
shuffle_log.c: sample run, demonstrating effects of seed vs permutation
constant changes
Implementation Code:
/*
* shuffle_lib.c
* Copyright 2002-2004 by Bill Westfield
*
* An algorithm for producing a random sequence from N items using minimal
* storage (32 bits) The sequence will not repeat items, but can be repeated
* overall by using the same seeds and offsets.
*/
/*
* internal storage for the shuffle algorithm
* These are supposed to be 16 bits each; keep an eye on your compiler.
*/
static unsigned short randreg; /* shift register PRN seed */
static unsigned short permutation_constant; /* constant for permutation */
/*
* pseudorandom
* return the next pseudo-random number (PRN) using a standard maximum
* length xor-feedback 16-bit shift register.
* This returns the number from 1 to 65535 in a fixed but apparently
* random sequence. No one number repeats.
* (This is the "standard" linear shift register with xor feedback PRN;
* other PRN generators could be used.)
*/
static unsigned short pseudorandom16 (void)
{
unsigned short newbit = 0;
if (randreg == 0) {
randreg = 1;
}
if (randreg & 0x8000) newbit = 1;
if (randreg & 0x4000) newbit ^= 1;
if (randreg & 0x1000) newbit ^= 1;
if (randreg & 0x0008) newbit ^= 1;
randreg = (randreg << 1) + newbit;
return randreg;
}
/*
* permutate
* in order to generate multiple pseudorandom seqeunces from a single
* pseudo-random seqeunce, we (variably) do a 1:1 mapping of the first
* PRN to a second set. Subtraction works fine, as would addition, xor,
* and other possibilities.
*/
static unsigned short permutate (unsigned short input)
{
return (input - permutation_constant);
}
/**************************************************************************
*
* The following functions are the externally visible interface to the
* shuffle algorithm.
**************************************************************************
*/
/*
* shuffle_init
*
* set the constants used by the shuffled number generator.
*
* Inputs: unsigned short prn_seed - the initial value for the PRN generator
* int permutation_const - value for controlling permutation
*
* (You can think of these inputs simply as two separate seeds. However,
* changing only the prn_seed may result in sequences that duplicates parts
* of other sequences. (that is, if you change only the PRN seed, "1" will
* appear at different places in the sequence, but the following number will
* always be the same.)
*
* Outputs: nothing.
*
*/
void shuffle_init (unsigned short prn_seed, int permutation_const)
{
randreg = prn_seed;
/*
* Our PRN generator will never produce zero, but the permutation WILL
* under normal circumstances. Ensure that we always have "normal
* circumstances" by disallowing zero...
*/
if (permutation_const == 0)
permutation_const == 1;
permutation_constant = permutation_const;
}
/*
* shuffle_next(max)
* Given the number of items, pick an apparently random "next item."
* Use a pseudo-random number as the basic iterator, but use different
* PORTIONS of the pseudo-random seqeunce, and skip values that are out
* of range.
*
* Returns values in the range of 0..(max-1)
*/
unsigned short shuffle_next (int max)
{
unsigned short result;
do {
result = permutate(pseudorandom16());
} while (result >= max);
return result;
}
Test code (for unix, not for Arduino…):
/*
* Shuffle_test.c
* Copyright 2002-2004 by Bill Westfield
*
* An algorithm for producing a random sequence from N items using minimal
* storage (32 bits) The sequence will not repeat items, but can be repeated
* overall by using the same seeds and offsets.
*
* This is a demonstration program that excercises the library in shuffle.c
*/
#include <stdio.h>
extern unsigned short shuffle_next(int max);
extern void shuffle_init(unsigned short prn_seed, int permutation_constant);
void test ()
{
int i; /* Loop counter */
int howmany; /* How many numbers to shuffle */
unsigned short rnd; /* "this" random number */
int offset, seed; /* seeds for the generator */
do {
/*
* input data for demonstration
*/
printf("howmany, offset, seed\n");
scanf("%d %d %d", &howmany, &offset, &seed);
if (howmany <= 0)
break;
/*
* Initialize the shuffle mechanism
*/
shuffle_init(seed, offset);
/*
* Get and print the requesting number of shuffled numbers
*/
printf("\nhowmany = %d, Offset = %d, seed = %d\n",
howmany, offset, seed);
for (i=0; i < howmany; i++) {
rnd = shuffle_next(howmany);
printf("%5d", rnd);
if (i % 15 == 14) {
printf("\n");
}
}
printf("\n");
printf("\n--------------------------------------------------------\n\n");
} while (1);
}
main ()
{
test();
}
(no, don’t tell me how old you were in 2002. Sigh.)
