Hi,
As with most microcontrollers, the PICaxe RANDOM function actually generates a repeatable and predictable sequence of numbers. Therefore an additional precaution of randomising the "seed" (starting value) is often needed to achieve a satisfactory result. However, sometimes the "repeatability" can be very useful, for example to debug a program in the simulator, or to compare the results of using different algorithms (such as number-sorting).
The PE6 Simulator exactly replicates the RANDOM function of the "real" PICaxe chips, but unfortunately the PE5 Simulator does not. So the main purpose of the code snippets in this thread is to emulate the RANDOM function to use in the PE5 Simulator. But the basic principle and explanation of its operation may be helpful to understand and improve its "randomness" or security in any PICaxe application.
Theory :
The RANDOM function uses a software algorithm to emulate the operation of a hardware "16-bit, Maximal Length, Feedback Shift Register". As the name suggests, it takes a 16-bit number which it shifts one bit to the left (i.e. multiplies it by 2). A consequence of this is that if bit 16 is set (i.e. the present value is => 32,768), then for the next value, the bit is lost by "falling off the end" (i.e. 32,768 is subtracted).
The bit loaded into the lower end of the Shift Register is determined by combining some of the parallel outputs from the Shift Register, using one or more "Exclusive OR" gates. The output from a single XOR gate (or a "tree" of several gates) is a logic "1" if an ODD number of inputs are set (to 1) and a "0" output if an EVEN number of inputs are set. Therefore, the "next value" from the Shift Register (or the RANDOM function) can be only exactly double the previous value, or "double plus one" (or the two consecutive numbers 32,768 smaller, if the previous value was greater than 32,767). This explains why the sequence of numbers is far from being truly random.
For many lengths (N) of FSR, a single XOR gate (fed from two specifically-selected outputs from the Shift Register) can produce a "maximal length" sequence of 2^N - 1 (e.g. 65,535 for 16 stages). The final (Nth) output is always used because otherwise the maximal length would be for a correspondingly shorter Shift Register. But, rather inconveniently, Shift Registers which have a length of exactly an integer multiple of 8 bits require at least four outputs to be combined to achieve a maximal cycle. This needs three XOR gates (two outputs feeding into the inputs of a third) in hardware, or 3 XOR functions in software. The PICaxe RANDOM function uses outputs 1, 2, 4 and 15 (with the first stage numbered as 0).
However, if the Shift Register contains the value of zero (all outputs low) then the subsequent input is also zero. This would repeat indefinitely to produce a "locked loop", so it appears that the zero is "trapped" by increasing its value to 1 (i.e. a seed value of either 0 or 1 becomes 2 on the next cycle). The main "counting" sequence can never return to zero because a single "1" anywhere in the Shift Register will eventually load another "1" back into the input. This explains why the maximal length is one less than 2^N. Note that here, the caret symbol (^) is used to indicate the "power" (or exponent) of 2, but in PICaxe Basic the same symbol may be used as an alternative to the XOR operator name.
Program Code :
The simplest program structure is to use W0 as the seed, so that the individual bit outputs can be directly accessed as bit0, bit1, ... , bit15. Thus the basic code, written as a subroutine, to multiply the present value by two (i.e. shift left) and add in the XOR function, could be as below. Note that the "bit" outputs are taken from the initial (seed) value of F before any shifting or gating occurs and act only on the "bit0" position (because their value is always either 0 or 1). Only at the end of the calculation is the final value assigned back to the variable F :
But sometimes it is not convenient to use w0 (or w1 which is also bit-addressable) so below is a version that can use any word variable (symbolised as F). The XOR function (shown using the alternative caret symbol) operates "bitwise" across the whole word, but it operates independently on each bit position (unlike the "carry" from one bit to the next that can occur for example with the + operator), so we can focus our attention on just one bit-position. Thus the first F*2 (which could be slightly more efficiently written as F + F) shifts "bit1" up to the "bit2" position and the two bits are XORed together by the ^F. Then the *4 moves this modified "bit2" up to "bit4" where it is XORed again and moved up to the final "bit15" position with a *2048 and XORed again.
Now we need to move just that final bit (15) into "bit0", which could be done by dividing by 32768, but the ** operator is slightly more efficient (automatically dividing by 65536) so we can simply write **2. Finally, the original value (F) needs to be shifted left (multiplied by 2) and added in, but here we must use +F+F because a *2 would also double the value in "bit0". Thus the equivalent subroutine becomes:
Conclusion :
The PICaxe RANDOM function generates a predictable and repeating sequence of 65,535 (16-bit) numbers, with each number from 1 up to 65,535 appearing exactly once and only once, but in a pseudo-random order. To create a subjectively random sequence, the function normally needs to receive a random "seed". There are numerous methods, but the simplest may be to store the seed in EPROM, incrementing it by 1 (or another prime number) each time that the program is run.
Note that it is essential that the function uses a Word variable; the loss of "bit16" restricts the feedback/loop data not just to the lowest 5 bits (31 possible values) but the result is no longer even of maximal length, terminating in sub-loops of length 12, 6, 4, 3, 3, 2 and 1 (dependent on the seed value).
If any single bit is used (e.g. to simulate a coin-toss) then exactly 32,768 "1"s and 32,767 "0"s will be generated in each run of 65,535, and there will never be more than 15 consecutive "0"s and 16 conecutive "1"s, regardles of how long the program runs. For binary (i.e. multiple bit) numbers, the RANDOM function should be executed at least once for each output bit to create an acceptable random result.
For other number bases such as 6 (for dice) or 10, then simply taking the modulus (or the remainder) after division (//) should give an acceptably random result. But for "larger" numbers, which are a significant proportion of 65,535, then it would be better to randomise to the next higher binary number, then "reject" any values that are out of the required range and execute the random function again.
Cheers, Alan.
As with most microcontrollers, the PICaxe RANDOM function actually generates a repeatable and predictable sequence of numbers. Therefore an additional precaution of randomising the "seed" (starting value) is often needed to achieve a satisfactory result. However, sometimes the "repeatability" can be very useful, for example to debug a program in the simulator, or to compare the results of using different algorithms (such as number-sorting).
The PE6 Simulator exactly replicates the RANDOM function of the "real" PICaxe chips, but unfortunately the PE5 Simulator does not. So the main purpose of the code snippets in this thread is to emulate the RANDOM function to use in the PE5 Simulator. But the basic principle and explanation of its operation may be helpful to understand and improve its "randomness" or security in any PICaxe application.
Theory :
The RANDOM function uses a software algorithm to emulate the operation of a hardware "16-bit, Maximal Length, Feedback Shift Register". As the name suggests, it takes a 16-bit number which it shifts one bit to the left (i.e. multiplies it by 2). A consequence of this is that if bit 16 is set (i.e. the present value is => 32,768), then for the next value, the bit is lost by "falling off the end" (i.e. 32,768 is subtracted).
The bit loaded into the lower end of the Shift Register is determined by combining some of the parallel outputs from the Shift Register, using one or more "Exclusive OR" gates. The output from a single XOR gate (or a "tree" of several gates) is a logic "1" if an ODD number of inputs are set (to 1) and a "0" output if an EVEN number of inputs are set. Therefore, the "next value" from the Shift Register (or the RANDOM function) can be only exactly double the previous value, or "double plus one" (or the two consecutive numbers 32,768 smaller, if the previous value was greater than 32,767). This explains why the sequence of numbers is far from being truly random.
For many lengths (N) of FSR, a single XOR gate (fed from two specifically-selected outputs from the Shift Register) can produce a "maximal length" sequence of 2^N - 1 (e.g. 65,535 for 16 stages). The final (Nth) output is always used because otherwise the maximal length would be for a correspondingly shorter Shift Register. But, rather inconveniently, Shift Registers which have a length of exactly an integer multiple of 8 bits require at least four outputs to be combined to achieve a maximal cycle. This needs three XOR gates (two outputs feeding into the inputs of a third) in hardware, or 3 XOR functions in software. The PICaxe RANDOM function uses outputs 1, 2, 4 and 15 (with the first stage numbered as 0).
However, if the Shift Register contains the value of zero (all outputs low) then the subsequent input is also zero. This would repeat indefinitely to produce a "locked loop", so it appears that the zero is "trapped" by increasing its value to 1 (i.e. a seed value of either 0 or 1 becomes 2 on the next cycle). The main "counting" sequence can never return to zero because a single "1" anywhere in the Shift Register will eventually load another "1" back into the input. This explains why the maximal length is one less than 2^N. Note that here, the caret symbol (^) is used to indicate the "power" (or exponent) of 2, but in PICaxe Basic the same symbol may be used as an alternative to the XOR operator name.
Program Code :
The simplest program structure is to use W0 as the seed, so that the individual bit outputs can be directly accessed as bit0, bit1, ... , bit15. Thus the basic code, written as a subroutine, to multiply the present value by two (i.e. shift left) and add in the XOR function, could be as below. Note that the "bit" outputs are taken from the initial (seed) value of F before any shifting or gating occurs and act only on the "bit0" position (because their value is always either 0 or 1). Only at the end of the calculation is the final value assigned back to the variable F :
Code:
random0:
w0 = w0 MIN 1 ; Avoid the minimal (zero) closed loop (only required on the first pass)
w0 = w0 * 2 + bit1 XOR bit2 XOR bit4 XOR bit15 ; Equivalent to RANDOM w0
returnNow we need to move just that final bit (15) into "bit0", which could be done by dividing by 32768, but the ** operator is slightly more efficient (automatically dividing by 65536) so we can simply write **2. Finally, the original value (F) needs to be shifted left (multiplied by 2) and added in, but here we must use +F+F because a *2 would also double the value in "bit0". Thus the equivalent subroutine becomes:
Code:
randomI: ; Trap a seed value of 0 on the first pass
F = F MIN 1
randomF: ; Subsequent passes can enter here
F = F * 2 ^ F * 4 ^ F * 2048 ^ F ** 2 + F + F ; Equivalent to RANDOM F
returnThe PICaxe RANDOM function generates a predictable and repeating sequence of 65,535 (16-bit) numbers, with each number from 1 up to 65,535 appearing exactly once and only once, but in a pseudo-random order. To create a subjectively random sequence, the function normally needs to receive a random "seed". There are numerous methods, but the simplest may be to store the seed in EPROM, incrementing it by 1 (or another prime number) each time that the program is run.
Note that it is essential that the function uses a Word variable; the loss of "bit16" restricts the feedback/loop data not just to the lowest 5 bits (31 possible values) but the result is no longer even of maximal length, terminating in sub-loops of length 12, 6, 4, 3, 3, 2 and 1 (dependent on the seed value).
If any single bit is used (e.g. to simulate a coin-toss) then exactly 32,768 "1"s and 32,767 "0"s will be generated in each run of 65,535, and there will never be more than 15 consecutive "0"s and 16 conecutive "1"s, regardles of how long the program runs. For binary (i.e. multiple bit) numbers, the RANDOM function should be executed at least once for each output bit to create an acceptable random result.
For other number bases such as 6 (for dice) or 10, then simply taking the modulus (or the remainder) after division (//) should give an acceptably random result. But for "larger" numbers, which are a significant proportion of 65,535, then it would be better to randomise to the next higher binary number, then "reject" any values that are out of the required range and execute the random function again.
Cheers, Alan.
