Fastest way to determine the non-zero minimum

Question

Having an array of for instance 4 integers how can one determine it's non-zero minimum - in the fastest way ?

Answer 1

There is a parallel solution to this problem, but its probably not worth the effort.

First we define an operation xchg(m, n) over an array a:

xchg(m, n) => ((a[m] > a[n] && a[n] != 0) || a[m] == 0) ? swap(a[m],a[n])

This operation sorts two elements 'm' and 'n' in ascending order if they both contain non-zero values, or swaps them if the value in the 'm' element is zero.

Next we execute a set of five such operations as follows:

xchg(0,2) xchg(1,3)
xchg(0,1) xchg(2,3)
xchg(1,2)

The paired xchg operations can be executed in parallel, reducing the time cost by 40% over a strictly sequential execution. When we're finished, any non-zero elements in the array will be sorted in ascending order. The smallest-value element will be in a[0]. If that value is zero, there are no non-zero values in the array.

This solution takes advantage of the inherent parallelism provided by sorting networks ( http://en.wikipedia.org/wiki/Sorting_network), but a sequential scan of 4 elements also uses no more than three comparison operations, and crucially requires half as many storage writes on average:

sequential scan

int v = a[0]
for (n = 1; n < 4; n++) {
   if ((a[n] < v && a[n] != 0 ) || v == 0) v = a[n]
}