## Jupyter at Bryn Mawr College

Public notebooks: /services/public/dblank / CS240 Computer Organization / 2015-Fall / Notes

# Randomness in LC-3¶

## Schrage's method¶

In [5]:
.ORIG x3000
;;; Algorithm for the iteration x <- a x mod m
;;; using Schrage's method

JSR Random
;; look in R1 for a pseudo-random value; call Random again to iterate through them
HALT

;;; -----------------------------------------------------
;;; Memory X has next random number
Random: ST R7,BACK  ; save return location
LD R0, M
LD R1, A
JSR Divide          ; R0 / R1
;; q = m / a
LD R0, QUOTIENT     ; R0 / R1
ST R0, Q
;; r = m mod a
LD R0, REMAINDER    ; R0 mod R1
ST R0, R
;; x / q
LD R0, X
LD R1, Q
JSR Divide          ; R0 / R1
LD R1, QUOTIENT
ST R1, TEMP2
LD R1, REMAINDER    ; x mod q
ST R1, TEMP1
;; x â†  a âˆ—  (x mod q) âˆ’ r âˆ—  (x / q)
;;      a * TEMP1 - r * TEMP2
LD R0, A
JSR Multiply        ; R2 <- R0 * R1
ST R2, TEMP1
;;      a * TEMP1 - r * TEMP2
LD R0, R
LD R1, TEMP2
JSR Multiply        ; R2 <- r * TEMP2
NOT R2,R2           ; -R2
ST R2, TEMP2
LD R1, TEMP1
ADD R2, R2, R1      ; TEMP1 - TEMP2
TEST:  BRzp DONE        ; if x < 0 then
LD R1, M
ADD R2, R2, R1      ; x â†  x + m
DONE: ST R2, X
LD R7, BACK         ; Restore return address
RET
A: .FILL #7             ;; a , the multiplicative constant is given
M: .FILL #32767         ;; m = 2 Ë† 15 âˆ’ 1, the modulus is given
X: .FILL #10            ;; x, the seed is given
R: .FILL #0
Q: .FILL #0
TEMP1: .FILL #0
TEMP2: .FILL #0
BACK: .FILL #0

;;; -----------------------------------------------------
;;; R2 <- R0 * R1
;;; Also uses R3 to store SIGN
Multiply: AND R2,R2,#0
AND R3,R3,#0
BRn MultNEG1
BR  MultCont
MultNEG1: NOT R3,R3 		; flip SIGN
NOT R0,R0
MultCONT: ADD R1,R1,#0 		; compare R1
BRn MultNEG2
BR MultInit
MultNEG2: NOT R3,R3 		; flip SIGN
NOT R1,R1
MultInit: ADD R0,R0,#0  	; have R0 set the condition codes
MultLoop: BRz MultDone
BR MultLoop
BRzp MultRet
NOT R2,R2
MultRet:  RET			; R2 has the sum

;;; -----------------------------------------------------
;;; R0 / R1
;;; Also uses R3 to store SIGN
;;;           R4 to store -R1
;;;           R5 is QUOTIENT
;;;           R6 is REMAINDER
;;;           R2 temp
Divide:   AND R3,R3,#0
ST R3, QUOTIENT
ST R3, REMAINDER
BRn DivNEG1
BR  DivCont
DivNEG1:  NOT R3,R3 		; flip SIGN
NOT R0,R0
DivCONT:  ADD R1,R1,#0 		; compare R1
BRn DivNEG2
BR DivInit
DivNEG2:  NOT R3,R3 		; flip SIGN
NOT R1,R1
NOT R4,R4
DivLoop:  ADD R2,R0,R4  	; have R2 set the condition codes
BRn DivDone
LD R2,QUOTIENT
ST R2,QUOTIENT
BR DivLoop
BRzp DivRet
LD R2,QUOTIENT 	; Yes, then negate R2
NOT R2,R2
ST R2,QUOTIENT
DivRet:	  ST R0,REMAINDER
RET			; R2 has the sum
QUOTIENT: .FILL #0
REMAINDER: .FILL #0
.END

Assembled! Use %dis or %dump to examine.

In [6]:
%exe

============================================================
Computation completed
============================================================
Instructions: 32889
Cycles: 230203 (0.115101 milliseconds)

============================================================
Registers:
============================================================
PC: x048E
N: 0 Z: 0 P: 1
R0: x0000 R1: x0046 R2: x0046 R3: x0000
R4: xEDB7 R5: x0000 R6: x0000 R7: x3002