Best search algorithm to find condition within a range

[Marko Rauhamaa]

Chris Angelico <rosuav at gmail.com>:

> For low-level bit manipulation work, you usually want an *unsigned*
> integer of specific size, with well defined wrap-around behaviour.
> When do you actually want a signed integer with well-defined overflow
> behaviour?

Bit manipulation is not the issue here.

The reason for signed, wrapping integers is that you want to be able to
perform signed subtractions. Consider for example time differences that
are often expressed as signed second and/or nanosecond counts that are
at the brink of overflowing. You want to be able to perform usual
arithmetic operations even if the intermediate results overflow.

A classic analogy: the roots of a cubic equation can be figured out
explicitly with Cardano's method <URL:
http://www.math.vanderbilt.edu/~schectex/courses/cubic/>. The
algebraists were impressed with the solution, but to their
consternation, the formula involved taking the square root of a negative
number even when all three solutions were real.

Temporary integer overflows and excursions into the complex number space
should not be shunned unnecessarily.


Marko