Monday 28 April 2008

Binary Search in Redcode

Binary search is an algorithm to find a value in a sorted list. Binary search finds the center element of the list and compares it to the target value.

If the target value is higher than the value of the center element, all elements below the center element can be eliminated from the search. Otherwise, all elements above the center element can be eliminated.

The search is then repeated on the remaining elements. In this way, binary search reduces the search space by 50% on each iteration. In Redcode, binary search is more efficient than linear search for lists of 38 or more elements.

The input parameters required are as follows:
  • size - the number of elements
  • bot - a pointer to the top of the sequence
  • find - the target value to find
A pointer to the required element is returned in ptr.
          nop    <bot,           >size
_bsnext mov.b size, ptr
div #2, ptr
jmn _bscont, ptr

mov.b bot, ptr
jmp notfound, >ptr

_bscont add.b bot, ptr
slt @ptr, find
jmp _bstopadj

add.b bot, size
sub.b ptr, size
mov.b ptr, bot
jmp _bsnext

_bstopadj sne.b @ptr, find
jmp found

div #2, size
jmp _bsnext

Sunday 20 April 2008

Write Number

Here's a short iterative routine to write a number to standard out. Although longer than the recursive algorithm, it avoids the need to maintain a data / return stack. 9x+1 cycles are required, where x is the number of digits.

The sts opcode is available in exMARS Streams.
writedec  mov    number,         temp
jmp _wdloop+1, >_wdloop

_wdloop mul #10, #0
div #10, temp
jmn _wdloop, temp

_wdprint mov number, temp
div.b _wdloop, temp
add #48, temp
sts temp, 0
mod.b _wdloop, number
div #10, _wdloop
jmn _wdprint, _wdloop

Saturday 12 April 2008

Sign v2

Shortly after publishing a five line snippet to return the sign of the input value, Roy van Rijn commented with the following improvement.

As with the original, Roy's code calculates the sign of location's b-field, returning -1, 0 or 1.

sign      jmz.b  done,           location
div #1+CORESIZE/2, location
mul.ab #-2, location
nop >location
done

Thursday 3 April 2008

Linear Search

This short snippet of code performs a linear search on a sorted list. The average time to find a value in a sequence of x cells is x+3 cycles. This outperforms binary search on sequences up to 38 cells.

If the required values isn't in the sequence, a pointer to the first higher value is returned.
lsearch   slt    >ptr,           find
jmp _lsdone
djn lsearch, #length
jmp notfound

_lsdone sne find, <ptr
jmp found
jmp notfound