NAG FL Interface
m01ndf (realvec_vec_search)
1
Purpose
m01ndf searches a strictly ordered vector of real numbers and returns the indices of the largest numbers in the vector which are smaller than or equal to the soughtafter items.
2
Specification
Fortran Interface
Subroutine m01ndf ( 
valid, mode, rv, n, m1, m2, item, m, idx, h, k, lk, ifail) 
Integer, Intent (In) 
:: 
mode, n, m1, m2, m 
Integer, Intent (Inout) 
:: 
k(lk), lk, ifail 
Integer, Intent (Out) 
:: 
idx(m) 
Real (Kind=nag_wp), Intent (In) 
:: 
rv(n), item(m) 
Real (Kind=nag_wp), Intent (Inout) 
:: 
h 
Logical, Intent (In) 
:: 
valid 

C Header Interface
#include <nag.h>
void 
m01ndf_ (const logical *valid, const Integer *mode, const double rv[], const Integer *n, const Integer *m1, const Integer *m2, const double item[], const Integer *m, Integer idx[], double *h, Integer k[], Integer *lk, Integer *ifail) 

C++ Header Interface
#include <nag.h> extern "C" {
void 
m01ndf_ (const logical &valid, const Integer &mode, const double rv[], const Integer &n, const Integer &m1, const Integer &m2, const double item[], const Integer &m, Integer idx[], double &h, Integer k[], Integer &lk, Integer &ifail) 
}

The routine may be called by the names m01ndf or nagf_sort_realvec_vec_search.
3
Description
m01ndf searches an array, $X$, of $n$ strictlyincreasing real numbers, ${X}_{i}<{X}_{i+1}$, $i=1\dots \left(n1\right)$, for the elements of an unordered array of $m$ real numbers, $Z$. If a value equal to a soughtafter item ${Z}_{i}$ is not found in $X$, the index of the immediate lower value is returned. If ${Z}_{i}$ is less than ${X}_{1}$, $0$ is returned.
The routine implements the direct search algorithm presented as Algorithm 8 in
Cannizzo (2018). It precomputes a scalar,
$H$, and a reference vector of indices,
$K$, that it uses to speed up searches of
$X$. The length of
$K$ is a function of the number of entries in
$X$ and their values, and the routine provides a mechanism to compute what this length should be.
If the amount of memory required for
$K$ is infeasible,
m01ndf
implements offsetbased binary search (Algorithm 5 in
Cannizzo (2018)) as an alternative that does not require
$K$ to be used.
See
Section 9 for more information on the relative time complexities of the two search algorithms.
4
References
Cannizzo F (2018) A fast and vectorizable alternative to binary search in O(1) with wide applicability to arrays of floating point numbers Journal of Parallel and Distributed Computing 113 37–54
5
Arguments

1:
$\mathbf{valid}$ – Logical
Input

On entry: if
valid is set to .TRUE. argument checking will be performed. If
valid is set to .FALSE.
m01ndf will be called without argument checking (which includes checking that array
rv is sorted in strictly ascending order). See
Section 9 for further details.

2:
$\mathbf{mode}$ – Integer
Input

On entry: a code for selecting the operation to be performed by the routine. The first call to
m01ndf must be made with
${\mathbf{mode}}=0$, and this must be followed by a second call with
${\mathbf{mode}}=1$. Thereafter repeated searches of
rv can be made through repeated calls with
${\mathbf{mode}}=2$.
 ${\mathbf{mode}}=0$
 Compute h and lk. Following a call with ${\mathbf{mode}}=0$, k must be allocated to hold lk elements and then the routine must be called again with ${\mathbf{mode}}=1$.
 ${\mathbf{mode}}=1$
 Set up k (the reference vector) using the values of h and lk returned from a prior call to m01ndf with ${\mathbf{mode}}=0$.
 ${\mathbf{mode}}=2$
 Direct search using h and k set up in prior calls to m01ndf with ${\mathbf{mode}}=0$ or $1$.
 ${\mathbf{mode}}=3$
 Search using offsetbased binary search, which does not require h or k to be used.
Constraint:
${\mathbf{mode}}=0$, $1$, $2$ or $3$.

3:
$\mathbf{rv}\left({\mathbf{n}}\right)$ – Real (Kind=nag_wp) array
Input

