home *** CD-ROM | disk | FTP | other *** search
/ POINT Software Programming / PPROG1.ISO / pascal / swag / math.swg / 0086_ASM Array Min-Max Finder.pas < prev    next >
Encoding:
Pascal/Delphi Source File  |  1995-03-26  |  2.4 KB  |  89 lines
  1. {
  2. >I need to find the minimum and maximum values in large arrays (~20,000
  3. >points) of type word.  Looking for a faster way using TP7 (assembler?)
  4. >to do it than:
  5. >
  6. >min := data^[1];
  7. >max := data^[1];
  8. >
  9. >for i := 2 to num_points do
  10. >begin
  11. > data_value := data^[i];
  12. > if data_value < min then min := data_value;
  13. > if data_value > max then max := data_value;
  14. >end;
  15. >
  16. Lets try some asm here:
  17.  
  18. From: terjem@hda.hydro.com (Terje Mathisen)
  19. }
  20.  
  21. Procedure FindMinMax(var data; num_points : word; var min, max : word);
  22. Assembler;
  23. asm
  24.   push ds
  25.   lds si,[data]
  26.   mov cx,[num_points]
  27.   sub cx,1
  28.    jc @done   {Empty array! }
  29.   mov dx,[si] {Min value}
  30.   lea si,[si+2] {Point at second table entry}
  31.   mov bx,dx   {Max value}
  32.    jz @store  {Single-entry array!}
  33.  
  34. @loop:
  35.   mov ax,[si]
  36.   add si,2
  37.   cmp ax,dx
  38.    jb @new_min
  39.   cmp ax,bx
  40.    ja @new_max
  41.   dec cx
  42.    jnz @loop
  43.    jmp @store
  44.  
  45. @new_min:
  46.   mov dx,ax   {Save new min value}
  47.   dec cx
  48.    jnz @loop
  49.    jmp @store
  50.  
  51. @new_max:
  52.   mov bx,ax   {Save new max value}
  53.   dec cx
  54.    jnz @loop
  55.  
  56. @store:       {Return the values found!}
  57.   lds si,[min]
  58.   mov [si],dx
  59.   lds si,[max]
  60.   mov [si],bx
  61. @done:
  62.   pop ds
  63. end;
  64.  
  65. {
  66. This was written from scratch, so no testing whatsoever!  It should be quite
  67. well optimized for both 486 and Pentium-class machines, running in about 10
  68. cycles/word on a 486, and just 4 cycles/word on a Pentium, since the
  69. 8 inner-loop instructions will pair perfectly.  With 20,000 points in your
  70. array, this should correspond to 6ms on a 486-33, and less than a milli-
  71. second on a Pentium-90.
  72.  
  73. The most important feature to note is that new extremal values will be quite
  74. rare, averaging just O(log(n)) for a random n-element array.  That's why I
  75. jump out of the loop to handle these cases, making the normal case much
  76. faster.  With a worst-case, already sorted array, we will find a new max
  77. value on each iteration, which will increase the running time to 12 cycles
  78. on the 486, while the Pentium will stay constant at 4 cycles.
  79.  
  80. If the array is pre-sorted in reverse (declining) order, the 486 is back to
  81. 10 cycles, while the P5 is actually faster, at just 3 cycles/word.
  82.  
  83. I think the only way to improve on this code is by unrolling it, which will
  84. save up to 4 cycles/word for the 486, and just a single P5 cycle.
  85.  
  86. PS. Make sure that your array is naturally aligned (16-bit word), if not it
  87. will run a lot slower, esp. on a P5.
  88. }
  89.