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

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

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

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