[Back to MATH SWAG index]  [Back to Main SWAG index]  [Original]

{
>I need to find the minimum and maximum values in large arrays (~20,000
>points) of type word.  Looking for a faster way using TP7 (assembler?)
>to do it than:
>
>min := data^[1];
>max := data^[1];
>
>for i := 2 to num_points do
>begin
> data_value := data^[i];
> if data_value < min then min := data_value;
> if data_value > max then max := data_value;
>end;
>
Lets try some asm here:

From: terjem@hda.hydro.com (Terje Mathisen)
}

Procedure FindMinMax(var data; num_points : word; var min, max : word);
Assembler;
asm
  push ds
  lds si,[data]
  mov cx,[num_points]
  sub cx,1
   jc @done   {Empty array! }
  mov dx,[si] {Min value}
  lea si,[si+2] {Point at second table entry}
  mov bx,dx   {Max value}
   jz @store  {Single-entry array!}

@loop:
  mov ax,[si]
  add si,2
  cmp ax,dx
   jb @new_min
  cmp ax,bx
   ja @new_max
  dec cx
   jnz @loop
   jmp @store

@new_min:
  mov dx,ax   {Save new min value}
  dec cx
   jnz @loop
   jmp @store

@new_max:
  mov bx,ax   {Save new max value}
  dec cx
   jnz @loop

@store:       {Return the values found!}
  lds si,[min]
  mov [si],dx
  lds si,[max]
  mov [si],bx
@done:
  pop ds
end;

{
This was written from scratch, so no testing whatsoever!  It should be quite
well optimized for both 486 and Pentium-class machines, running in about 10
cycles/word on a 486, and just 4 cycles/word on a Pentium, since the
8 inner-loop instructions will pair perfectly.  With 20,000 points in your
array, this should correspond to 6ms on a 486-33, and less than a milli-
second on a Pentium-90.

The most important feature to note is that new extremal values will be quite
rare, averaging just O(log(n)) for a random n-element array.  That's why I
jump out of the loop to handle these cases, making the normal case much
faster.  With a worst-case, already sorted array, we will find a new max
value on each iteration, which will increase the running time to 12 cycles
on the 486, while the Pentium will stay constant at 4 cycles.

If the array is pre-sorted in reverse (declining) order, the 486 is back to
10 cycles, while the P5 is actually faster, at just 3 cycles/word.

I think the only way to improve on this code is by unrolling it, which will
save up to 4 cycles/word for the 486, and just a single P5 cycle.

PS. Make sure that your array is naturally aligned (16-bit word), if not it
will run a lot slower, esp. on a P5.
}

[Back to MATH SWAG index]  [Back to Main SWAG index]  [Original]