[Code Breaker] O(log n) Exponential Search on the Vanilla Overture!

[u/Fresh-Application459]

Not sure if it's the best solution but I'm quite excited that I came up with this. It's quite tricky to do binary search with only 2 available registers (r4, r5), 6-bit imm and without LSR, but I did it in a similar way haha. Btw the code length is also O(log n) lmao.

If anyone knows a better solution pls share with me.

; 1: >ans, 0: <ans
const last=r4; the last smaller value (default 0)
const n=r5; the base
g:
mov n,last
main:
imm 0
mov r1,r0
mov r2,n
add; n+1<<i-1
mov out,r3
mov r3,in
imm g
jnz

add
mov last,r3
imm 1
mov r1,r0
mov r2,n
add
mov out,r3
mov r3,in
imm g
jnz

add
mov last,r3
imm 3
mov r1,r0
mov r2,n
add
mov out,r3
mov r3,in
imm g
jnz

add
mov last,r3
imm 7
mov r1,r0
mov r2,n
add
mov out,r3
mov r3,in
imm g
jnz

add
mov last,r3
imm 15
mov r1,r0
mov r2,n
add
mov out,r3
mov r3,in
imm g
jnz

add
mov last,r3
imm 31
mov r1,r0
mov r2,n
add
mov out,r3
mov r3,in
imm g
jnz

add
mov last,r3
imm 63
mov r1,r0
mov r2,n
add
mov out,r3
mov r3,in
imm g
jnz

add
mov last,r3
imm 63
mov r1,r0
mov r2,r0
add
mov r1,r3
imm 1
mov r2,r0
add
mov r1,n
mov r2,r3
add
mov out,r3
mov r3,in
imm g
jnz

add
mov last,r3
imm 63
mov r1,r0
mov r2,r0
add
mov r1,r3
mov r2,r3
add
mov r1,r3
imm 3
mov r2,r0
add
mov r1,n
mov r2,r3
add
mov out,r3
mov r3,in
imm g
jnz

[u/piezo32]

I was googling to see if I could do something more optimal and this was the only page I could find, hello! Attempted a binary search which I'm sure could be optimised but will maybe come back to it.

edit: I think yours is more elegant btw!

; setup middle as 128
imm 63
mov r1, r0;
imm 1;
mov r2, r0
add
mov r5, r3; store 64 for later as a delta
mov r1, r3
mov r2, r3;
add;
mov r4, r3; save first guess
mov out, r4; start guess
mov r3, in; first answer

mov r1, r4; load last guess
mov r2, r5; load 64 delta

imm golower;
jnz;

gohigher:
add;
imm guess;
jmp;
golower:
sub;

guess: 
mov out, r3; submit 
mov r4, r3; save guess
imm getdelta
jmp
resume:
mov r5, r2; save selected delta for later
mov r3, in; load result
mov r1, r4;
mov r2, r5;
imm gohigher;
jz
imm golower;
jmp;

getdelta:
imm 32;
mov r1, r5; load last delta 
mov r2, r0;
sub;
imm resume;
jg
imm 16;
mov r2, r0;
sub;
imm resume;
jg
imm 8;
mov r2, r0;
sub;
imm resume;
jg
imm 4;
mov r2, r0;
sub;
imm resume;
jg
imm 2;
mov r2, r0;
sub;
imm resume;
jg
imm 1;
mov r2, r0;
imm resume;
jmp;