On entry: $X$, the real values to be searched.
Constraint:
elements of
rv must be sorted in strictly ascending order.

4:
$\mathbf{n}$ – Integer
Input

On entry: $n$, the number of real values to be searched.
Constraint:
${\mathbf{n}}\ge 2$.

5:
$\mathbf{m1}$ – Integer
Input

On entry: the index of the first element of
rv to be searched.
Constraint:
${\mathbf{m1}}\ge 1$.

6:
$\mathbf{m2}$ – Integer
Input

On entry: the index of the last element of
rv to be searched.
Constraint:
${\mathbf{m1}}\le {\mathbf{m2}}\le {\mathbf{n}}$.

7:
$\mathbf{item}\left({\mathbf{m}}\right)$ – Real (Kind=nag_wp) array
Input

On entry: $Z$, the soughtafter items.

8:
$\mathbf{m}$ – Integer
Input

On entry: $m$, the number of items sought.
Constraint:
${\mathbf{m}}\ge 1$.

9:
$\mathbf{idx}\left({\mathbf{m}}\right)$ – Integer array
Output

On exit: if
${\mathbf{mode}}\ne 0$,
${\mathbf{idx}}\left(i\right)$ contains the index of the largest entry in
rv which is smaller than or equal to
${\mathbf{item}}\left(i\right)$.

10:
$\mathbf{h}$ – Real (Kind=nag_wp)
Communication Array

On entry:
$H$, the reference scalar required by the direct search algorithm. If
${\mathbf{mode}}=0$,
m01ndf calculates the value of
h required by the direct search routine for the given values in
rv. Otherwise, the value of
h as declared in the (sub)routine from which
m01ndf is called. If
${\mathbf{mode}}=0$,
h is not referenced.
On exit: the value of
h required by the direct search routine for the given values in
rv.
Constraint:
if
${\mathbf{mode}}=1$ or
$2$,
h must be unchanged from the previous call to
m01ndf.

11:
$\mathbf{k}\left({\mathbf{lk}}\right)$ – Integer array
Communication Array

On entry: if
${\mathbf{mode}}=2$,
k, the reference vector from the previous call to
m01ndf. If
${\mathbf{mode}}=0$ or
$3$,
k is not referenced.
On exit: if ${\mathbf{mode}}=1$ or $2$, the reference vector.
Constraint:
if
${\mathbf{mode}}=2$,
k must be unchanged from the previous call to
m01ndf.

12:
$\mathbf{lk}$ – Integer
Input/Output

On entry: if
${\mathbf{mode}}=0$,
m01ndf calculates the dimension of
k required by the direct search routine for the given values in
rv. Otherwise, the dimension of the array
k as declared in the (sub)routine from which
m01ndf is called. If
${\mathbf{mode}}=3$,
lk is not referenced.
On exit: if
${\mathbf{mode}}=0$, the dimension of the array
k required by the direct search routine for the given values in
rv. Otherwise, the dimension of the array
k as declared in the (sub)routine from which
m01ndf is called.
Constraint:
if
${\mathbf{mode}}=1$ or
$2$,
lk must be unchanged from the previous call to
m01ndf.

13:
$\mathbf{ifail}$ – Integer
Input/Output

On entry:
ifail must be set to
$0$,
$1\text{or}1$. If you are unfamiliar with this argument you should refer to
Section 4 in the Introduction to the NAG Library FL Interface for details.
For environments where it might be inappropriate to halt program execution when an error is detected, the value
$1\text{or}1$ is recommended. If the output of error messages is undesirable, then the value
$1$ is recommended. Otherwise, if you are not familiar with this argument, the recommended value is
$0$.
When the value $\mathbf{1}\text{or}\mathbf{1}$ is used it is essential to test the value of ifail on exit.
On exit:
${\mathbf{ifail}}={\mathbf{0}}$ unless the routine detects an error or a warning has been flagged (see
Section 6).
6
Error Indicators and Warnings
If on entry
${\mathbf{ifail}}=0$ or
$1$, explanatory error messages are output on the current error message unit (as defined by
x04aaf).
Errors or warnings detected by the routine:
 ${\mathbf{ifail}}=1$

On entry, ${\mathbf{mode}}=\u2329\mathit{\text{value}}\u232a$.
Constraint: ${\mathbf{mode}}=0$, $1$, $2$ or $3$.
 ${\mathbf{ifail}}=2$

