On Jan 6, 2012, at 13:47, John Gilmore wrote: > > Now the comparison instructions in all of the machine architectures I > am familiar with are ternary. They make the same less-than, equal, > greater-than discrimination that signum makes. > > This has baleful consequences. The unavailability of ternary > arithmetic comparisons in C, for example led Kernighan and Ritchie to > implement binary search using the notorious sequence > > if (x < v[mid]) high = mid - 1 ; > else if (x < v[mid]) low = mid + 1 ; > else return mid ; > > that asymptotically executes twice as many comparison [machine] > instructions as it needs to execute. [It is suboptimal in other ways > too, but they are not so important.] > I suspect that most modern optimizing compilers will detect the common subexpression and the implied signum and collapse the sequence into one compare and three conditional branches.
I'd need to see the K&R snippet in more context to be confident that it was immune to overrun at the boundaries, and that it produces desired results when X is entirely outside the range and for a single-element array. Likewise, the arithmetic IF or use of a single-argument signum with two comparands requires a subtraction which may result in overflow for extreme comparand values. Finally, ISTR, but can find no references, that FORTRAN II had a two argument SGNF(X,Y) defined as the magnitude of X with the sign of Y. A plausible motivation is this was a single machine instruction on the IBM 70x series -- doubleword shift with a count of zero. -- gil
