Pseudorandom Number Generator (PRNG)

The availability of random numbers in modern computers is taken for granted. We always assume that it will be possible to simulate the throw of a dice by calling a function that “magically” returns a random number.

But, where do random numbers come from and how can we use the Digirule2 to generate a few?

The Linear Feedback Shift Register (LFSR)

This section demonstrates a very simple, but effective technique of producing a series of random numbers using Digirule2 ASM. This technique is based on a “shift register” and it does not really have to be implemented in software since it is possible to build it on a breadboard out of discrete components or even program it on a Field Programmable Gate Array (FPGA).

Its operation is very simple, an exclusive OR (XOR) function over the current binary number stored in the register is used to produce a 0/1 result. Then, the bits in the register are shifted to the right and the XOR result is sent to the Most Significant Bit (MSB) of the register. This process is repeated, each time taking the shift register from one state to the next. The shift direction and whether the new bit is added at the MSB or Least Significant Bit (LSB) sides are of course interchangeable.

Obviously, there is nothing truly “random” in this process. But given a long enough shift register and a carefully chosen combination of its output to be XORed, the amount of different states the register goes through is so large that they appear to be random, especially to a human being.

A PRNG based on this technique is called a “Linear Feedback Shift Register”. It is Linear, because the calculation of the new bit is a linear combination of the outputs of the shift register. It uses “Feedback” because the bit derived from the current state of the register is sent back through the same register. And finally, it is called “Shift Register” because at each step, the register is shifted either to the left or the right to “make space” for the calculated bit.

Two variants of this are presented here: an 8bit PRNG and a 9bit PRNG.

An 8bit PRNG

As explained in the brief introduction about LFSRs, there are two things that need to be managed, the “width” of the shift register and which outputs are to be combined in order to produce the feedback bit. Both of these parameters determine the “randomness” of the generator.

Considering the width of the shift register is straightforward: An \(N\) bit shift register is capable of producing \(2^{N-1}\) states. An 8bit PRNG is expected to produce 255 different numbers before running out of combinations and repeating itself. Similarly a 64bit PRNG is expected to produce 18,446,744,073,709,551,615 combinations, before repeating itself.

Repetition is not good for randomness but this is why these are called “Pseudo-random” generators.

But, considering which outputs of the register to combine, so that the shift register goes through all of its possible states, is a more difficult problem. For example, you may have noticed that the shift register never goes through the all-zeros state (hence the \(N-1\) above). If the LFSR ever hits the all-zeros state it will never move out of it. This is because of the truth table of the XOR function where zeros at both of its inputs result in a zero at its output. It is only if (and only if) either of its inputs is 1, that the output of the XOR equals a logic 1 too. This means that the inputs must be chosen carefully, otherwise they might put the state register through a much shorter and predictable cycle of numbers that would not appear random at all.

Fortunately, the rules behind the selection of the right outputs so that an \(N\) bit LFSR really does go through all of its states have been worked out and the Wikipedia webpage on LFSRs includes them in a table, with one combination per value of \(N\), from a mere 2bit LFSR all the way to 24 and beyond.

For \(N=8\), the “polynomial” that describes which inputs to be used in the calculation of the feedback bit is:

\[x^8 + x^6 + x^5 + x^4 + 1\]

In this case, the shift register is shift to the right and \(x^8\) is the input. Bit positions are counted from the left.

Therefore, all that we have to do here is grab a bunch of bits, XOR them, shift the register and send the calculated bit at its input.

This is a one liner in Python:

# Remember here, bit positions are counted from the left.
# x>>2 is x^4, x>>3 is x^5 and so on.
rn=lambda x:(x>>1) | (((x ^ (x>>2) ^ (x>>3) ^ (x>>4)) & 1)<<7)

print(rn(42)) # Returns 149
print(rn(rn(42))) # Returns 202 and so  on

The evaluation of this one liner in Digirule2 ASM proceeds as follows:

 1.EQU status_reg=252
 2.EQU carry_bit=1
 3
 4COPYRA state
 5COPYRR state R1
 6SHIFTRR state
 7CBR carry_bit status_reg
 8SHIFTRR state
 9XORRA state
