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