The arithmetic function that mathematicians call signum, viz., for an arithmetic expression x
signum(x) = -1, a < 0, signum(x) = 0, a = 0, signum(x) = +1, a > 0 is available as a BIF called sign in PL/I, where it is [almost always] implemented in line. An analogous function is available for strings in C, where it is implemented as a library subroutine. It has always been available in FORTRAN in the form of the much deprecated but in fact enormously useful arithmetic-IF statement When it is implemented in statement-level procedural languages each iteration of a binary search typically makes a second binary comparison iff a first one fails. There is an optimal ordering of these comparisons, which depends upon how middling subscript values are calculated, but the details are probably TMI here. For the modestly suboptimal case in which the search argument is compared first with a current middling table element for equality, it is clear that two comparisons---binary ones implemented at the machine-code level as specialized ternary ones--are executed for all but the last iteration of successful searches, of which there are n. For most SLPL implementations Knuth's M(n) thus becomes something like M*(n) = 2M(n) - n The number of comparison operations--This number for the usual 2n + 1q search arguments is Knuth's figure of merit for binary-search schemes--is thus roughly doubled. The availability of a ternary comparison is thus very important for binary-search performance. (This issue is often, even usually, fudged in programmjing texts for ideological reasons. Ternary-comparison operations are judged to be 'unstructured', even 'anarchic' by many academics. In fact some uses of them are and some are not; but this distinction is judged oversubtle for their students.) No optimizing compiler rhat I am familiar, including the current shared C and PL/I optimizer, collapses sequences of binary comparisons into a smaller number of ternary ones; and this would be difficult to do in general, although compact special cases like those that occur typically in binary-search routines are probably tractable. John Gilmore, Ashland, MA 01721 - USA