10CBR carry_bit status_reg
11SHIFTRR state
12XORRA state
13CBR carry_bit status_reg
14SHIFTRR state
15XORRA state
16ANDLA 1
17COPYAR R2
18CBR carry_bit status_reg
19SHIFTRR R1
20DECRJZ R2
21JUMP clr_bit
22set_bit:
23SBR 7 R1
24JUMP resume
25clr_bit:
26CBR 7 R1
27resume:
28COPYRR R1 state
29HALT
30state:
31.DB 42
32R1:
33.DB 0
34R2:
35.DB 0

This is part of ../../dg_asm_examples/lfsr/lfsr.dsf

Notice here that in the first two operations, the current state is saved in R1 and then undergoes a series of shifts and XORs between these shifted versions. The CBR that precedes the SHIFT is specific to Digirule2 ASM because its shift operation is through the Carry bit. Also, although the whole word is XORed, we are only interested in the LSB. Finally, the input bit of the shift register (the \(x^8\)) is set (or cleared) and the final value is copied back to the state register.

To this, we can also add an array, as demonstrated in section Advanced Digirule 2 Programming and add another parameter that controls the maximum number of numbers to generate.

With an initial state value of \(42\) and set to produce 10 random numbers, this program returns:

149, 202, 229, 114, 185, 220, 238, 119, 187, 221

Putting it all together

The complete listing is as follows:

 1# A very simple random number generator
 2
 3# Here is one of the simplest ways to generate 
 4# Pseudo-Random-Numbers. The clue is in the name.
 5# Although it is difficult to predict what is the 
 6# next number in a sequence of 10 numbers, if we 
 7# wait long enough, the numbers start repeating, in 
 8# exactly the same sequence. In fact, if we start 
 9# the generator from the same number it will generate 
10# the exact same next one and the next one and so on.
11
12# In this example, the width of the register is 8bit 
13# and therefore its "period" is 256 numbers.
14
15# This should be enough to give the Digirule the 
16# ability to roll the dice.
17
18.EQU status_reg=252    # Status register on the Digirule2
19.EQU carry_bit=1
20.EQU zero_bit=0
21
22# Number of random numbers to generate
23.EQU gen_n_numbers=10  
24
25# Initial state for the random number generator
26# NOTE: Usually computers take the current time 
27#       as the initial "seed". And this is how
28#       the sequence of numbers appears to be 
29#       different, every time we execute a program.
30.EQU rnd_state=42      
31
32# Put `array_idx` at the start of `array`
33COPYLR array array_idx
34start:
35COPYRA state
36COPYRR state R1
37SHIFTRR state             # SHIFTRR goes through the carry bit
38CBR carry_bit status_reg  # and here we only want a SHIFT operation. 
39SHIFTRR state             # This bit clearing after SHIFTRR is  
40XORRA state               # repeatedly applied here, since each  
41CBR carry_bit status_reg  # SHIFTRR should not be affected by whatever
42SHIFTRR state             # is already in the carry bit of the status  
43XORRA state               # register.  
44CBR carry_bit status_reg
45SHIFTRR state
46XORRA state
47ANDLA 1
48COPYAR R2
49CBR carry_bit status_reg
50SHIFTRR R1
51DECRJZ R2
52JUMP clr_bit
53set_bit:
54SBR 7 R1
55JUMP resume
56clr_bit:
57CBR 7 R1
58resume:
59COPYRR R1 state           # The current state becomes the next state 
60COPYLR state f_from
61COPYRR array_idx f_to
62CALL f_copy_ind           # The current state gets assigned to the array
63INCR array_idx 
64DECRJZ R0
65JUMP start                # Standard iteration: Decrease, check and jump  
66HALT                      # otherwise stop.
67
68state:
69.DB rnd_state
70R0:
71.DB gen_n_numbers
72R1:
73.DB 0
74R2:
75.DB 0
76
77
78# Memory copy by indirect addressing via self-modification.
79# We construct a suitable absolute
80# addressing copy instruction (COPYRR) and
81# execute it as a sub-routine over f_from, f_to
82
83f_copy_ind:
84.DB 7
85f_from:
86.DB 0
87f_to:
88.DB 0
89RETURN
90
91array_idx:
92.DB 0
93
94array:
95.DB 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0

