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