Slicing two-dimensional arrays

[Richard Russell]

As another (artificial) example of the power of array slicing, here's a procedure which will find the maximum value in an integer array, without using any comparisons and without looping over every element in the array! As coded it's limited to power-of-two-size arrays:

Code: Select all

      DEF FNmaximum(a%())
      LOCAL N%, u%(), v%() : N% = DIM(a%(),1)
      DIM u%(N% >> 1), v%(N% >> 1)
      REPEAT
        N% = N% >> 1
        v%(0 TO N%) = a%(0 TO N%) - a%(N%+1 TO 2*N%+1)
        u%(0 TO N%) = v%(0 TO N%) AND &80000000
        u%(0 TO N%) = u%(0 TO N%) DIV &7FFFFFFF
        v%(0 TO N%) = v%(0 TO N%) + u%(0 TO N%) EOR u%(0 TO N%)
        a%(0 TO N%) = a%(0 TO N%) + a%(N%+1 TO 2*N%+1) + v%(0 TO N%)
        a%(0 TO N%) DIV= 2
      UNTIL N% = 0
      = a%(0)

The way it works is to replace the first half of the array with the maximum of the first and second halves. It then iteratively repeats this, halving the size each time, until only a single element is left! That is then the maximum value in the entire array.

You might like to try to understand the code. If you can think of a way of simplifying or improving it, I would be very interested.

I should point out that it has little practical application, other than a demonstration, because it's barely any faster than the naïve approach of looping over all the elements, comparing each with the current maximum.

[Richard Russell]

I feel I'm not altogether succeeding in persuading people of the value of array slicing, so here's another example. Consider filtering a one-dimensional signal (it might perhaps be PCM audio) using a Finite Impulse Response filter, one of the most common and versatile signal-processing algorithms: used for low-pass filtering, band-pass filtering, multi-band filtering and more.

The filter kernel itself can very conveniently be implemented as an array dot-product, but in standard BBC BASIC you would have to copy the 'window' of input samples, on which you want to perform the filtering, to a separate array first - and then repeat that for every single output sample! With array slicing no copying is necessary, you can directly apply the filter kernel to a slice of the input signal.

So if the input signal is in a single, large, one-dimensional array in() and the filter coefficients are in the array lpf() (assumed here to have 17 taps) you end up with something like this; out() is a single-element array declared as DIM out(0):

Code: Select all

      FOR I% = 8 TO DIM(in(),1)-8
        out() = in(I%-8 TO I%+8) . lpf()
        REM Do something with out(0)
      NEXT

This is much more elegant, and should be much faster, than anything possible with standard BBC BASIC.

[Richard Russell]

I am being extra cautious in the release of versions of BBC BASIC supporting array slicing, for fear of introducing a bug or unwanted behaviour (sadly much more likely than it once would have been because of my condition). I have therefore today released an update to the Console Mode editions (BBCTTY) only so that it can be tested there before I update BBCSDL or BB4W.

Please download the relevant Console Mode edition for your platform(s) from here and test the array functionality as thoroughly as you can (both 'standard' array operations - lest they have been accidentally affected - and array slicing). I would appreciate feedback, whether it is positive or negative. All the editions come with the median.bbc example program which uses array slicing.

As well as reports on functionality, I would also value confirmation that you understand what array slicing is and why it can be valuable. I do worry that some BBC BASIC users operate in something of a 'bubble' in which they don't take much of an interest in other languages and dialects, and therefore don't know what they are missing. I am the complete opposite!