On entry,
rv must be sorted in strictly ascending order:
${\mathbf{rv}}\text{ element}\u2329\mathit{\text{value}}\u232a>\text{ element}\u2329\mathit{\text{value}}\u232a$.
 ${\mathbf{ifail}}=3$

On entry, ${\mathbf{m1}}=\u2329\mathit{\text{value}}\u232a$.
Constraint: ${\mathbf{m1}}\ge 1$.
 ${\mathbf{ifail}}=4$

On entry, ${\mathbf{m1}}=\u2329\mathit{\text{value}}\u232a$, ${\mathbf{m2}}=\u2329\mathit{\text{value}}\u232a$, ${\mathbf{n}}=\u2329\mathit{\text{value}}\u232a$.
Constraint: ${\mathbf{m1}}\le {\mathbf{m2}}\le {\mathbf{n}}$.
 ${\mathbf{ifail}}=5$

On entry, ${\mathbf{n}}=\u2329\mathit{\text{value}}\u232a$.
Constraint: ${\mathbf{n}}\ge 2$.
 ${\mathbf{ifail}}=6$

On entry, ${\mathbf{m}}=\u2329\mathit{\text{value}}\u232a$.
Constraint: ${\mathbf{m}}\ge 1$.
 ${\mathbf{ifail}}=7$

On entry, the values in
rv are such that the required value of
lk would
overflow the current platform's largest positive integer value. This error
should only appear when
m01ndf is called with
${\mathbf{mode}}=0$
(i.e., when the routine is asked to calculate the required value of
lk for the given
rv).
 ${\mathbf{ifail}}=8$

Either
m01ndf was not called with
${\mathbf{mode}}=0$ or
$1$,
or the values of
h,
k or
lk may have become corrupted.
 ${\mathbf{ifail}}=99$
An unexpected error has been triggered by this routine. Please
contact
NAG.
See
Section 7 in the Introduction to the NAG Library FL Interface for further information.
 ${\mathbf{ifail}}=399$
Your licence key may have expired or may not have been installed correctly.
See
Section 8 in the Introduction to the NAG Library FL Interface for further information.
 ${\mathbf{ifail}}=999$
Dynamic memory allocation failed.
See
Section 9 in the Introduction to the NAG Library FL Interface for further information.
7
Accuracy
Not applicable.
8
Parallelism and Performance
m01ndf is threaded by NAG for parallel execution in multithreaded implementations of the NAG Library.
Please consult the
X06 Chapter Introduction for information on how to control and interrogate the OpenMP environment used within this routine. Please also consult the
Users' Note for your implementation for any additional implementationspecific information.
The argument
valid should be used with caution. Set it to .FALSE. only if you are confident that the other arguments are correct, in particular that array
rv is in fact arranged in strictly ascending order. If you wish to search the same array
rv many times, you are recommended to set
valid to .TRUE. on the first call of
m01ndf and to .FALSE. on subsequent calls, in order to minimize the amount of time spent checking
rv, which may be significant if
rv is large.
The time taken by
m01ndf to construct the reference vector (i.e., when the routine is called with
${\mathbf{mode}}=1$) is
$\mathit{O}\left(n\right)$. Note that the values stored in
k depend on all entries of
rv, and not just those in the interval
$\left[{\mathbf{m1}},{\mathbf{m2}}\right]$. Thereafter, searching for
m items using direct search (i.e., when the routine is called with
${\mathbf{mode}}=2$) is
$\mathit{O}\left(m\right)$. In contrast offsetbased binary search (i.e., when the routine is called with
${\mathbf{mode}}=3$), does not require construction of the reference vector and has time complexity
$\mathit{O}\left(m\hspace{0.17em}\mathrm{log}\left(n\right)\right)$. Although this is the same as classical binary search, offsetbased binary search may be faster in practice because the implementation does not feature conditional branches. Direct search is preferable when the overhead of constructing the reference vector can be offset by conducting multiple searches on an unchanged
rv.
10
Example
This example reads a list of real numbers and a list of soughtafter items and performs the search for these items. The example demonstrates how to use m01ndf for both direct search (i.e., ${\mathbf{mode}}=2$) and offsetbased binary search (${\mathbf{mode}}=3$).
10.1
Program Text
10.2
Program Data
10.3
Program Results