LC$-3$: Random Number Generator $(50$ points$)$

Random numbers are an important concept in computer science because they are often used

to simulate real$-$world events. For example, in a game of chance, random numbers are used to

determine the outcome of the game. In a computer simulation, random numbers are used to model

the uncertainty of the system being simulated. Additionally, random numbers are used in many

security applications, such as generating secure cryptographic keys and simulating user behaviour

for testing purposes. Overall, the ability to generate random numbers allows computers to model

and analyse complex, uncertain systems, making them a fundamental tool in computer science.

However, computers can$$t just randomly generate numbers. They can make use of events of nature

that appear to be random $($or at least, infeasibly hard to trace a pattern$),$ but what also happens

regularly is that they use so$-$called pseudo$-$random number generators. An example of such a

pseudo$-$random number generator where each number can be defined from the previous number can

be seen in Equation $1,$ given the three non$-$negative integers a$,$ b$,$ and m$.$

Xn $=($aXn$1+$ b$)$ mod m $(1)$

$3$

Computer Architecture Homework $5$

Lastly, we need to define the initial number, X$0.$ For this, computers usually take some noise, like

the current time, but for your case, we will provide you with some artificial noise in the form of a

few random characters $($or maybe a few dozen$).$ Another name for this initial number X$0$ is the seed.

Input Details

The first line of the input consists of three non$-$negative integer numbers a$,$ b and m; these are

represented using the normal decimal system. Note that these numbers are separated$/$surrounded

by spaces or new lines, therefore the inputs

$1234$

and

$12$

$3$

$4$

and

$12$

$34$

are all valid, equivalent inputs.

After the three numbers a$,$ b$,$ and m have been read, there will be a line break followed by any

number of characters, which will represent the seed X$0.$ For each character, treat letters as their

index in the alphabet $($starting from $0),$ and digits like numbers. All other characters can $($and

should$)$ be ignored. In other words, you may treat these as $0.$ The sequence of characters ends with

a new line. Note that there is no new line in the seed line. As an example, if we have the seed

$,9$d$23$a$569.,,$ we can deduce the following:

$,9$ d $23$ a $569.,$

$----------------------$

$09323056900$

The seed X$0$ is then obtained by taking the sum of all the valid characters. In our example, we have

$0+9+3+2+3+0+5+6+9+0+0=37.$

Example noise could be:

abbH$23$ sa $^^651$d

or

$5663$a

The final line of the input will contain a non$-$negative integer n $($represented using decimal notation$),$

which you should use to print X$1,$ X$2,...,$ Xn separated by a single new line. You should not

print X$0!$ So if the input is$,$ for example

$3$

$4$

Computer Architecture Homework $5$

you should print

X$\_1$

X$\_2$

X$\_3$

These numbers must be printed in hexadecimal form, and they must start with an x$.$ You should

use capital letters and not print any leading zeroes. For example, instead of x$00$d$5$f you should

print xD$5$F$.$

Moreover, be sure to print a new line after the last number Xn as well!

Input$/$Output Example

Input

$2325$

aaabbbccc$^^1$

$4$

should print the output

x$17$

x$18$

x$1$

x$5$

In this case, we see that a $=2,$ b $=3,$ m $=25,$ and the seed X$0$ equals $10($X$0=0+0+0+1+1+$

$1+2+2+2+1=10).$ Since n $=4,$ we print X$1,$ X$2,$ X$3,$ X$4$ and print a new line character after

each.

In a real application, the user would like to see what they type. Therefore, you must also print

every inputted character. This is easily accomplished by using the OUT instruction after every GETC.

Notice that you should not use the IN command because then you get the $$Input a character$>$

message each time, which is obviously undesirable.

Implementation Hints

You have learned about subroutines in the tutorial. They can make your journey much more

pleasant, so consider using them. Also make sure document the subroutines for clarity. A simple

LC$3$ template containing a subroutine is given below:

$5$

Computer Architecture Homework $5$

$.$ORIG x$3000$

MAIN

LD R$2,$ MODULO$\_$ROUTINE$\_$PTR

JSRR R$2$

HALT

; data

MODULO$\_$ROUTINE$\_$PTR $.$FILL MODULO$\_$ROUTINE

END$\_$MAIN

;$=====================================================$

; Description: does a thing

; $-$ parameters: R$1$: contains something

; R$2$: contains something else

; $-$ post condition: R$4$: contains something else else

;$=====================================================$

MODULO$\_$ROUTINE

;

RET

; data

END$\_$MODULO$\_$ROUTINE

$.$END

Lastly, don$$t forget that your LC$-3$ programs must always start with $.$ORIG x$3000.$