1bit Powerup! - A 9bit PRNG!

Surprisingy, a 9bit PRNG is not only feasible on the Digirule2, it probably runs faster than the 8bit but if it was to be used practically, it ends up being inefficient.

The technique is exactly the same but in the case of the 9bit PRNG we are taking into advantage the fact that the SHIFT** operations are through carry on the Digirule2. Therefore, 1 more bit is inserted in the whole process, for free.

This characteristic, along with the fact that the 9bit PRNG uses a 2 factor polyonym, makes this PRNG much faster compared to the 8bit version.

The only problem with this version however is that if this PRNG was to be packaged in a re-usable form, then both the state variable as well as the Carry flag bit (that is 1 bit) would have to be stored and re-stored between calls to the function. Since it is impossible to save a single bit, two bytes would have to be used. Out of these two bytes, the second one would practically be going “to waste”.

Note

The PRNG is re-usable in its current form if the state variable can be truncated to 8 bits. In that case, the random number sequence would not have the variation possible with the 9bits but it would still appear “random”.

Here is what this implementation looks like:

 1# A very simple random number generator 
 2# using a 9bit LFSR. The one extra bit is coming from the 
 3# carry flag on the Digirule2, because its `SHIFTRR, SHIFTRL` 
 4# commands perform shift THROUGH the carry.
 5
 6# To make this random number generator re-usable, we would have 
 7# to store the carry bit as well between calls, consuming two 
 8# bytes of memory.
 9
10.EQU status_reg=252      # Status register on the Digirule2
11.EQU carry_bit=1         # The carry bit
12.EQU data_led=255        # LED register
13.EQU rnd_state=42        # Initial state for the random number generator
14.EQU gen_n_numbers=10    # How many numbers to generate
15COPYLR array array_idx
16start:
17BCRSS 0 state
18JUMP op_a_was_0
19JUMP op_a_was_1
20op_a_was_0:
21BCRSS 5 state
22JUMP op_a_was_0_op_b_was_0
23JUMP op_a_was_0_op_b_was_1
24op_a_was_1:
25BCRSS 5 state
26JUMP op_a_was_1_op_b_was_0
27JUMP op_a_was_1_op_b_was_1
28op_a_was_1_op_b_was_1:
29op_a_was_0_op_b_was_0:
30CBR carry_bit status_reg
31JUMP continue
32op_a_was_0_op_b_was_1:
33op_a_was_1_op_b_was_0:
34SBR carry_bit status_reg
35continue:
36SHIFTRR state
37COPYLR state f_from
38COPYRR array_idx f_to
39CALL f_copy_ind
40INCR array_idx 
41DECRJZ R0
42JUMP start
43HALT
44
45state:
46.DB rnd_state
47R0:
48.DB gen_n_numbers
49
50f_copy_ind:
51.DB 7
52f_from:
53.DB 0
54f_to:
55.DB 0
56RETURN
57
58array_idx:
59.DB 0
60
61array:
62.DB 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0

Notice here that due to the fact that only 1 XOR is required, it is run “in-place” through a series of bit tests that directly modify the Carry flag, prior to shifting the register.

As before, we get to see only the lower 8bits but with much more variation in the available combinations. This routine produces these numbers: 149, 202, 229, 114, 185, 220, 238, 119, 187, 221

The complete listing adds parameters for the initial state of the register and how many numbers to generate and is available in ../../dg_asm_examples/lfsr/lfsr_9bit.dsf

Conclusion

Providing the ability to generate random numbers on the Digirule2 means that we can now set new “random” objectives in games.

For example, one of the Digirule2 demos is a game of “Guess the number”, where the player tries to guess a hidden number in as few guesses as possible.

With a random number generator, it is now possible to make the game restart, with a new unknown number challenge for the player, or have the POV Light Stick display random “images”.