Jupyter at Bryn Mawr College
Public notebooks: /services/public/dblank / CS240 Computer Organization / 2015-Fall / Notes

Randomness in LC-3

Schrage's method

.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
    ADD R2,R2,#1
    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
  ADD R0,R0,#0 		; compare R0
  BRn MultNEG1
  BR  MultCont
MultNEG1: NOT R3,R3 		; flip SIGN
  NOT R0,R0
  ADD R0,R0,#1
MultCONT: ADD R1,R1,#0 		; compare R1
  BRn MultNEG2
  BR MultInit
MultNEG2: NOT R3,R3 		; flip SIGN
  NOT R1,R1
  ADD R1,R1,#1
MultInit: ADD R0,R0,#0  	; have R0 set the condition codes
MultLoop: BRz MultDone
  ADD R2,R2,R1
  ADD R0,R0,#-1
  BR MultLoop
MultDone: ADD R0,R3,#0
  BRzp MultRet
  NOT R2,R2
  ADD R2,R2,#1
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
  ADD R0,R0,#0 		; compare R0
  BRn DivNEG1
  BR  DivCont
DivNEG1:  NOT R3,R3 		; flip SIGN
  NOT R0,R0
  ADD R0,R0,#1
DivCONT:  ADD R1,R1,#0 		; compare R1
  BRn DivNEG2
  BR DivInit
DivNEG2:  NOT R3,R3 		; flip SIGN
  NOT R1,R1
  ADD R1,R1,#1
DivInit:  ADD R4,R1,#0
  NOT R4,R4
  ADD R4,R4,#1
DivLoop:  ADD R2,R0,R4  	; have R2 set the condition codes
  BRn DivDone
  ADD R0,R0,R4
  LD R2,QUOTIENT
  ADD R2,R2,#1
  ST R2,QUOTIENT
  BR DivLoop
DivDone:  ADD R3,R3,#0 		; Negative?
  BRzp DivRet
  LD R2,QUOTIENT 	; Yes, then negate R2
  NOT R2,R2
  ADD R2,R2,#1
  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.

%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