**[**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**]**