annotate lab4/test/binsearch.p @ 0:bfdcc3820b32

Basis
author Mike Spivey <mike@cs.ox.ac.uk>
date Thu, 05 Oct 2017 08:04:15 +0100
parents
children
rev   line source
0
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
1 (* Binary search for sqrt(200000000) *)
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
2
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
3 var y, a, b, m: integer;
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
4
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
5 begin
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
6 y := 200000000;
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
7 a := 0;
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
8 b := 20000;
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
9 (* Inv: a^2 <= y < b^2 *)
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
10 while a+1 < b do
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
11 m := (a+b) div 2;
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
12 if m*m <= y then
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
13 a := m
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
14 else
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
15 b := m
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
16 end
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
17 end;
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
18 print_num(a); newline()
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
19 end.
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
20
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
21 (*<<
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
22 14142
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
23 >>*)
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
24
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
25 (*[[
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
26 @ picoPascal compiler output
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
27 .include "fixup.s"
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
28 .global pmain
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
29
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
30 .text
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
31 pmain:
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
32 mov ip, sp
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
33 stmfd sp!, {r4-r10, fp, ip, lr}
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
34 mov fp, sp
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
35 @ y := 200000000;
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
36 set r0, #200000000
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
37 set r1, _y
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
38 str r0, [r1]
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
39 @ a := 0;
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
40 mov r0, #0
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
41 set r1, _a
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
42 str r0, [r1]
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
43 @ b := 20000;
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
44 set r0, #20000
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
45 set r1, _b
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
46 str r0, [r1]
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
47 .L2:
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
48 @ while a+1 < b do
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
49 set r0, _a
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
50 ldr r4, [r0]
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
51 set r0, _b
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
52 ldr r5, [r0]
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
53 add r0, r4, #1
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
54 cmp r0, r5
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
55 bge .L4
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
56 @ m := (a+b) div 2;
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
57 mov r1, #2
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
58 add r0, r4, r5
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
59 bl int_div
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
60 set r1, _m
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
61 str r0, [r1]
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
62 @ if m*m <= y then
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
63 mul r1, r0, r0
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
64 set r2, _y
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
65 ldr r2, [r2]
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
66 cmp r1, r2
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
67 bgt .L6
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
68 @ a := m
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
69 set r1, _a
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
70 str r0, [r1]
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
71 b .L2
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
72 .L6:
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
73 @ b := m
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
74 set r0, _m
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
75 ldr r0, [r0]
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
76 set r1, _b
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
77 str r0, [r1]
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
78 b .L2
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
79 .L4:
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
80 @ print_num(a); newline()
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
81 set r0, _a
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
82 ldr r0, [r0]
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
83 bl print_num
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
84 bl newline
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
85 ldmfd fp, {r4-r10, fp, sp, pc}
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
86 .ltorg
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
87
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
88 .comm _y, 4, 4
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
89 .comm _a, 4, 4
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
90 .comm _b, 4, 4
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
91 .comm _m, 4, 4
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
92 @ End
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
93 ]]*)