- no title specified

Analysis

 

 

 

 

 

 

 

 

 

 

 

 

 

Implementation

 

 

 

DIVISOR ← INPUT

DIVIDEND ← INPUT

ASSERT DIVIDEND ≥ DIVISOR

 

diff ← DIVISOR

 

WHILE diff 0:

    diff ← diff – DIVIDEND

 

diff ← diff + DIVIDEND

 

RETURN diff

 

 

 

start   LDA mod_r

        BRP end

        BRA mod

end     OUT

        HLT

 

mod     LDA mod_a1

mod_p   SUB mod_a2

        BRP mod_p

        ADD mod_a2

        STO mod_r

        BRA start

 

mod_a1  DAT 997

mod_a2  DAT 5

mod_r   DAT -1

 

 

 

M ← INPUT

N ← INPUT

OUT ← 0

COUNTER ← M - 1

 

WHILE COUNTER 0:

        OUT ← OUT + N

        COUNTER ← COUNTER - 1

 

RETURN M

 

 

 

start   LDA mul_r

        BRP cont

        BRA mul

        LDA mul_r

        OUT

        HLT

 

mul     LDA mul_a2

        STO mul_c2

        LDA mul_a1

        SUB mul_s

        STO mul_c1

mul_p   LDA mul_a2

        ADD mul_c2

        STO mul_c2

        LDA mul_c1

        SUB mul_s

        STO mul_c1

        BRP mul_p

        LDA mul_c2

        SUB mul_a2

        STO mul_r

        BRA         start

 

mul_a1  DAT 4

mul_a2  DAT 10

mul_c1  DAT -1

mul_c2  DAT -1

mul_s   DAT 1

mul_r   DAT -1

 

 

 

 

 

 

start   LDA mul_r

        BRP cont

        BRA mul

cont           LDA mul_r

        OUT

        HLT

 

mul     LDA mul_a2

        STO mul_c2

        LDA mul_a1

        SUB mul_s

        STO mul_c1

mul_p   LDA mul_a2

        ADD mul_c2

        STO mul_c2

        LDA mul_c1

        SUB mul_s

        STO mul_c1

        BRZ mul_end

        BRA mul_p

mul_end LDA mul_c2

        STO mul_r

        BRA         start

 

mul_a1  DAT 4

mul_a2  DAT 10

mul_c1  DAT -1

mul_c2  DAT -1

mul_s   DAT 1

mul_r   DAT -1

 

 

 

 

 

; -- snip --

mul_p   LDA mul_a2

        ADD mul_r

        STO mul_r

        LDA mul_c1

        SUB mul_s

        STO mul_c1

        BRZ start

        BRA mul_p

; -- snip --

 

 

mul     LDA mul_a2

        STO mul_r

mul_p   LDA mul_a1

        SUB mul_s

        STO mul_a1

        BRZ start

        LDA mul_a2

        ADD mul_r

        STO mul_r

        BRA mul_p

 

 

 

 

rand ← 1

LOOP:

        part1 ← MULTIPLY(rand, 505)

        rand ← MOD(part1, 997)

       

        YIELD rand

       

 

 

start   LDA rand

        STO mul_a1

        BRA mul

mul_e   LDA mul_r

        STO mod_a1

        BRA mod

mod_e   LDA mod_r

        OUT

        STO rand

        BRA start

 

 

start   LDA rand

        STO mul_a1

        BRA mul

mul_e   LDA mul_r

        BRP cont

        ADD big

cont    STO mod_a1

        BRA mod

mod_e   LDA mod_r

        OUT

        STO rand

        BRA start

       

big     DAT 999

 

 

start   LDA mul_a2

        STO mul_r

 

mul_p   LDA rand

        SUB mul_s

        STO rand

        BRZ mul_e

        LDA mul_a2

        ADD mul_r

        STO mul_r

        BRA mul_p

 

mul_e   LDA mul_r

mod_p   SUB mod_a2

        BRP mod_p

        ADD mod_a2

        OUT

        STO rand

        BRA start

 

rand    DAT 1

mod_a2  DAT 997

mod_r   DAT -1

mul_a2  DAT 505

mul_s   DAT 1

mul_r   DAT -1

 

 

Seed

1

2

3

4

5

6

7

8

9

10

11

12

Value

505

13

518

21

526

34

539

42

547

55

560

63

Change

+504

+11

+515

+17

+521

+28

+532

+36

+538

+45

+549

+51

 

 

 

Seed

1

505

155

314

649

911

285

2

13

568

983

663

Value

505

155

314

649

911

285

2

13

568

983

663

982

Change

+504

-350

+159

335

262

-626

-283

+11

+555

+415

-320

+319

       

 

Evaluation

 

 

 

 

 

 

gap correlation by lagging the results from each other:

 

 

 

 

 
 

Exam Style Q:

 

 

Two different random number LCG algorithms with ‘m’ values of 997 produce the following sequences:

 

1

505

155

314

649

911

285

2

13

568

983

663

982

 

1

987

161

155

143

120

12

927

160

154

144

120

12

 

 

927, 160

The second algorithm is modified to produce the following sequence:

 

1

527

361

455

343

322

415

360

554

344

417

399

464

 

 

The first, since the IQR spans approximately half the range of the resuts. On the second algorithm, the IQR is much tighter.

        Part of the algorithm responsible for the top sequence looks like so:

 

 

f1  LDA a1

f2  SUB a2

     BRP f2

     ADD a2

     STO res

 

a1  DAT 505

a2  DAT 997

res         DAT -1

 

Jump to the specified instruction if the accumulator is holding a positive value.

 

The algorithm calculates the remainder of a1 and a2, and then stores it in the position labelled ‘res’