Random Number Generation

Lab 12 -- Random Number Generation

Generating random numbers is an important computing function, and these are used in simulations and games. For testing and debugging of simulations and/or games using random numbers, we need to have an ability to reproduce the same sequence. Instead of using truly random numbers, we use pseudo-random numbers. These are numbers that appear to be random to us, but created by an algorithm. By giving the algorithm the same "seed" value, we can get the same sequence of pseudo-random numbers. Thus, a programming language typically provides two functions: one to specify the seed value (e.g. srandom), and one to give us the next value (random). We will use the srandom and random functions from C in this lab. We call functions like these random number generators (RNGs).

Part 1 - Calling the seed function and the random function

First, let's examine how we use the seed function and the random function. You can use rand1.asm to get started, or you can create your own version from previous code.

Since we will be using C functions, we need to specify them with the "extern" keyword.


    extern  printf      ; We will use this external function
    extern  srandom     ; We will use this external function
    extern  random      ; We will use this external function

You can put this all on one line, though this way allows the functions to stand out when reviewing the code.

In the main part of the program, we will call the srandom function with the seed value placed into EDI. The A register should be cleared. The following code will "seed" the random number generator with the value 3. Note that there is nothing special about using as the seed value. Choosing a seed value is beyond the scope of this lab, but if you are interested you can find academic papers on the subject. We use a seed value here to get a repeatable series of random values.


   mov   edi, 3
   xor   rax, rax          ; A = 0
   call  srandom

Next, we call the random function to get a pseudo-random number. The A register may already be clear, but you should not expect every function that you "call" will not change the register values. (Also, this may work without setting A to 0. You can try it if you are curious.)


   xor   rax, rax          ; A = 0
   call  random
   ; A should now hold a random value
   mov   [myval], rax      ; Store the value

After the call to "random", we store the value in the A register. Edit the "rand1.asm" program to generate two more random numbers. Do not call the seed function a second time; the point is to see that it does generate a sequence of values. Put all of this together, along with anything else that you need to make a fully functioning program. Show the program, and that it assembles and runs. Run this program three times. You should observe the same three values are output each time.

Copy the program to a new file. In the copy, change the seed value. It's OK to hard-code it like in the previous example. Run this program three times. You should observe the same three values are output each time, but that these values are different from those generated by the first version.

Part 2 - A random-looking seed

Now let's give the seed function an unpredictable value. This way, the seed itself will seem to be random, so the generated values are also going to be unpredictable. This is good for simulations and games, where we want the user's experience to be different each time. One common way to do this is to use a variation on the time for the seed. For example, there is a "time()" function in C that reports the current time as an unsigned integer, and this value changes every second. Therefore, using that will allow a program to make a random-seeming seed value. We will use this idea to seed the RNG.

On x86 machines, there is an instruction called "rdtsc" which ReaDs the Time-Stamp Counter, and puts the result into the 32-bit versions of D and A. In other words, before the 64 bit registers, you could get a 64-bit result but it would put the top half in D and the lower half in A. Examine the code that follows.


   ; "Seed" the random number generator
   rdtsc
   mov   [myseed], eax     ; tsc = Time Stamp Counter into edx:eax
   mov   edi, eax          ; seed value goes into EDI
   xor   rax, rax          ; A = 0
   call  srandom

You should notice that the first couple of lines do the rdtsc instruction, then stores EAX into a memory location with the label "myseed". This is done primarily so that we can print it out. Copy your code from part 1, add the TSC value to seed the RNG, print "Seed is " followed by the [myseed] value, and verify that it works. You should observe that it prints three random values each time, and that these random values are different every run. You should also observe that the seed value is different every time you run it.

Part 3 - Populating some data randomly

Now that we have seen how to seed the RNG and get several pseudo-random values, use it to populate some data. Data like this could be used for a game, such as a matching challenge: imagine if the player has only a few seconds to find the longest string of vowels. Or it could be used for an application like a neural network, where each value represents a network weight, which are then altered to "learn" a function. Several AI algorithms use random values like this to initialize data.

Start with an uninitialized data section, and reserve 100 bytes (revisit the lab on input and output to see how to reserve space). Reserve another byte directly after that, which we will use to mark the end of the string. (You could reserve 101 bytes together, but you might find it easier to have a second label to use to store the 0 that marks the end of the string.) Then create a loop to populate the first 100 bytes with random character values.

To map the random values to characters, we will keep the process simple. Since the random values are very large integers, the first step is to limit the random values to something smaller, which we will do as an AND command. To make this easy, we will not be concerned with the entire alphabet, but a subset of the first 15 characters. The hexdecimal value F is equivalent to decimal 15, so ANDing the random value with F will result in a value between 0 and 15. Next, we'll make the assumption that the at-sign can be included. (Look at an ASCII chart, and you should be able to anticipate where this is going.) Next, OR the value with 40h. The result should be an ASCII value between 64 and 79.

Put a 0 in byte 101, to indicate the end of a string. Then print the array. Also print a new-line character. Using "puts" to print the array means that it will add a new-line character for you. Or you could print a new-line in another way. Run this several times, to show that it does create random data every time.

The following code shows an example of "puts", where "mystring" is defined as a null-terminated string (i.e. the string has a 0 after it). You can use "printf" instead if you prefer.


       extern  puts        ; We will use this external function
    ...
       mov   rdi, mystring
       call  puts             ; puts adds a newline.

Notes:

You will need to create a loop to accomplish this. You can use the "loop" command to do it, but you are not required to use the "loop" command.
Ideally, the program should have an easy-to-change value for the number of random characters in the string, such as "N" defined at the top, set to 100. The space for the zero value would then make the length "N+1".

Questions

Suppose that a fellow student always calls the seed function with 3 before every call to the random function. What would their code produce? What advice would you give them?
Why does it make the program easier to write by only having 16 possible random characters?
Why does it make the program easier to write by allowing the at-sign as a character?
Suppose that we want to use lower-case letters instead. What would you need to change in the program?
What other operations besides AND and OR could we use to restrict the random values? Are there any advantages/disadvantages to using AND and OR?
When using time-based seed values, to make the program seem random, you could restrict the seed to part of the time value. Why is using the low part of the time value for this purpose better than using the high part?

In this lab, we have learned:

How to seed an RNG.
How to get a random value.
How to seed the RNG to give an unpredictable sequence of values.
How to populate an array with random data.