Consider the following binary search for a value greater than lo, but less than or equal to hi:

find(lo: number, hi: number, isTooLow: (testVal: number) => boolean) {
    for(;;) {
        const testVal = between(lo, hi);
        if (testVal <= lo || testVal >= hi) {
            break;
        }
        if (isTooLow(testVal)) {
            lo = testVal;
        } else {
            hi = testVal;
        }
    }
    return hi;
}

Note that a number here is a 64-bit float.

The search will will always terminate, and if the between function is very carefully written to choose the median available 64-bit float between lo and hi, if it exists, then also:

• The search will terminate within 64 iterations; and
• It will exactly find the smallest value hi such that isTooLow(hi) == false

But such a between function is tricky and complicated, and it depends on the fine details of the floating point representation.

Can anyone suggest an implementation for between that is simpler and that does not depend on any specifics of the floating point representation, except that there is a fixed-width mantissa, a fixed-width exponent, and a sign?

It will need to be implemented in Javascript, and it only needs to be almost as good, such that:

• The search will always terminate within 200 iterations or so; and
• It will very nearly (within 3 or 4 possible values) find the smallest value hi such that isTooLow(hi) == false

Extra points for avoiding transcendental functions and sqrt.

CodePudding user response：

Here’s an idea that I think meets your specs on IEEE doubles using primitive operations only (but seems probably worse than using square root assuming that it’s hardware-accelerated). Find the sign (if needed), find the top 7 bits of the 11-bit exponent using linear search (≈ 128 queries, plus 4 for subnormals, ugh), then switch to the arithmetic mean (≈ 53 2¹¹⁻⁷ = 69 queries), for a total of about 200 queries if I’m counting right. Untested JavaScript below.

const multiplicative_stride = 1 / 2 ** (2 ** (11 - 7));
function between(low, high) {
  if (high <= 0) return -between(-high, -low);
  if (low < 0) return 0;
  const mid = multiplicative_stride * high;
  return mid <= low ? low   0.5 * (high - low) : mid;
}

CodePudding user response：

We could also use a look-up table (the sign bit is another branch; can’t see how to avoid it).

const fractions = [];
for (let f = 0.25; f > 0; f *= f) fractions.push(f);
function Guesser() {
  this.i = fractions.length;
  this.between = function (low, high) {
    return low   (this.i > 0 ? fractions[--this.i] : 0.5) * (high - low);
  };
}
g = new Guesser();
for (let i = 0; i < 20;   i) console.log(g.between(1, 2));