RANDOM function for the PE5 Simulator, etc..

AllyCat

Senior Member
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 :

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
return

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:

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
return

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.
 
Hi,

Often when responding to questions concerning Random numbers in the Active Forum, I link across to this thread, so perhaps it's time for an Update. The need to accurately emulate the RANDOM command in PE5 is probably now very rare, so I am changing the emphasis onto ensuring that the "Randomness" of the RANDOM command is not compromised, and how it might be extended.

As explained above, the RANDOM command actually generates a repeatable sequence of 65,535 16-bit numbers, starting from the value of the 16-bit "Seed" (or 1 if the seed is zero). At one variable per second the cycle takes about 18 hours, so is unlikely to be noticed by a "human". However, the instruction actually generates only one Random BIT per iteration, so consecutive "numbers" (i.e. represented by more than one bit) do follow an obvious pattern. Thus for consecutive nibbles (4-bits) or bytes (8-bits) the instruction should be executed at least 4 or 8 times. In practice, 8 consecutive RANDOM commands will execute about four times faster than one placed within a loop (e.g. FOR b2 = 0 TO 7 : RANDOM w0 : NEXT) and consumes only about one more byte of Program Memory. These repetitions do NOT reduce the overall cycle time because 4 and 8 (etc.) have no Common Factor with 65535, so 65,535 values per cycle must still occur. But ......

65,535 is a number of the form 2N - 1 of which many are Prime numbers, but 65535 is NOT, being obviously divisible by 5 (and also by 3, 15, 17, 51, 85, etc.). In fact all EVEN values of N must have factors of (2N/2 - 1) and (2N/2 + 1) . Therefore it is advisable NOT to use continuous repeated blocks of 3, 5 , 17 , etc. and particularly 257 RANDOM commands. In one of my test programs I "accidentally" added a single additional RANDOM "for luck", which fortunately showed as a mistake in a simple test, where the cycle period had been reduced to less than 5 minutes in the Simulator ! In passing, a Very detailed report about Random Number Generation has a usefully "quotable" Introduction, for example : ''The saying “In theory, there is no difference between theory and practice. But, in practice, there is.” certainly applies to random number generation.''. Also, her Reference [1] is to Douglas Adams' The H-HGttG. ;)

My introduction to Maximal Length (Linear) Feeedback Shift Registers (ML-LFSRs) was almost 50 years ago when a colleague gave me a handwritten single A4 sheet Table of the "Taps" for creating ML-FSRs up to about 40 stages, which he had copied from an "IEEE Transactions" of the time. I've re-copied that sheet numerous times and used it often over the years, but I thought it would be interesting to see what "The Internet" has to offer now. Quickly I found a fairly recent report with a Table up to 786 stages, but interestingly there is still no simple "Formula" to calculate the taps, it requires a "search" Program. Furthermore, this needs a very "directed" (or Pruned) search, because even a 64 stage FSR would need a computer running with a 1 ns shift rate for many years to test it by a "Brute Force" method. The Table shows that about half of all the lengths can be created using a single "Exclusive-OR" Function or Gate, with the remainder (including all those with an integer multiple of 8 stages) needing 4 Taps (and 3 gates).

There are two basic configurations for a ML-LFSR ; The type described above (Fibonacci) takes up to 4 Outputs from the Shift Register, combines them and applies the result to the (first) input of the SR. The alternative (Galois) version takes a single Output from the last stage and applies it to up to 4 Inputs (where one is always the first input). In Hardware terms the Galois is more complex because the SR needs to be "broken" at up to 3 positions to insert an EOR Gate. It can be marginally faster, because there is always only one Gate Delay (rather than up to 2), but the SR's "Input Set-Up" and "Output Propogation" Delays still need to be added. However, Galois has an advantage in the Software version, that the Output signal can be applied directly in parallel to the 4 Stages, usually via a single Byte or Word variable (because the Taps are usually calculated to be close to one end of the SR). The same Tap numbers can be used for Fibonacci or Galois, and the Symmetry (numbering) and/or Direction of the SR can be reversed, still giving the same Maximal Length. However, the generated Number Sequence is generally NOT the same, and in some circumstances can represent an exact reversal (in time).

Returning to PICaxe program code, here are some examples of a Galois Software implementation in PICaxe Basic. In this case, the XOR fuction is applied AFTER the Shift which affects the exact numbering of the Taps. The first program generates complete sequences for a 5-bit register (31 Output values), including reversed Tap Numbering and reversed Shifting Direction, showing how the time sequence can be reversed. The bit arrangement should assist in interpreting the construction of longer registers from the Table (which IMHO uses the reverse of the more-usual stage-numbering).
Code:
; 5 bits Maximal Length Feedback Shift Registers.  AllyCat October 2024.
; Taps : LFSR2 = 5 , 3 (in the comments) ; LFSR4 = 5 , 4 , 3 , 2
 b0 = 1 : b1 = 1 : b2 = 1 : b3 = 1
for b9 = 0 to 31 
  sertxd(cr,lf,#b0,"  ",#b1,"   ",#b2,"  ",#b3)
  b4 = bit4 * %01111                ; %00101     Taps pattern 4 ; 2
  b0 = b0 * 2 xor b4 and 31         ; Shift Left
  b5 = bit8 * %10111                ; %10010
  b1 = b1 / 2 xor b5 and 31         ; Shift Right (Time Reversed Output)
  b6 = bit20 * %11101               ; %01001
  b2 = b2 * 2 xor b6 and 31         ; Shift Left
  b7 = bit24 * %11110               ; %10100
  b3 = b3 / 2 xor b7 and 31         ; Shift Right (Time Reversed Output)
next b9
#REM  ; 4 inputs :
1  1   1  1
2  23   2  30
4  28   4  15
; .......
28  4   15  4
23  2   30  2
1  1   1  1
Now here is an (untested) Program for a 32-bit ML-FSR which should count loops until it returns to the Seed value. Here it could use bit15 and bit31 for the "top" bits, but I have used the Wn ** 2 format as in post #1 above, which can work with any Word variable. Note how "1" is not a good choice for a starting value (but it must occur at some time in the cycle). In most cases the XORed variable can be stored in a single byte and when/if I have a "real" PICaxe available to run for a few months at 32 MHz, then I might try testing a full cycle. :)
Code:
; 32 bits Maximal Length Feedback Shift Register (Taps 32, 30, 26, 25).  AllyCat October 2024.
w0 = 1 : w1 = 0             ; Seed Low and High Words
w2 = 0 : w3 = 0             ; Loop Counter Low and High Words
do
  b8 = w1 ** 2 * %11000101         ; MSB of High word (or bit31 in w1) * Taps For 32 bits ML-FSR
  w1 = w0 ** 2 + w1 + w1           ; MSB of Low word (or bit15 in w0) shifted Left into High word
  w0 = w0 + w0 xor b8              ; Shift Left and Toggle Tap (input) stages (if High bit was set)
  b9 = w0 AND 15                   ; Nibble result
  sertxd(" ",#b9)
  inc w2 : if w2 = 0 then          ; Loop Counter Low Word
    inc w3 : endif                 ; Carry into High Word
loop until w0 = 1 and w1 = 0       ; Continue until back to Seed
sertxd(cr,lf,"Loops= ",#w3," * 65536 + ",#w2)

Cheers, Alan.
 
Back
Top